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.ESA.2020.74
URN: urn:nbn:de:0030-drops-129402
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12940/
Okrasa, Karolina ;
Piecyk, Marta ;
Rzążewski, Paweł
Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs
Abstract
A homomorphism from a graph G to a graph H is an edge-preserving mapping from V(G) to V(H). Let H be a fixed graph with possible loops. In the list homomorphism problem, denoted by LHom(H), we are given a graph G, whose every vertex v is assigned with a list L(v) of vertices of H. We ask whether there exists a homomorphism h from G to H, which respects lists L, i.e., for every v ∈ V(G) it holds that h(v) ∈ L(v).
The complexity dichotomy for LHom(H) was proven by Feder, Hell, and Huang [JGT 2003]. The authors showed that the problem is polynomial-time solvable if H belongs to the class called bi-arc graphs, and for all other graphs H it is NP-complete.
We are interested in the complexity of the LHom(H) problem, parameterized by the treewidth of the input graph. This problem was investigated by Egri, Marx, and Rzążewski [STACS 2018], who obtained tight complexity bounds for the special case of reflexive graphs H, i.e., if every vertex has a loop.
In this paper we extend and generalize their results for all relevant graphs H, i.e., those, for which the LHom(H) problem is NP-hard. For every such H we find a constant k = k(H), such that the LHom(H) problem on instances G with n vertices and treewidth t
- can be solved in time k^t ⋅ n^?(1), provided that G is given along with a tree decomposition of width t,
- cannot be solved in time (k-ε)^t ⋅ n^?(1), for any ε > 0, unless the SETH fails. For some graphs H the value of k(H) is much smaller than the trivial upper bound, i.e., |V(H)|.
Obtaining matching upper and lower bounds shows that the set of algorithmic tools that we have discovered cannot be extended in order to obtain faster algorithms for LHom(H) in bounded-treewidth graphs. Furthermore, neither the algorithm, nor the proof of the lower bound, is very specific to treewidth. We believe that they can be used for other variants of the LHom(H) problem, e.g. with different parameterizations.
BibTeX - Entry
@InProceedings{okrasa_et_al:LIPIcs:2020:12940,
author = {Karolina Okrasa and Marta Piecyk and Pawe{\l} Rzążewski},
title = {{Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {74:1--74:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-162-7},
ISSN = {1868-8969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12940},
URN = {urn:nbn:de:0030-drops-129402},
doi = {10.4230/LIPIcs.ESA.2020.74},
annote = {Keywords: list homomorphisms, fine-grained complexity, SETH, treewidth}
}
|
Keywords: |
|
list homomorphisms, fine-grained complexity, SETH, treewidth |
|
Collection: |
|
28th Annual European Symposium on Algorithms (ESA 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
26.08.2020 |
