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.54
URN: urn:nbn:de:0030-drops-136990
URL: https://drops.dagstuhl.de/opus/volltexte/2021/13699/
Go to the corresponding LIPIcs Volume Portal


Okrasa, Karolina ; Rzążewski, Paweł

Complexity of the List Homomorphism Problem in Hereditary Graph Classes

pdf-format:
LIPIcs-STACS-2021-54.pdf (0.9 MB)


Abstract

A homomorphism from a graph G to a graph H is an edge-preserving 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 time-solvable if H is a so-called bi-arc-graph, and NP-complete otherwise.
We are interested in the complexity of the LHom(H) problem in F-free 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 non-bi-arc graph the LHom(H) problem is NP-complete 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 quasi-polynomial time in P_t-free graphs. On the other hand, if H is predacious, then there exists t, such that the existence of a subexponential-time algorithm for LHom(H) in P_t-free 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 non-predacious and triangle-free. On the other hand, if H is reflexive, then LHom(H) cannot be solved in subexponential time whenever H is not a bi-arc 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:1--54: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/13699},
  URN =		{urn:nbn:de:0030-drops-136990},
  doi =		{10.4230/LIPIcs.STACS.2021.54},
  annote =	{Keywords: list homomorphism, fine-grained complexity, hereditary graph classes}
}

Keywords: list homomorphism, fine-grained 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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI