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 worstcase 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 kCSP, it is hard to find an assignment satisfying more than c0 k^2/2^k fraction of the constraints.
* Given a kuniform hypergraph, k >= 2, for all epsilon > 0, it is hard to tell if it is qstrongly colorable or has no independent set with an epsilon fraction of vertices, where q = ceiling[k + sqrt(k)  0.5].
* Given a kuniform hypergraph, k >= 3, for all epsilon > 0, it is hard to tell if it is (k1)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:14:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770446},
ISSN = {18688969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7553},
URN = {urn:nbn:de:0030drops75537},
doi = {10.4230/LIPIcs.APPROXRANDOM.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 