License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2021.56
URN: urn:nbn:de:0030-drops-137012
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13701/
Piecyk, Marta ;
Rzążewski, Paweł
Fine-Grained Complexity of the List Homomorphism Problem: Feedback Vertex Set and Cutwidth
Abstract
For graphs G,H, a homomorphism from G to H is an edge-preserving mapping from V(G) to V(H). In the list homomorphism problem, denoted by LHom(H), we are given a graph G, whose every vertex v is equipped with a list L(v) ⊆ V(H), and we need to determine whether there exists a homomorphism from G to H which additionally respects the lists L. List homomorphisms are a natural generalization of (list) colorings.
Very recently Okrasa, Piecyk, and Rzążewski [ESA 2020] studied the fine-grained complexity of the problem, parameterized by the treewidth of the instance graph G. They defined a new invariant i^*(H), and proved that for every relevant graph H, i.e., such that LHom(H) is NP-hard, this invariant is the correct base of the exponent in the running time of any algorithm solving the LHom(H) problem.
In this paper we continue this direction and study the complexity of the problem under different parameterizations. As the first result, we show that i^*(H) is also the right complexity base if the parameter is the size of a minimum feedback vertex set of G, denoted by fvs(G). In particular, for every relevant graph H, the LHom(H) problem
- can be solved in time i^*(H)^fvs(G) ⋅ |V(G)|^?(1), if a minimum feedback vertex set of G is given,
- cannot be solved in time (i^*(H) - ε)^fvs(G) ⋅ |V(G)|^?(1), for any ε > 0, unless the SETH fails. Then we turn our attention to a parameterization by the cutwidth ctw(G) of G. Jansen and Nederlof [TCS 2019] showed that List k-Coloring (i.e., LHom(K_k)) can be solved in time c^ctw(G) ⋅ |V(G)|^?(1) for an absolute constant c, i.e., the base of the exponential function does not depend on the number of colors. Jansen asked whether this behavior extends to graph homomorphisms. As the main result of the paper, we answer the question in the negative. We define a new graph invariant mim^*(H), closely related to the size of a maximum induced matching in H, and prove that for all relevant graphs H, the LHom(H) problem cannot be solved in time (mim^*(H)-ε)^{ctw(G)}⋅ |V(G)|^?(1) for any ε > 0, unless the SETH fails. In particular, this implies that, assuming the SETH, there is no constant c, such that for every odd cycle the non-list version of the problem can be solved in time c^ctw(G) ⋅ |V(G)|^?(1).
BibTeX - Entry
@InProceedings{piecyk_et_al:LIPIcs.STACS.2021.56,
author = {Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}},
title = {{Fine-Grained Complexity of the List Homomorphism Problem: Feedback Vertex Set and Cutwidth}},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages = {56:1--56:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-180-1},
ISSN = {1868-8969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13701},
URN = {urn:nbn:de:0030-drops-137012},
doi = {10.4230/LIPIcs.STACS.2021.56},
annote = {Keywords: list homomorphisms, fine-grained complexity, SETH, feedback vertex set, cutwidth}
}
|
Keywords: |
|
list homomorphisms, fine-grained complexity, SETH, feedback vertex set, cutwidth |
|
Collection: |
|
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
10.03.2021 |
