Böker, Jan ;
Chen, Yijia ;
Grohe, Martin ;
Rattan, Gaurav
The Complexity of Homomorphism Indistinguishability
Abstract
For every graph class {F}, let HomInd({F}) be the problem of deciding whether two given graphs are homomorphismindistinguishable over {F}, i.e., for every graph F in {F}, the number hom(F, G) of homomorphisms from F to G equals the corresponding number hom(F, H) for H. For several natural graph classes (such as paths, trees, bounded treewidth graphs), homomorphismindistinguishability over the class has an efficient structural characterization, resulting in polynomial time solvability [H. Dell et al., 2018].
In particular, it is known that two nonisomorphic graphs are homomorphismindistinguishable over the class {T}_k of graphs of treewidth k if and only if they are not distinguished by kdimensional WeisfeilerLeman algorithm, a central heuristic for isomorphism testing: this characterization implies a polynomial time algorithm for HomInd({T}_k), for every fixed k in N. In this paper, we show that there is a polynomialtimedecidable class {F} of undirected graphs of bounded treewidth such that HomInd({F}) is undecidable.
Our second hardness result concerns the class {K} of complete graphs. We show that HomInd({K}) is coNPhard, and in fact, we show completeness for the class C_=P (under Ptime Turing reductions). On the algorithmic side, we show that HomInd({P}) can be solved in polynomial time for the class {P} of directed paths. We end with a brief study of two variants of the HomInd({F}) problem: (a) the problem of lexographiccomparison of homomorphism numbers of two graphs, and (b) the problem of computing certain distancemeasures (defined via homomorphism numbers) between two graphs.
BibTeX  Entry
@InProceedings{bker_et_al:LIPIcs:2019:10998,
author = {Jan B{\"o}ker and Yijia Chen and Martin Grohe and Gaurav Rattan},
title = {{The Complexity of Homomorphism Indistinguishability}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {54:154:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771177},
ISSN = {18688969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and JoostPieter Katoen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10998},
URN = {urn:nbn:de:0030drops109980},
doi = {10.4230/LIPIcs.MFCS.2019.54},
annote = {Keywords: graph homomorphism numbers, counting complexity, treewidth}
}
20.08.2019
Keywords: 

graph homomorphism numbers, counting complexity, treewidth 
Seminar: 

44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Issue date: 

2019 
Date of publication: 

20.08.2019 