Sparsification Lower Bounds for List H-Coloring

Hubie  Chen; Bart M.P. Jansen; Karolina Okrasa; Astrid Pieterse; Paweł Rzążewski

doi:10.1145/3612938

Sparsification Lower Bounds for List H-Coloring

Hubie Chen, Bart M.P. Jansen, Karolina Okrasa, Astrid Pieterse, Paweł Rzążewski

Graph Algorithms

Research output: Contribution to journal › Article › Academic › peer-review

52 Downloads (Pure)

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 O(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-graphs.

Original language	English
Article number	8
Number of pages	23
Journal	ACM Transactions on Computation Theory
Volume	15
Issue number	3-4
DOIs	https://doi.org/10.1145/3612938
Publication status	Published - Dec 2023

Funding

B. M. P. Jansen was supported by NWO Gravitation grant “Networks.” K. Okrasa was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme Grant Agreement No. 714704. A. Pieterse was supported by a DFG Emmy Noether-grant (KR 4286/1). Part of this research was supported by NWO Gravitation grant “Networks.” P. Rzążewski was supported by Polish National Science Centre Grant No. 2018/31/D/ST6/00062.

Funders	Funder number
European Union's Horizon 2020 - Research and Innovation Framework Programme	714704
H2020 European Research Council
Deutsche Forschungsgemeinschaft	KR 4286/1
Nederlandse Organisatie voor Wetenschappelijk Onderzoek
Narodowe Centrum Nauki	2018/31/D/ST6/00062

Keywords

List H-coloring
constraint satisfaction problem
sparsification

Access to Document

10.1145/3612938Licence: CC BY

pdfFinal published version, 662 KBLicence: CC BY

Cite this

@article{6cd0cd13e63b4cca9d3b800c69a29ca0,

title = "Sparsification Lower Bounds for List H-Coloring",

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 O(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-graphs.",

keywords = "List H-coloring, constraint satisfaction problem, sparsification",

author = "Hubie Chen and Jansen, \{Bart M.P.\} and Karolina Okrasa and Astrid Pieterse and Pawe{\l} Rz{\c a}{\.z}ewski",

year = "2023",

month = dec,

doi = "10.1145/3612938",

language = "English",

volume = "15",

journal = "ACM Transactions on Computation Theory",

issn = "1942-3454",

publisher = "Association for Computing Machinery, Inc.",

number = "3-4",

}

TY - JOUR

T1 - Sparsification Lower Bounds for List H-Coloring

AU - Chen, Hubie

AU - Jansen, Bart M.P.

AU - Okrasa, Karolina

AU - Pieterse, Astrid

AU - Rzążewski, Paweł

PY - 2023/12

Y1 - 2023/12

N2 - 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 O(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-graphs.

AB - 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 O(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-graphs.

KW - List H-coloring

KW - constraint satisfaction problem

KW - sparsification

UR - http://www.scopus.com/inward/record.url?scp=85181516534&partnerID=8YFLogxK

U2 - 10.1145/3612938

DO - 10.1145/3612938

M3 - Article

SN - 1942-3454

VL - 15

JO - ACM Transactions on Computation Theory

JF - ACM Transactions on Computation Theory

IS - 3-4

M1 - 8

ER -

Sparsification Lower Bounds for List H-Coloring

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this