2026-06-05T23:18:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13402 2024-03-06T10:51:53Z ddc:004 open_access

Sparsification Lower Bounds for List H-Coloring Chen, Hubie Jansen, Bart M. P. Okrasa, Karolina Pieterse, Astrid Rzążewski, Paweł List H-Coloring Sparsification Constraint Satisfaction Problem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hubie Chen and Bart M. P. Jansen and Karolina Okrasa and Astrid Pieterse and Paweł Rzążewski 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.58 urn:nbn:de:0030-drops-134027 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.58 eng https://creativecommons.org/licenses/by/3.0/legalcode