ECCC-Report TR15-032https://eccc.weizmann.ac.il/report/2015/032Comments and Revisions published for TR15-032en-usMon, 04 May 2015 09:08:17 +0300
Revision 2
| Graph Isomorphism, Color Refinement, and Compactness |
Vikraman Arvind,
Johannes Köbler,
Gaurav Rattan,
Oleg Verbitsky
https://eccc.weizmann.ac.il/report/2015/032#revision2Color refinement is a classical technique used to show that two given graphs G and H are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a graph G amenable to color refinement if the color-refinement procedure succeeds in distinguishing G from any non-isomorphic graph H. Tinhofer (1991) explored a linear programming approach to Graph Isomorphism and defined the notion of compact graphs: A graph is compact if its fractional automorphisms polytope is integral. Tinhofer noted that isomorphism testing for compact graphs can be done quite efficiently by linear programming. However, the problem of characterizing and recognizing compact graphs in polynomial time remains an open question.
Our results are summarized below:
– We determine the exact range of applicability of color refinement by showing that amenable graphs are recognizable in time O((n + m)logn), where n and m denote the number of vertices and the number of edges in the input graph.
– We show that all amenable graphs are compact. Thus, the applicability range for Tinhofer’s linear programming approach to isomorphism testing is at least as large as for the combinatorial approach based on color refinement.
– Exploring the relationship between color refinement and compactness further, we study related combinatorial and algebraic graph properties introduced by Tinhofer and Godsil. We show that the corresponding classes of graphs form a hierarchy and we prove that recognizing each of these graph classes is P-hard. In particular, this gives a first complexity bound for recognizing compact graphs. and defined the notion of compact graphs: A graph is compact if its fractional automorphisms polytope is integral. Tinhofer noted that isomorphism testing for compact graphs can be done quite efficiently by linear programming. However, the problem of characterizing and recognizing compact graphs in polynomial time remains an open question. Our results are summarized below:
Mon, 04 May 2015 09:08:17 +0300https://eccc.weizmann.ac.il/report/2015/032#revision2
Revision 1
| Graph Isomorphism, Color Refinement, and Compactness |
Vikraman Arvind,
Johannes Köbler,
Gaurav Rattan,
Oleg Verbitsky
https://eccc.weizmann.ac.il/report/2015/032#revision1Color refinement is a classical technique used to show that two given graphs G and H are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a graph G amenable to color refinement if the color-refinement procedure succeeds in distinguishing G from any non-isomorphic graph H. Tinhofer (1991) explored a linear programming approach to Graph IsomorphismColor refinement is a classical technique used to show that two given graphs G and H are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a graph G amenable to color refinement if the color-refinement procedure succeeds in distinguishing G from any non-isomorphic graph H. Tinhofer (1991) explored a linear programming approach to Graph Isomorphism and defined the notion of compact graphs: A graph is compact if its fractional automorphisms polytope is integral. Tinhofer noted that isomorphism testing for compact graphs can be done quite efficiently by linear programming. However, the problem of characterizing and recognizing compact graphs in polynomial time remains an open question. Our results are summarized below: – We determine the exact range of applicability of color refinement by showing that amenable graphs are recognizable in time O((n + m)logn), where n and m denote the number of vertices and the number of edges in the input graph. – We show that all amenable graphs are compact. Thus, the applicability range for Tinhofer’s linear programming approach to isomorphism testing is at least as large as for the combinatorial approach based on color refinement. – Exploring the relationship between color refinement and compactness further, we study related combinatorial and algebraic graph properties introduced by Tinhofer and Godsil. We show that the corresponding classes of graphs form a hierarchy and we prove that recognizing each of these graph classes is P-hard. In particular, this gives a first complexity bound for recognizing compact graphs. and defined the notion of compact graphs: A graph is compact if its fractional automorphisms polytope is integral. Tinhofer noted that isomorphism testing for compact graphs can be done quite efficiently by linear programming. However, the problem of characterizing and recognizing compact graphs in polynomial time remains an open question. Our results are summarized below:
– We determine the exact range of applicability of color refinement by showing that amenable graphs are recognizable in time O((n + m)logn), where n and m denote the number of vertices and the number of edges in the input graph.
– We show that all amenable graphs are compact. Thus, the applicability range for Tinhofer’s linear programming approach to isomorphism testing is at least as large as for the combinatorial approach based on color refinement.
– Exploring the relationship between color refinement and compactness further, we study related combinatorial and algebraic graph properties introduced by Tinhofer and Godsil. We show that the corresponding classes of graphs form a hierarchy and we prove that recognizing each of these graph classes is P-hard. In particular, this gives a first complexity lower bound for recognizing compact graphs.Mon, 04 May 2015 08:43:33 +0300https://eccc.weizmann.ac.il/report/2015/032#revision1
Paper TR15-032
| Graph Isomorphism, Color Refinement, and Compactness |
Vikraman Arvind,
Johannes Köbler,
Gaurav Rattan,
Oleg Verbitsky
https://eccc.weizmann.ac.il/report/2015/032Color refinement is a classical technique used to show that two given graphs $G$ and $H$
are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a graph $G$ amenable to color refinement if the color-refinement procedure succeeds in distinguishing $G$ from any non-isomorphic graph $H$. Babai, Erdos, and Selkow (1982) have shown that random graphs are amenable with high probability.
Our main results are the following:
– We determine the exact range of applicability of color refinement by showing that the class of
amenable graphs is recognizable in time $O((n + m) \log n)$, where $n$ and $m$ denote the number of vertices and the number of edges in the input graph.
– Furthermore, we prove that amenable graphs are compact in the sense of Tinhofer (1991). That is, their polytopes of fractional automorphisms are integral. The concept of compactness was introduced in order to identify the class of graphs G for which isomorphism $G \cong H$ can be decided by computing an extreme point of the polytope of fractional isomorphisms from $G$ to $H$ and checking if this point is integral. Our result implies that the applicability range for this linear programming approach to isomorphism testing is at least as large as for the combinatorial approach based on color refinement.
Fri, 06 Mar 2015 15:05:39 +0200https://eccc.weizmann.ac.il/report/2015/032