1
$\begingroup$

This paper gives example of polynomial GI for certain graphs.

Probably I am misunderstanding the paper, but appears to me it implies polynomial GI for cubic, $4$-regular and probably higher degree regular graphs.

GI for regular graphs is GI complete.

On p. 7 the graphs $H(a,b,c)$ are defined. They are a claw with $a+b$ leaves, $a$ edges are subdivided and $c$ isolated vertices are added.

On p. 8 Theorem 4. Isomorphism of $(H(0, b, c), \overline{H(0, b' , c' ))}$-free graphs is in $P$ when:

(2.) $c, c′ \le 1$ and $b, b' \ge 1$.

Take $c=c'=1,b=b'=5$.

$H=H(0,5,1)$ is $K_{1,5} + K_1$.

Both $H$ and $\overline{H}$ have degree $5$ vertex, so neither can be induced subgraph of cubic or $4$ regular graph.

By taking larger $b$ this works for higher degree regular graphs.

  1. Does the paper imply GI is in $P$ for cubic and $4$-regular graphs?

  2. Does the paper imply GI is in $P$ for higher degree regular graphs (the running time might depend on $b$, not sure)?

Improve this question
$\endgroup$
6
  • 5
    $\begingroup$ Graph isomorphism is in P for classes of bounded degree graphs. 4 regular graph is just a subset of this graphs. $\endgroup$
    – Saeed
    Jun 14, 2014 at 13:11
  • $\begingroup$ @Saeed Thank you. What about the second question for larger $b$? $\endgroup$
    – joro
    Jun 14, 2014 at 13:16
  • $\begingroup$ @DavidRicherby According to "Problems Polynomially equivalent to Graph Isomorphism",Booth GI for regular graphs is GI complete or am misunderstanding your comment? Regarding the second question for larger $b$. $\endgroup$
    – joro
    Jun 14, 2014 at 14:34
  • $\begingroup$ I've not checked your implications but GI is in P for any class of graphs that has bounded degree so, in particular, for the class of $d$-regular graphs for any fixed $d$. Eugene Luks, "Isomorphism of graphs of bounded valence can be tested in polynomial time", Journal of Computer and System Sciences 25:1(42–65), 1982. PDF. $\endgroup$
    – David Richerby
    Jun 14, 2014 at 14:36
  • $\begingroup$ @joro In my second point, I had missed the fact that the class of all regular graphs doesn't have bounded degree so we don't know GI is in P there. I couldn't edit the comment because of the stoopid 5-minute rule so I deleted it and reposted. $\endgroup$
    – David Richerby
    Jun 14, 2014 at 14:38

1 Answer 1

Reset to default
1
$\begingroup$

Their paper doesn't say anything about general regular graphs. Note that the $b$ is constant. Actually all of their excluded subgraphs are constant. Their polynomial time algorithm is consist of considering all possible $K_{2b+1}$'s in that case. This causes to running time $\Omega(n^{2b+1})$. Means if we want to use their algorithm for $r$-regular graph then we should use running time $\Omega(n^{2r+1})$, means when $r$ is not fix their algorithm is not polynomial time in the size of input. Actually we can say that they proved the problem in that case belongs to XP when the problem parametrized by $b$. Don't mix parametrized complexity with usual polynomial time algorithms.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Thank you. So modification of this gives poly in $t$ for $K_{1,t}$-free of bounded clique number. $\endgroup$
    – joro
    Jun 15, 2014 at 9:12
  • $\begingroup$ @joro, If we suppose $t$ is fixed yes ($K_{1,t}$-free is actually trivial because it's bounded degree). $\endgroup$
    – Saeed
    Jun 15, 2014 at 9:14
  • $\begingroup$ I think $K_n$ are counterexamples to bounded degree claw free graphs. $\endgroup$
    – joro
    Jun 15, 2014 at 9:27
  • $\begingroup$ @joro, I said if $t$ is fixed and for $K_n$, $t$ is not fixed because for every $t\in[n-1]$ there is a $K_{1,t}$ in $K_n$ as a subgraph. It is just $K_{1,n}$ free which is not a fix $t$. Their algorithm basically doesn't work in this case. Please read about parametrized complexity either on wiki or my link, if you understand this terminology you won't confuse in such cases. $\endgroup$
    – Saeed
    Jun 15, 2014 at 14:08
  • $\begingroup$ I don't think $K_5$ contains induced $K_{1,3}$ aka claw. I was just pointing out claw-free doesn't imply bounded degree. $\endgroup$
    – joro
    Jun 15, 2014 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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