3
$\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

1 Answer 1

Reset to default
7
$\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$
    – Kevin Ventullo
    Nov 17, 2013 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$
    – under_the_sea_salad
    Nov 17, 2013 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, 2013 at 1:18
  • $\begingroup$ Yes, this makes sense to me. $\endgroup$
    – under_the_sea_salad
    Nov 17, 2013 at 23:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .