Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
On Tinhofer's Linear Programming Approach to Isomorphism Testing
Ist Teil von
Mathematical Foundations of Computer Science 2015, 2015, Vol.9235, p.26-37
Ort / Verlag
Germany: Springer Berlin / Heidelberg
Erscheinungsjahr
2015
Link zum Volltext
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
Exploring a linear programming approach to Graph Isomorphism, Tinhofer (1991) defined the notion of compact graphs: A graph is compact if the polytope of its fractional automorphisms 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. In this paper we make new progress in our understanding of compact graphs. Our results are summarized below:We show that all graphs G which are distinguishable from any non-isomorphic graph by the classical color-refinement procedure are compact. In other words, 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.