License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2016.14
URN: urn:nbn:de:0030-drops-58291
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5829/
Brakensiek, Joshua ;
Guruswami, Venkatesan
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*floor(t/3) - 1} (Garey and Johnson 1976; Khanna, Linial, Safra, 1993; Guruswami, Khanna, 2000). 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 = ceiling(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 (Austrin, Guruswami, Hastad, 2014), though interestingly our results are "PCP-free" in that they do not require any approximation gap in the starting Label Cover instance.
BibTeX - Entry
@InProceedings{brakensiek_et_al:LIPIcs:2016:5829,
author = {Joshua Brakensiek and Venkatesan Guruswami},
title = {{New Hardness Results for Graph and Hypergraph Colorings}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {14:1--14:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-008-8},
ISSN = {1868-8969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5829},
URN = {urn:nbn:de:0030-drops-58291},
doi = {10.4230/LIPIcs.CCC.2016.14},
annote = {Keywords: hardness of approximation, graph coloring, hypergraph coloring, polymor- phisms, combinatorics}
}
|
Keywords: |
|
hardness of approximation, graph coloring, hypergraph coloring, polymor- phisms, combinatorics |
|
Collection: |
|
31st Conference on Computational Complexity (CCC 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
19.05.2016 |
