License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2018.27
URN: urn:nbn:de:0030-drops-84867
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8486/
Egri, László ;
Marx, Dániel ;
Rzazewski, Pawel
Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization
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 self-loop. If is known that reflexive LHom(H) is polynomial-time solvable if H is an interval graph and it is NP-complete 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 non-interval 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 Exponential-Time 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 Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {27:1--27:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-062-0},
ISSN = {1868-8969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8486},
URN = {urn:nbn:de:0030-drops-84867},
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 |
