Covering CSPs

Abstract—We study the covering complexity of constraint satisfaction problems (CSPs). The covering number of a CSP instance C, denoted v(C), is the smallest number of assignments to the variables, such that each constraint is satisfied by at least one of the assignments. This covering notion describes situations in which we must satisfy all the constraints, and are willing to use more than one assignment to do so. At the same time, we want to minimize the number of assignments. We study the covering problem for different constraint predicates. We first observe that if the predicate contains an odd predicate, then it is covered by any assignment and its negation. In particular, 3CNF and 3LIN, that are hard in the max-CSP sense, are easy to cover. However, the covering problem is hard for predicates that do not contain an odd predicate: 1. For the 4LIN predicate, it is NP-hard to decide if a given instance C has v(C) at most 2, or v(C) is super-constant. 2. (a) We propose a framework of covering dictatorship tests. We design and analyze such a dictatorship test for every predicate that supports a pairwise independent distribution. (b) We introduce a covering unique games conjecture, and use it to convert the covering dictatorship tests into conditional hardness results. 3. Finally, we study a hypothesis about the hardness of covering random instances that is similar to Feige’s R3SAT hypothesis. We show the following somewhat surprising im-plication: If our hypothesis holds for dense enough instances, then it is hard to color an O(1)-colorable hypergraph with a polynomial number of colors. I