Paper Info
Title
New hardness results for graph and hypergraph colorings.
Abstract
Finding a proper coloring of a t-colorable graph G with t colors is a classic NP-hard problem when t ≥ 3. In this work, we investigate the approximate coloring problem in which the objective is to find a proper c-coloring of G where c ≥ t. We show that for all t ≥ 3, it is NP-hard to find a c-coloring when c ≤ 2t - 2. In the regime where t is small, this improves, via a unified approach, the previously best known hardness result of c ≤ max{2t - 5, t + 2⌊t/3⌋ - 1} [9, 21, 13]. For example, we show that 6-coloring a 4-colorable graph is NP-hard, improving on the NP-hardness of 5-coloring a 4-colorable graph. We also generalize this to related problems on the strong coloring of hypergraphs. A k-uniform hypergraph H is t-strong colorable (where t ≥ k) if there is a t-coloring of the vertices such that no two vertices in each hyperedge of H have the same color. We show that if t = ⌈3k/2⌉, then it is NP-hard to find a 2-coloring of the vertices of H such that no hyperedge is monochromatic. We conjecture that a similar hardness holds for t = k + 1. We establish the NP-hardness of these problems by reducing from the hardness of the Label Cover problem, via a \"dictatorship test\" gadget graph. By combinatorially classifying all possible colorings of this graph, we can infer labels to provide to the label cover problem. This approach generalizes the \"weak polymorphism\" framework of [3], though interestingly our results are \"PCP-free\" in that they do not require any approximation gap in the starting Label Cover instance.
Year
DOI
Venue
2016
10.4230/LIPIcs.CCC.2016.14
Electronic Colloquium on Computational Complexity (ECCC)
Keywords
DocType
Volume
hardness of approximation,graph coloring,hypergraph coloring,polymorphisms,combinatorics
Conference
23
ISSN
Citations 
PageRank 
1868-8969
0
0.34
References 
Authors
12
2
Name
Order
Citations
PageRank
Joshua Brakensiek126.80
V. Guruswami23205247.96