Paper Info
Title
Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy.
Abstract
A classic result of Schaefer [STOC, 1978] classifies all constraint satisfaction problems (CSPs) over the Boolean domain to be either in P or NP-hard. This paper considers a promise-problem variant of CSPs called PCSPs. Many problems such as approximate graph and hypergraph coloring, the (2 + ∈)-SAT problem due to Austrin, Guruswami, and Håstad [SIAM Journal on Computing, 2017], and the digraph homomorphism problem can be placed in this framework. This paper is motivated by the pursuit of understanding the computational complexity of Boolean PCSPs, determining which PCSPs are polynomial-time tractable or NP-hard. As our main result, we show that PCSPs exhibits a dichotomy (it is either polynomial-time tractable or NP-hard) when the clauses are symmetric and allow for negations of variables. In particular, we show that every such polynomial-time tractable instance can be solved via either Gaussian elimination over F2 or a linear programming relaxation. We achieve our dichotomy theorem by extending the weak polymorphism framework of AGH which itself is a generalization of the algebraic approach used by polymorphisms to study CSPs. In >both the algorithm and hardness portions of our proof, we incorporate new ideas and techniques not utilized in the CSP case.
Year
DOI
Venue
2018
10.5555/3174304.3175422
SODA '18: Symposium on Discrete Algorithms New Orleans Louisiana January, 2018
Field
DocType
ISBN
Constraint satisfaction,Discrete mathematics,Combinatorics,Computer science,Hypergraph,Structure (category theory),Constraint satisfaction problem,Homomorphism,Linear programming relaxation,Boolean domain,Computational complexity theory
Conference
978-1-61197-503-1
Citations 
PageRank 
References 
1
0.36
0
Authors
2
Name
Order
Citations
PageRank
Joshua Brakensiek126.80
V. Guruswami23205247.96