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.APPROX-RANDOM.2017.4
URN: urn:nbn:de:0030-drops-75537
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7553/
Brakensiek, Joshua ;
Guruswami, Venkatesan
The Quest for Strong Inapproximability Results with Perfect Completeness
Abstract
The Unique Games Conjecture (UGC) has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect completeness inherent in the UGC. For the important case when the input CSP instance admits a satisfying assignment, it therefore remains wide open to understand how well it can be approximated.
This work is motivated by the pursuit of a better understanding of the inapproximability of perfectly satisfiable instances of CSPs. Our main conceptual contribution is the formulation of a (hypergraph) version of Label Cover which we call "V label cover." Assuming a conjecture concerning the inapproximability of V label cover on perfectly satisfiable instances, we prove the following implications:
* There is an absolute constant c0 such that for k >= 3, given a satisfiable instance of Boolean k-CSP, it is hard to find an assignment satisfying more than c0 k^2/2^k fraction of the constraints.
* Given a k-uniform hypergraph, k >= 2, for all epsilon > 0, it is hard to tell if it is q-strongly colorable or has no independent set with an epsilon fraction of vertices, where q = ceiling[k + sqrt(k) - 0.5].
* Given a k-uniform hypergraph, k >= 3, for all epsilon > 0, it is hard to tell if it is (k-1)-rainbow colorable or has no independent set with an epsilon fraction of vertices.
We further supplement the above results with a proof that an ``almost Unique'' version of Label Cover can be approximated within a constant factor on satisfiable instances.
BibTeX - Entry
@InProceedings{brakensiek_et_al:LIPIcs:2017:7553,
author = {Joshua Brakensiek and Venkatesan Guruswami},
title = {{The Quest for Strong Inapproximability Results with Perfect Completeness}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {4:1--4:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-044-6},
ISSN = {1868-8969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7553},
URN = {urn:nbn:de:0030-drops-75537},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.4},
annote = {Keywords: inapproximability, hardness of approximation, dictatorship testing, constraint satisfaction, hypergraph coloring}
}
|
Keywords: |
|
inapproximability, hardness of approximation, dictatorship testing, constraint satisfaction, hypergraph coloring |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
11.08.2017 |
