Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.58
URN: urn:nbn:de:0030-drops-134027
URL: https://drops.dagstuhl.de/opus/volltexte/2020/13402/
Chen, Hubie ; Jansen, Bart M. P. ; Okrasa, Karolina ; Pieterse, Astrid ; Rzążewski, Paweł
Sparsification Lower Bounds for List H-Coloring
| pdf-format: |
|
Abstract
We investigate the List H-Coloring problem, the generalization of graph coloring that asks whether an input graph G admits a homomorphism to the undirected graph H (possibly with loops), such that each vertex v ∈ V(G) is mapped to a vertex on its list L(v) ⊆ V(H). An important result by Feder, Hell, and Huang [JGT 2003] states that List H-Coloring is polynomial-time solvable if H is a so-called bi-arc graph, and NP-complete otherwise. We investigate the NP-complete cases of the problem from the perspective of polynomial-time sparsification: can an n-vertex instance be efficiently reduced to an equivalent instance of bitsize 𝒪(n^(2-ε)) for some ε > 0? We prove that if H is not a bi-arc graph, then List H-Coloring does not admit such a sparsification algorithm unless NP ⊆ coNP/poly. Our proofs combine techniques from kernelization lower bounds with a study of the structure of graphs H which are not bi-arc graphs.
BibTeX - Entry
@InProceedings{chen_et_al:LIPIcs:2020:13402,
author = {Hubie Chen and Bart M. P. Jansen and Karolina Okrasa and Astrid Pieterse and Pawe{\l} Rzążewski},
title = {{Sparsification Lower Bounds for List H-Coloring}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {58:1--58:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-173-3},
ISSN = {1868-8969},
year = {2020},
volume = {181},
editor = {Yixin Cao and Siu-Wing Cheng and Minming Li},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13402},
URN = {urn:nbn:de:0030-drops-134027},
doi = {10.4230/LIPIcs.ISAAC.2020.58},
annote = {Keywords: List H-Coloring, Sparsification, Constraint Satisfaction Problem}
}
| Keywords: | List H-Coloring, Sparsification, Constraint Satisfaction Problem | |
| Seminar: | 31st International Symposium on Algorithms and Computation (ISAAC 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 04.12.2020 |
