Abstract
For graphs G,H, a homomorphism from G to H is an edgepreserving 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 finegrained 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 NPhard, 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 kColoring (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 nonlist 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 = {{FineGrained 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:156:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771801},
ISSN = {18688969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13701},
URN = {urn:nbn:de:0030drops137012},
doi = {10.4230/LIPIcs.STACS.2021.56},
annote = {Keywords: list homomorphisms, finegrained complexity, SETH, feedback vertex set, cutwidth}
}
Keywords: 

list homomorphisms, finegrained 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 