TR02-053 Authors: Lars Engebretsen, Venkatesan Guruswami

Publication: 18th September 2002 09:48

Downloads: 608

Keywords:

By the breakthrough work of HÃ¥stad, several constraint satisfaction

problems are now known to have the following approximation resistance

property: satisfying more clauses than what picking a random

assignment would achieve is NP-hard. This is the case for example for

Max E3-Sat, Max E3-Lin and Max E4-Set Splitting. A notable exception

to this extreme hardness is constraint satisfaction over two variables

(2-CSP); as a corollary of the celebrated Goemans-Williamson

algorithm, we know that every Boolean 2-CSP has a non-trivial

approximation algorithm whose performance ratio is better than that

obtained by picking a random assignment to the variables. An

intriguing question then is whether this is also the case for 2-CSPs

over larger, non-Boolean domains. This question is still open, and is

equivalent to whether the generalization of Max 2-SAT to domains of

size d, can be approximated to a factor better than (1 - 1/d^2).

In an attempt to make progress towards this question, in this paper we

prove, firstly, that a slight restriction of this problem, namely a

generalization of linear inequations with two variables per

constraint, is not approximation resistant, and, secondly, that the

Not-All-Equal Sat problem over domain size d with three variables per

constraint, is approximation resistant, for every d >= 3. In the

Boolean case, Not-All-Equal Sat with three variables per constraint is

equivalent to Max 2-SAT and thus has a non-trivial approximation

algorithm; for larger domain sizes, Max 2-SAT can be reduced to

Not-All-Equal Sat with three variables per constraint. Our

approximation algorithm implies that a wide class of 2-CSPs called

regular 2-CSPs can all be approximated beyond their random assignment

threshold.