Abstract
Constraint satisfaction problems (CSPs) are ubiquitous in theoretical computer science. We study the problem of StrongCSP s, i.e. instances where a large induced subinstance has a satisfying assignment. More formally, given a CSP instance 𝒢(V, E, [k], {Π_{ij}}_{(i,j) ∈ E}) consisting of a set of vertices V, a set of edges E, alphabet [k], a constraint Π_{ij} ⊂ [k] × [k] for each (i,j) ∈ E, the goal of this problem is to compute the largest subset S ⊆ V such that the instance induced on S has an assignment that satisfies all the constraints.
In this paper, we study approximation algorithms for UniqueGames and related problems under the StrongCSP framework when the underlying constraint graph satisfies mild expansion properties. In particular, we show that given a StrongUniqueGames instance whose optimal solution S^* is supported on a regular low threshold rank graph, there exists an algorithm that runs in time exponential in the threshold rank, and recovers a large satisfiable subinstance whose size is independent on the label set size and maximum degree of the graph. Our algorithm combines the techniques of BarakRaghavendraSteurer (FOCS'11), GuruswamiSinop (FOCS'11) with several new ideas and runs in time exponential in the threshold rank of the optimal set. A key component of our algorithm is a new threshold rank based spectral decomposition, which is used to compute a "large" induced subgraph of "small" threshold rank; our techniques build on the work of Oveis Gharan and Rezaei (SODA'17), and could be of independent interest.
BibTeX  Entry
@InProceedings{ghoshal_et_al:LIPIcs.APPROX/RANDOM.2022.43,
author = {Ghoshal, Suprovat and Louis, Anand},
title = {{Approximating CSPs with Outliers}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {43:143:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772495},
ISSN = {18688969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17165},
URN = {urn:nbn:de:0030drops171656},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.43},
annote = {Keywords: Constraint Satisfaction Problems, Strong Unique Games, Threshold Rank}
}
Keywords: 

Constraint Satisfaction Problems, Strong Unique Games, Threshold Rank 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) 
Issue Date: 

2022 
Date of publication: 

15.09.2022 