2
$\begingroup$

I was reading about The Graph Isomorphism Problem on Wikipedia and the article lists a number of special cases for which the problem can be solved in polynomial time. One of these cases is a graph of bounded degree, i.e.,

the number of incident edges to any node in the graph is bounded by an integer (for the entire graph).

I can't think of a graph that wouldn't be of bounded degree. Can someone give an example or perhaps clarify what the article or definition is saying that I do not understand.

Here is the original Wikipedia article which talks of graphs of bounded degree (although it will probably be unhelpful in answering my question): https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Solved_special_cases.

Here is the Wikipedia article on the degree of a graph: https://en.wikipedia.org/wiki/Degree_(graph_theory).

My best guess at a graph of unbounded degree is something like a Caley digraph for the multiplicative group of positive integers (so any node/integer is connected to an infinite number of nodes/integers), but I am not sure if I understand the definitions correctly.

$\endgroup$
0
5
$\begingroup$

Of course any finite graph has a bounded degree. What the article means is that if you fix some number $k$, then the graph isomorphism problem for graphs of order $n$ can be solved in time $O(P(n))$, where $P$ is a polynomial which depends on k.

The point is that a general graph of order $n$ could have vertices with degree roughly the size of $n$. But as $n$ grows, if I only look at graphs with max degree at most $5$, then I can solve the graph isomorphism problem in polynomial time. If I change the 5 to 10, then I can still do it in polynomial time, but the polynomial is larger.

The general graph isomorphism problem would require you to let $k$ get larger as $n$ gets larger, so you'd be getting bigger and bigger polynomials as $n$ gets large, i.e. there is no one polynomial which could bound all of them.

Does this make sense?

$\endgroup$
4
  • $\begingroup$ So "bounded degree" means you're bounding the max degree by some fixed constant, and letting $n\rightarrow \infty$. $\endgroup$ Nov 17 '13 at 0:13
  • $\begingroup$ Okay, I think I see what you are saying (so maybe a possible isomorphism between complete graphs, ones in which the degree is directly proportional to the number of nodes, cannot be evaluated by the algorithm which requires the degree to be bounded), but I'm still having trouble grasping this. (I'll get back to you on this and see if I can accept your answer.) $\endgroup$ Nov 17 '13 at 0:22
  • 2
    $\begingroup$ @ijkilchenko: Consider a hypothetical algorithm which takes $O(n^k)$ time, where $n$ is the number of nodes and $k$ is the maximum degree. $\endgroup$
    – user856
    Nov 17 '13 at 1:18
  • $\begingroup$ Yes, this makes sense to me. $\endgroup$ Nov 17 '13 at 23:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.