Is there any specific computational complexity result of Graph Isomorphism for Triangle Free graphs?
Anything close to the subject will help and of course, I have searched Google.
$\begingroup$
$\endgroup$
8
-
5$\begingroup$ What if you "blow up" a graph by replacing every edge by a path of length 2? This results in a triangle-free graph, and if all nodes of the original graphs have degree larger than 2, then two graphs are isomorphic if and only if their blow-ups are isomorphic. (BTW, does this construction have a name? It's definitely not blow-up, which already has a different meaning for graphs...) Hence graph isomorphism for triangle-free graphs should have complexity equal to graph isomorphism in general. $\endgroup$– Tobias FritzCommented Apr 19, 2016 at 14:40
-
2$\begingroup$ @TobiasFritz The name of your construction is the ''barycentric subdivision.'' $\endgroup$– Tony HuynhCommented Apr 19, 2016 at 14:49
-
2$\begingroup$ As per Tobias's argument, any graph class able to encode all graphs has similar worst-case complexity, but average case and other randomized complexities can differ. $\endgroup$– logicuteCommented Apr 19, 2016 at 14:50
-
$\begingroup$ @TonyHuynh: thanks, of course! I didn't see that this was just a special case of a familiar construction... $\endgroup$– Tobias FritzCommented Apr 19, 2016 at 14:55
-
$\begingroup$ @TobiasFritz ok just to be sure,consoder a situation, where we can decide GI if graphs are not triangle free graphs in $f(n)$ time using an algo. But algo does work if graphs are triangle free, according to you , we can reconstruct and use the algo? $\endgroup$– MichaelCommented Apr 19, 2016 at 14:57
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
4
The following very simple answer addresses worst-case complexity. How to do the reduction in practice would be a different question, as would average complexity (as pointed out by logicute).
For a graph $G$, let $\hat{G}$ denote the barycentric subdivision of $G$. This is triangle-free. I claim that $G$ can be reconstructed from $\hat{G}$, as follows. Since the connected components of $G$ and $\hat{G}$ are in an obvious bijection, it is enough to consider the case of connected $G$. This means that we can determine the bipartition of $\hat{G}$ into the vertices of $G$ and the edges of $G$, but we might not yet know which bipartition class is which. If $\hat{G}$ has a vertex of degree $\neq 2$, then we know that this vertex must belong to the bipartition class of vertices of $G$. This disambiguates things and we can reconstruct $G$ by taking this bipartition class and using the paths of length $2$ as the edges; this recovers $G$. Otherwise, all vertices in $\hat{G}$ have degree $2$, which implies that $\hat{G}$ is a cycle because of connectedness, and therefore also $G$ must have been a cycle (of half the size).
This reconstruction shows that if $\hat{G}$ and $\hat{H}$ are isomorphic, then so are $G$ and $H$. The converse is clear. Taking $G\mapsto \hat{G}$ is therefore a polynomial-time reduction from graph isomorphism to triangle-free graph isomorphism.
Thanks to Tony Huynh for pointing out that replacing an edge by a path of length $2$ is exactly barycentric subdivision. For a discussion on whether isomorphism of barycentric subdivsions of simplicial complexes implies isomorphism, see this question.
answered Apr 19, 2016 at 15:47
-
$\begingroup$ I would like to send you my paper on graph isomorphism, if you permit. $\endgroup$– MichaelCommented Apr 26, 2016 at 14:45
-
$\begingroup$ @Jim: please feel free to email me, it should be fun to take a look! But there also will be people out there who are much more qualified than me to give you helpful feedback. So you might instead want to ask somebody who has actually done research on graph isomorphism (which I haven't). $\endgroup$ Commented Apr 27, 2016 at 2:26
-
2$\begingroup$ so in other words this is basically a proof that triangle free graphs are GI-complete? $\endgroup$– vznCommented Jun 2, 2016 at 18:40
-
$\begingroup$ @vzn: yes, that's correct. In fact, your link provides references to several strictly smaller classes of graphs that are still GI-complete. (Since e.g. every bipartite graph is triangle-free.) $\endgroup$ Commented Jun 2, 2016 at 18:53