Abstract
A homomorphism from a graph G to a graph H is an edgepreserving mapping from V(G) to V(H). For a fixed graph 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). We ask if there exists a homomorphism f from G to H, in which f(v) ∈ L(v) for every v ∈ V(G). Feder, Hell, and Huang [JGT 2003] proved that LHom(H) is polynomial timesolvable if H is a socalled biarcgraph, and NPcomplete otherwise.
We are interested in the complexity of the LHom(H) problem in Ffree graphs, i.e., graphs excluding a copy of some fixed graph F as an induced subgraph. It is known that if F is connected and is not a path nor a subdivided claw, then for every nonbiarc graph the LHom(H) problem is NPcomplete and cannot be solved in subexponential time, unless the ETH fails. We consider the remaining cases for connected graphs F.
If F is a path, we exhibit a full dichotomy. We define a class called predacious graphs and show that if H is not predacious, then for every fixed t the LHom(H) problem can be solved in quasipolynomial time in P_tfree graphs. On the other hand, if H is predacious, then there exists t, such that the existence of a subexponentialtime algorithm for LHom(H) in P_tfree graphs would violate the ETH.
If F is a subdivided claw, we show a full dichotomy in two important cases: for H being irreflexive (i.e., with no loops), and for H being reflexive (i.e., where every vertex has a loop). Unless the ETH fails, for irreflexive H the LHom(H) problem can be solved in subexponential time in graphs excluding a fixed subdivided claw if and only if H is nonpredacious and trianglefree. On the other hand, if H is reflexive, then LHom(H) cannot be solved in subexponential time whenever H is not a biarc graph.
BibTeX  Entry
@InProceedings{okrasa_et_al:LIPIcs.STACS.2021.54,
author = {Okrasa, Karolina and Rz\k{a}\.{z}ewski, Pawe{\l}},
title = {{Complexity of the List Homomorphism Problem in Hereditary Graph Classes}},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages = {54:154: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/13699},
URN = {urn:nbn:de:0030drops136990},
doi = {10.4230/LIPIcs.STACS.2021.54},
annote = {Keywords: list homomorphism, finegrained complexity, hereditary graph classes}
}
Keywords: 

list homomorphism, finegrained complexity, hereditary graph classes 
Collection: 

38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) 
Issue Date: 

2021 
Date of publication: 

10.03.2021 