Abstract
A homomorphism from a graph G to a graph H is an edgepreserving 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 polynomialtime solvable if H belongs to the class called biarc graphs, and for all other graphs H it is NPcomplete.
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 NPhard. 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 boundedtreewidth 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 BoundedTreewidth Graphs}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {74:174:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12940},
URN = {urn:nbn:de:0030drops129402},
doi = {10.4230/LIPIcs.ESA.2020.74},
annote = {Keywords: list homomorphisms, finegrained complexity, SETH, treewidth}
}
Keywords: 

list homomorphisms, finegrained complexity, SETH, treewidth 
Collection: 

28th Annual European Symposium on Algorithms (ESA 2020) 
Issue Date: 

2020 
Date of publication: 

26.08.2020 