Abstract
In the list homomorphism problem, the input consists of two graphs G and H, together with a list L(v) \subseteq V(H) for every vertex v \in V(G). The task is to find a homomorphism phi:V(G) > V(H) respecting the lists, that is, we have that phi(v) \in L(v) for every v \in V(H) and if u and v are adjacent in G, then phi(u) and phi(v) are adjacent in H. If H is a fixed graph, then the problem is denoted LHom(H). We consider the reflexive version of the problem, where we assume that every vertex
in H has a selfloop. If is known that reflexive LHom(H) is polynomialtime solvable if H is an interval graph and it is NPcomplete otherwise [Feder and Hell, JCTB 1998].
We explore the complexity of the problem parameterized by the treewidth tw(G) of the input graph G. If a tree decomposition of G of width tw(G) is given in the input, then the problem can be solved in time V(H)^{tw(G)} n^{O(1)} by naive dynamic programming. Our main result completely reveals when and by exactly how much this naive algorithm can be improved. We introduce a simple combinatorial invariant i^*(H), which is based on the existence of decompositions and incomparable sets, and show that this number should appear as the base of the exponent in the best possible running time. Specifically, we prove for every fixed noninterval graph H that
* If a tree decomposition of width tw(G) is given in the input, then the problem can be solved in time i^*(H)^{tw(G)} n^{O(1)}.
* Assuming the Strong ExponentialTime Hypothesis (SETH), the probem cannot be solved in time (i^*(H)epsilon)^{tw(G)} n^{O(1)} for any epsilon>0.
Thus by matching upper and lower bounds, our result exactly characterizes for every fixed H the complexity of reflexive LHom(H) parameterized by treewidth.
BibTeX  Entry
@InProceedings{egri_et_al:LIPIcs:2018:8486,
author = {L{\'a}szl{\'o} Egri and D{\'a}niel Marx and Pawel Rzazewski},
title = {{Finding List Homomorphisms from Boundedtreewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {27:127:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770620},
ISSN = {18688969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8486},
URN = {urn:nbn:de:0030drops84867},
doi = {10.4230/LIPIcs.STACS.2018.27},
annote = {Keywords: graph homomorphism, list homomorphism, reflexive graph, treewidth}
}
Keywords: 

graph homomorphism, list homomorphism, reflexive graph, treewidth 
Collection: 

35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) 
Issue Date: 

2018 
Date of publication: 

27.02.2018 