<p>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 <a href="https://cs.stackexchange.com/questions/1477/dealing-with-intractability-np-complete-problems/11773#11773">parametrized complexity</a> with usual polynomial time algorithms.</p>

CC BY-SA 3.0
2014-06-15T09:12:20.697Z
Thank you. So modification of this gives poly in $t$ for $K_{1,t}$-free of bounded clique number.
joro
CC BY-SA 3.0
2014-06-15T09:14:18.147Z
@joro, If we suppose $t$ is fixed yes ($K_{1,t}$-free is actually trivial because it's bounded degree).
Saeed
CC BY-SA 3.0
2014-06-15T09:27:16.610Z
I think $K_n$ are counterexamples to bounded degree claw free graphs.
joro
CC BY-SA 3.0
2014-06-15T14:08:26.843Z
@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.
Saeed
CC BY-SA 3.0
2014-06-15T14:13:40.327Z
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.
joro
CC BY-SA 3.0
2014-06-15T14:27:31.507Z
@joro, Yes, you are right, I misunderstood your first comment. I thought you talking about subgraph not induced subgraph (I answered the question yesterday and when I saw your comment I thought you talking about subgraph not induced subgraph). And yes as you can see their work they are considering all cliques of size $2t+1$ to provide a proper coloring to show isomorphism equivalence so their algorithm still works for the case that you mentioned but if $t$ is fixed. Also $K_{1,t}$ is special case of their theorem.
Saeed
CC BY-SA 3.0
2014-06-15T14:32:06.197Z
No problem. I think it is common terminology $X$-free to mean _induced_ $X$.
joro
CC BY-SA 3.0
2014-06-15T14:34:46.150Z
@joro, Not actually, at least for me. I'm working in closely related aspects and when I say X-free I usually mean X-minor free, and for me is not common to use it neither for a subgraph nor for an induced subgraph.
Saeed
CC BY-SA 3.0
2014-06-15T14:37:25.260Z
Anyway, the paper defines it as induced.
joro
CC BY-SA 3.0
2014-06-15T14:37:59.960Z
@joro, Yeah, and in the answer I talked about induced.
Saeed
CC BY-SA 3.0
2014-06-14T19:30:04.997Z
2014-06-14T19:30:04.997Z
2017-04-13T12:48:30.830Z
Saeed
<p><a href="http://arxiv.org/abs/1208.0142" rel="nofollow">This paper</a> gives example
of polynomial GI for certain graphs.</p>

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

<p>GI for regular graphs is GI complete.</p>

<p>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.</p>

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

<p>(2.) $c, c′ \le 1$ and $b, b' \ge 1$.</p>

<p>Take $c=c'=1,b=b'=5$.</p>

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

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

<p>By taking larger $b$ this works for higher
degree regular graphs.</p>

<ol>
<li><p>Does the paper imply GI is in $P$ for cubic
and $4$-regular graphs?</p></li>
<li><p>Does the paper imply GI is in $P$ for higher
degree regular graphs (the running time might
depend on $b$, not sure)?</p></li>
</ol>

CC BY-SA 3.0
2014-06-14T13:11:45.190Z
Graph isomorphism is in P for classes of bounded degree graphs. 4 regular graph is just a subset of this graphs.
Saeed
CC BY-SA 3.0
2014-06-14T13:16:53.593Z
@Saeed Thank you. What about the second question for larger $b$?
joro
CC BY-SA 3.0
2014-06-14T14:34:59.480Z
@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$.
joro
CC BY-SA 3.0
2014-06-14T14:36:46.090Z
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](http://www.sciencedirect.com/science/article/pii/0022000082900095).
David Richerby
CC BY-SA 3.0
2014-06-14T14:38:14.697Z
@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.
David Richerby
CC BY-SA 3.0
2014-06-14T14:41:13.347Z
@DavidRicherby According to [this paper](https://cs.uwaterloo.ca/research/tr/1977/CS-77-04.pdf) GI is complete for regular graphs.
joro
<graph-theory><graph-isomorphism>
Does this paper imply graph isomorphism is polynomial for cubic and $4$-regular graphs?
joro
# Does this paper imply graph isomorphism is polynomial for cubic and $4$-regular graphs?

(Asked by: username_0 on 2014-06-14)

[This paper](http://arxiv.org/abs/1208.0142) 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)?

**Tags:** graph-theory, graph-isomorphism
> **Comments:**
> **username_1**: Graph isomorphism is in P for classes of bounded degree graphs. 4 regular graph is just a subset of this graphs.  
> **username_0**: @Saeed Thank you. What about the second question for larger $b$?  
> **username_0**: @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$.  
> **username_2**: 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](http://www.sciencedirect.com/science/article/pii/0022000082900095).  
> **username_2**: @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.  
> **username_0**: @DavidRicherby According to [this paper](https://cs.uwaterloo.ca/research/tr/1977/CS-77-04.pdf) GI is complete for regular graphs.  

---

## 1 answers

### Answer by username_1 on 2014-06-14. Score: 1 | Accepted answer

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](https://cs.stackexchange.com/questions/1477/dealing-with-intractability-np-complete-problems/11773#11773) with usual polynomial time algorithms.

> **Comments:**
> **username_0**: Thank you. So modification of this gives poly in $t$ for $K_{1,t}$-free of bounded clique number.  
> **username_1**: @joro, If we suppose $t$ is fixed yes ($K_{1,t}$-free is actually trivial because it's bounded degree).  
> **username_0**: I think $K_n$ are counterexamples to bounded degree claw free graphs.  
> **username_1**: @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.  
> **username_0**: 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.  
> **username_1**: @joro, Yes, you are right, I misunderstood your first comment. I thought you talking about subgraph not induced subgraph (I answered the question yesterday and when I saw your comment I thought you talking about subgraph not induced subgraph). And yes as you can see their work they are considering all cliques of size $2t+1$ to provide a proper coloring to show isomorphism equivalence so their algorithm still works for the case that you mentioned but if $t$ is fixed. Also $K_{1,t}$ is special case of their theorem.  
> **username_0**: No problem. I think it is common terminology $X$-free to mean _induced_ $X$.  
> **username_1**: @joro, Not actually, at least for me. I'm working in closely related aspects and when I say X-free I usually mean X-minor free, and for me is not common to use it neither for a subgraph nor for an induced subgraph.  
> **username_0**: Anyway, the paper defines it as induced.  
> **username_1**: @joro, Yeah, and in the answer I talked about induced.  

---

