Dell, Holger ;
Grohe, Martin ;
Rattan, Gaurav
Lovász Meets Weisfeiler and Leman
Abstract
In this paper, we relate a beautiful theory by Lovász with a popular heuristic algorithm for the graph isomorphism problem, namely the color refinement algorithm and its kdimensional generalization known as the WeisfeilerLeman algorithm. We prove that two graphs G and H are indistinguishable by the color refinement algorithm if and only if, for all trees T, the number Hom(T,G) of homomorphisms from T to G equals the corresponding number Hom(T,H) for H.
There is a natural system of linear equations whose nonnegative integer solutions correspond to the isomorphisms between two graphs. The nonnegative real solutions to this system are called fractional isomorphisms, and two graphs are fractionally isomorphic if and only if the color refinement algorithm cannot distinguish them (Tinhofer 1986, 1991). We show that, if we drop the nonnegativity constraints, that is, if we look for arbitrary real solutions, then a solution to the linear system exists if and only if, for all t, the two graphs have the same number of lengtht walks.
We lift the results for trees to an equivalence between numbers of homomorphisms from graphs of tree width k, the kdimensional WeisfeilerLeman algorithm, and the levelk SheraliAdams relaxation of our linear program. We also obtain a partial result for graphs of bounded path width and solutions to our system where we drop the nonnegativity constraints.
A consequence of our results is a quasilinear time algorithm to decide whether, for two given graphs G and H, there is a tree T with Hom(T,G)!=Hom(T,H).
BibTeX  Entry
@InProceedings{dell_et_al:LIPIcs:2018:9044,
author = {Holger Dell and Martin Grohe and Gaurav Rattan},
title = {{Lov{\'a}sz Meets Weisfeiler and Leman}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {40:140:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9044},
URN = {urn:nbn:de:0030drops90444},
doi = {10.4230/LIPIcs.ICALP.2018.40},
annote = {Keywords: graph isomorphism, graph homomorphism numbers, tree width}
}
2018
Keywords: 

graph isomorphism, graph homomorphism numbers, tree width 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

2018 