On the hardness of losing weight
Andrei Krokhin1 and Dániel Marx2

arXiv:1711.03894v1 [] 10 Nov 2017

1

2

Department of Computer Science, Durham University, Durham, DH1 3LE, UK
andrei.krokhin@durham.ac.uk
Department of Computer Science and Information Theory, Budapest University of
Technology and Economics, H-1521 Budapest, Hungary
dmarx@cs.bme.hu

Abstract. We study the complexity of local search for the Boolean constraint satisfaction problem (CSP), in the following form: given a CSP
instance, that is, a collection of constraints, and a solution to it, the
question is whether there is a better (lighter, i.e., having strictly less
Hamming weight) solution within a given distance from the initial solution. We classify the complexity, both classical and parameterized, of
such problems by a Schaefer-style dichotomy result, that is, with a restricted set of allowed types of constraints. Our results show that there
is a considerable amount of such problems that are NP-hard, but fixedparameter tractable when parameterized by the distance.

1

Introduction

Local search is one of the most widely used approaches to solving hard optimization problems. The basic idea of local search is that one tries to iteratively improve a current solution by searching for better solutions in its (k-)neighborhood
(i.e., within distance k from it). Any optimization algorithm can be followed by
a local search phase, thus the problem of finding a better solution locally is of
great practical interest. However, a brute force search of a k-neighborhood is not
feasible for large k, thus it is natural to study the complexity of searching the
k-neighborhood.
The constraint satisfaction problem (CSP) provides a framework in which it
is possible to express, in a natural way, many combinatorial problems encountered in artificial intelligence and computer science. A constraint satisfaction
problem is represented by a set of variables, a domain of values for each variable, and a set of constraints between variables. The basic aim in a constraint
satisfaction problem is then to find an assignment of values to the variables that
satisfies the constraints. Boolean CSP (when all variables have domain {0, 1}),
aka generalized satisfiability, is a natural generalization of Sat where constraints
are given by arbitrary relations, not necessarily by clauses. Local search methods
for Sat and CSP are very extensively studied (see, e.g., [5,9,10,11]).
Complexity classifications for various versions of CSP (and, in particular,
for versions of Boolean CSP) have recently attracted massive attention from
researchers, and one of the most popular directions here is to characterise restrictions on the type of constraints that lead to problems with lower complexity

in comparison with the general case (see [2,3]). Such classifications are sometimes
called Schaefer-style because the first classification of this type was obtained by
T.J. Schaefer in his seminal work [16]. A local-search related Schaefer-style classification for Boolean Max CSP was obtained in [1], in the context of local
search complexity classes such as PLS.
The hardness of searching the k-neighborhood (for any optimisation problem)
can be studied very naturally in the framework of parameterized complexity [6,8],
as suggested in [7]; such a study for the traveling salesman problem (TSP) was recently performed in [14]. Parameterized complexity studies hardness in finer detail than classical complexity. Consider, for example, two standard NP-complete
problems Minimum Vertex Cover and Maximum Clique. Both have the
natural parameter k: the size of the required vertex cover/clique. Both problems
can be solved in nO(k) time by complete enumeration. Notice that the degree of
the polynomial grows with k, so the algorithm becomes useless for large graphs,
even if k is as small as 10. However, Minimum Vertex Cover can be solved
in time O(2k · n2 ) [6,8]. In other words, for every fixed cover size there is a
polynomial-time (in this case, quadratic) algorithm solving the problem where
the degree of the polynomial is independent of the parameter. Problems with this
property are called fixed-parameter tractable. The notion of W[1]-hardness in
parameterized complexity is analogous to NP-completeness in classical complexity. Problems that are shown to be W[1]-hard, such as Maximum Clique [6,8],
are very unlikely to be fixed-parameter tractable. A Schaefer-style classification
of the basic Boolean CSP with respect to parameterized complexity (where the
parameter is the required Hamming weight of the solution) was obtained in [13].
In this paper, we give a Schaefer-style complexity classification for the following problem: given a collection of Boolean constraints, and a solution to it, the
question is whether there is a better (i.e., with smaller Hamming weight) solution
within a given (Hamming) distance k from the initial solution. We obtain classification results both for classical (Theorem 9) and for parameterized complexity
(Theorem 3). However, we would like to point out that it makes much more sense
to study this problem in the parameterized setting. Intuitively, if we are able to
decide in polynomial time whether there is a better solution within distance k,
then this seems to be almost as powerful as finding the best solution (although
there are technicalities such as whether there is a feasible solution at all). Our
classification confirms this intuition: searching the k-neighborhood is polynomialtime solvable only in cases where finding the optimum is also polynomial-time
solvable. On the other hand, there are cases (for example, Horn constraints or
1-in-3 Sat) where the problem of finding the optimum is NP-hard, but searching the k-neighborhood is fixed-parameter tractable. This suggests evidence that
parameterized complexity is the right setting for studying local search.
The paper is organized as follows. Section 2 reviews basic notions of parameterized complexity and Boolean CSP. Section 3 presents the classificiation with
respect to fixed-parameter tractability, while Section 4 deals with polynomialtime solvability. The proofs omitted from Section 4 can be found in the appendix.
2

2

Preliminaries

Boolean CSP. A formula φ is a pair (V, C) consisting of a set V of variables
and a set C of constraints. Each constraint ci ∈ C is a pair hsi , Ri i, where si =
(xi,1 , . . . , xi,ri ) is an ri -tuple of variables (the constraint scope) and Ri ⊆ {0, 1}ri
is an ri -ary Boolean relation (the constraint relation). A function f : V → {0, 1}
is a satisfying assignment of φ if (f (xi,1 ), . . . , f (xi,ri )) is in Ri for every ci ∈ C.
Let Γ be a set of Boolean relations. A formula is a Γ -formula if every constraint
relation Ri is in Γ . In this paper, Γ is always a finite set. The (Hamming) weight
w(f ) of assignment f is the number of variables x with f (x) = 1. The distance
dist(f1 , f2 ) of assignments f1 , f2 is the number of variables x with f1 (x) 6= f2 (x).
We recall various standard definitions concerning Boolean constraints (cf. [3]):
– R is 0-valid if (0, . . . , 0) ∈ R.
– R is 1-valid if (1, . . . , 1) ∈ R.
– R is Horn or weakly negative if it can be expressed as a conjunction of clauses
such that each clause contains at most one positive literal. It is known that R
is Horn if and only if it is min-closed: if (a1 , . . . , ar ) ∈ R and (b1 , . . . , br ) ∈ R,
then (min(a1 , b1 ), . . . , min(ar , br )) ∈ R.
– R is affine if it can be expressed as a conjunction of constraints of the form
x1 +x2 +· · ·+xt = b, where b ∈ {0, 1} and addition is modulo 2. The number
of tuples in an affine relation is always an integer power of 2.
– R is width-2 affine if it can be expressed as a conjunction of constraints of
the form x = y and x 6= y.
– R is IHS-B− (or implicative hitting set bounded) if it can be represented by
a conjunction of clauses of the form (x), (x → y) and (¬x1 ∨ . . . ¬xn ), n ≥ 1.
– The relation Rp-in-q (for 1 ≤ p ≤ q) has arity q and Rp-in-q (x1 , . . . , xq ) is true
if and only if exactly p of the variables x1 , . . . , xq have value 1.
The following definition is new in this paper. It plays a crucial role in characterizing the fixed-parameter tractable cases for local search.
Definition 1. Let R be a Boolean relation and (a1 , . . . , ar ) ∈ R. A set S ⊆
{1, . . . , r} is a flip set of (a1 , . . . , ar ) (with respect to R) if (b1 , . . . , br ) ∈ R
where bi = 1 − ai for i ∈ S and bi = ai for i 6∈ S. We say that R is flip separable
if whenever some (a1 , . . . , ar ) ∈ R has two flip sets S1 , S2 with S1 ⊂ S2 , then
S2 \ S1 is also a flip set for (a1 , . . . , ar ).
It is easy to see that R1-in-3 is flip separable: every flip set has size exactly 2,
hence S1 ⊂ S2 is not possible. Moreover, Rp-in-q is also flip separable for every
p ≤ q. Affine constraints are also flip separable: to see this, it is sufficient to
verify the definition only for the constraint x1 + · · · + xr = 0.
The basic problem in CSP is to decide if a formula has a satisfying assignment:
CSP(Γ )
Input: A Γ -formula φ.
Question: Does φ have a satisfying assignment?
3

Schaefer completely characterized the complexity of CSP(Γ ) for every finite
set Γ of Boolean relations [16]. In particular, every such problem is either in
PTIME or NP-complete, and there is a very clear description of the boundary
between the two cases.
Optimization versions of Boolean CSP were investigated in [3,4]. A straightforward way to obtain an optimization problem is to relax the requirement that
every constraint is satisfied, and ask for an assignment maximizing the number
of satisfied constraints. Another possibility is to ask for a solution with minimum/maximum weight. In this paper, we investigate the problem of minimizing
the weight. As we do not consider the approximability the problem, we define
here only the decision version:
Min-Ones(Γ )
Input: A Γ -formula φ and an integer W .
Question: Does φ have a satisfying assignment f with w(f ) ≤ W ?
The characterization of the approximability of finding a minimum weight
satisfying assignment for a Γ -formula can be found in [3]. Here we state only the
classification of polynomial-time solvable and NP-hard cases:
Theorem 2 ([3]). Let Γ be a finite set of Boolean relations. Min-Ones(Γ ) is
solvable in polynomial time if one the following holds, and NP-complete otherwise:
– Every R ∈ Γ is 0-valid.
– Every R ∈ Γ is Horn.
– Every R ∈ Γ is width-2 affine.
A Schaefer-style characterization of the approximability of finding two satisfying assignments to a formula with a largest distance between them was obtained in [4], motivated by the blocks world problem from KR, while a Schaeferstyle classification of the problem of deciding whether a given satisfying assignment to a given CSP instance is component-wise minimal was presented in [12],
motivated by the circumscription formalism from AI.
The main focus of the paper is the local search version of minimizing weight:
LS-CSP(Γ )
Input: A Γ -formula φ, a satisfying assignment f , and an integer k.
Question: Does φ have a satisfying assignment f ′ with w(f ′ ) < w(f )
and dist(f, f ′ ) ≤ k?
LS in the above problem stands for both “local search” and “lighter solution.”
Observe that the satisfying assignments of an (x ∨ y)-formula correspond to
the vertex covers of the graph where the variables are the vertices and the edges
are the constraints. Thus LS-CSP({x ∨ y}) is the problem of reducing the size
of a (given) vertex cover by including and excluding a total of at most k vertices.
4

As we shall see (Lemma 7), this problem is W[1]-hard, even for bipartite graphs.
This might be of independent interest.
Parameterized complexity. In a parmeterized problem, each instance contains an integer k called the parameter. A parameterized problem is fixed-parameter tractable (FPT) if can be solved by an algorithm with running time f (k)·nc ,
where n is the length of the input, f is an arbitrary (computable) function depending only on k, and c is a constant independent of k.
A large fraction of NP-complete problems is known to be FPT. On the other
hand, analogously to NP-completeness in classical complexity, the theory of
W[1]-hardness can be used to give strong evidence that certain problems are
unlikely to be fixed-parameter tractable. We omit the somewhat technical definition of the complexity class W[1], see [6,8] for details. Here it will be sufficient
to know that there are many problems, including Maximum Clique, that were
proved to be W[1]-hard. To prove that a parameterized problem is W[1]-hard,
we have to present a parameterized reduction from a known W[1]-hard problem.
A parameterized reduction from problem L1 to problem L2 is a function that
transforms a problem instance x of L1 with parameter k into a problem instance
x′ of L2 with parameter k ′ in such a way that
– x′ is a yes-instance of L2 if and only if x is a yes-instance of L1 ,
– k ′ can be bounded by a function of k, and
– the transformation can be computed in time f (k) · |x|c for some constant c
and function f (k).
It is easy to see that if there is a parameterized reduction from L1 to L2 , and
L2 is FPT, then it follows that L1 is FPT as well.

3

Characterizing fixed-parameter tractability

In this section, we completely characterize those finite sets Γ of Boolean relations
for which LS-CSP(Γ ) is fixed-parameter tractable.
Theorem 3. Let Γ be a finite set of Boolean relations. The problem LS-CSP(Γ )
is in FPT if every relation in Γ is Horn or every relation in Γ is flip separable.
In all other cases, LS-CSP(Γ ) is W[1]-hard.
First we handle the fixed-parameter tractable cases (Lemmas 4 and 6)
Lemma 4. If every R ∈ Γ is Horn, then LS-CSP(Γ ) is FPT.
Proof. Observe that if there is a solution f ′ , then we can assume that f ′ (x) ≤
f (x) for every variable x: by defining f ′′ (x) := min{f (x), f ′ (x)}, we get that f ′′
is also satisfying (as every R ∈ Γ is min-closed) and dist(f ′′ , f ) ≤ dist(f ′ , f ).
Thus we can restrict our search to solutions that can be obtained from f by
changing some 1’s to 0’s, but every 0 remains unchanged.
Since w(f ′ ) < w(f ), there is a variable x with f (x) = 1 and f ′ (x) = 0. For
every variable x with f (x) = 1, we try to find a solution f ′ with f ′ (x) = 0 using
5

a simple bounded-height search tree algorithm. For a particular x, we proceed as
follows. We start with initial assignment f . Change the value of x to 0. If there is
a constraint h(x1 , . . . , xr ), Ri that is not satisfied by the new assignment, then we
select one of the variables x1 , . . . , xr that has value 1, and change it to 0. Thus
at this point we branch into at most r directions. If the assignment is still not
satisfying, the we branch again on the variables of some unsatisfied constraint.
The branching factor of the resulting search tree is at most rmax , where rmax is
the maximum arity of the relations in Γ . By the observation above, if there is a
solution, then we find a solution on the first k levels of the search tree. Therefore,
k+1
we can stop the search on the k-th level, implying that we visit at most rmax
nodes of the search tree. The work to be done at each node is polynomial in the
k+1
size n of the input, hence the total running time is rmax
· nO(1) .
⊓
⊔
If every R ∈ Γ is not only Horn, but IHS-B− (which is a subset of Horn), then
the algorithm of Lemma 4 actually runs in polynomial time:
Corollary 5. If every R ∈ Γ is IHS-B−, then LS-CSP(Γ ) is in PTIME.
Proof. We can assume that every constraint is either (x), (x → y), or (x̄1 ∨ · · · ∨
x̄r ). If a constraint (x̄1 ∨ · · · ∨ x̄r ) is satisfied in the initial assignment f , then it
remains satisfied after changing some 1’s to 0. Observe that if a constraint (x) or
(x → y) is not satisfied, then at most one variable has the value 1. Thus there is
no branching involved in the algorithm of Lemma 4, making it a polynomial-time
algorithm.
⊓
⊔
For flip separable relations, we give a very similar branching algorithm. However, in this case the correctness of the algorithm requires a nontrivial argument.
Lemma 6. If every R ∈ Γ is flip separable, then LS-CSP(Γ ) is FPT.
Proof. Let (φ, f, k) be an instance of LS-CSP(Γ ). If w(f ′ ) < w(f ) for some
assignment f ′ , there is a variable x with f (x) = 1 and f ′ (x) = 0. For every
variable x with f (x) = 1, we try to find a solution f ′ with f ′ (x) = 0 using
a simple bounded-height search tree algorithm. For each such x, we proceed
as follows. We start with the initial assignment f and set the value of x to 0.
Iteratively do the following: (a) if there is a constraint in φ that is not satisfied
by the current assignment and such that the value of some variable in it has not
been flipped yet (on this branch), then we select one of such variables, and flip
its value; (b) if there is no such constraint, but the current assignment is not
satisfying then we move to the next branch; (c) if every constraint is satisfied,
then either we found a required solution or else we move to the next branch. If
a required solution is not found on the first k levels of the search tree then the
algorithm reports that there is no required solution.
Assume that (φ, f, k) is a yes-instance. We claim that if f ′ is a required
solution with minimal distance from f , then some branch of the algorithm finds
it. Let X be the set of variables on which f and f ′ differ, so |X| ≤ k. We now show
that on the first k levels of the search tree, the algorithm finds some satisfying
6

assignment f0 (possibly heavier than f ) that differs from f only on a subset
X0 ⊆ X of variables. To see this, assume that at some node of the search tree,
the current assignment differs from the initial assignment only on a subset of X;
we show that this remains true for at least one child of the node. If we branch
on the variables (x1 , . . . , xr ) of an unsatisfied constraint, then at least one of its
variables, say xi , has a value different from f ′ (as f ′ is a satisfying assignment).
It follows that xi ∈ X: otherwise the current value of xi is f (xi ) (since so far
we changed variables only in X) and f (xi ) = f ′ (xi ) (by the definition of X),
contradicting the fact that current value of xi is different from f (xi ). Thus if we
change variable xi , it remains true that only variables from X are changed. Since
|X| ≤ k, this branch of the algorithm has to find some satisfying assignment f0 .
If w(f0 ) < w(f ), then, by the choice of f ′ , we must have f0 = f ′ . Otherwise,
let X0 ⊆ X be the set of variables where f and f0 differ and let f ′′ be the
assignment that differs from f exactly on the variables X \X0 . From the fact that
every constraint is flip separable, it follows that f ′′ is a satisfying assignment.
We claim that w(f ′′ ) < w(f ). Indeed, if changing the values of the variables in X
decreases the weight and changing the values in X0 does not decrease the weight,
then the set X \ X0 has to decrease the weight. This contradicts the assumption
that f ′ is a solution whose distance from f is minimal: f ′′ is a solution with
distance |X \ X0 | < |X|. Thus it is sufficient to investigate only the first k levels
of the search tree. As in the proof of Lemma 4, the branching factor of the tree
k+1
is at most rmax , and the algorithm runs in time rmax
· nO(1) .
⊓
⊔
All the hardness proofs in this section are based on the following lemma:
Lemma 7. LS-CSP({x ∨ y}) is W[1]-hard.
Proof. The proof is by reduction from a variant of Maximum Clique: given a
graph G(V, E) with a distinguished vertex x and an integer t, we have to decide
whether G has a clique of size t that contains x. It is easy to see that this problem
is W[1]-hard. Furthermore, it can be assumed that t is odd. Let n be the number
of vertices of G and let m be the number of edges. We construct a formula φ on
m + n(t − 1)/2 − 1 variables and a satisfying assignment f such that G has a
clique of size t containing x if and only if φ has a satisfying assignment f ′ with
w(f ′ ) < w(f ) and distance at most k := t(t − 1) − 1 from f .
Let d = (t − 1)/2 (note that t is odd). The formula φ has d variables v1 ,
. . . , vd for each vertex v 6= x of G and a variable ue for each edge e of G. The
distinguished vertex x has only d − 1 variables x1 , . . . , xd−1 . If a vertex v is the
endpoint of an edge e, then for every 1 ≤ i ≤ d (or 1 ≤ i ≤ d − 1, if v = x), we
add the constraint ue ∨ vi . Thus each variable ue is in 2d − 1 or 2d constraints
(depending on whether x is the endpoint of e or not). Set f (ue ) = 1 for every
e ∈ E and f (vi ) = 0 for every v ∈ V , 1 ≤ i ≤ d. Clearly, f is a satisfying
assignment.
Assume that G has a clique K of size t that includes x. Set f ′ (vi ) = 1 for
every v ∈ K (1 ≤ i ≤ d) and set f ′ (ue ) = 0 for every edge e in K; let f ′ be the
same as f on every other variable. Observe that f ′ is also a satisfying assignment:
if a variable ue was changed to 0 and there is a constraint ue ∨ vi , then v ∈ K
7

and hence f ′ (vi ) = 1. We have w(f ′ ) < w(f ): dt − 1 variables were changed to
1 (note that x ∈ K) and t(t − 1)/2 = dk variables were changed to 0. Moreover,
the distance of f and f ′ is exactly dt − 1 + t(t − 1)/2 = t(t − 1) − 1 = k.
Assume now that f ′ satisfies the requirements. Let K be the set of those
vertices v in G for which f ′ (vi ) = 1 for every i. We claim that K is a clique of size
t in G. Observe that there are at least d|K| − 1 variables vi with f ′ (vi ) > f (vi )
and f ′ (ue ) < f (ue ) is possible only if both endpoints of e are in K, i.e., e
is in the set E(K) of edges in K. Thus w(f ′ ) < w(f ) implies d|K| − 1 <
|E(K)| ≤ |K|(|K| − 1)/2, which is only possible if |K| ≥ t. If |K| > t, then
f ′ (vi ) > f (vi ) for at least (t + 1)d − 1 variables, hence there must be at least
that many variables ue with f ′ (ue ) < f (ue ). Thus the distance of f and f ′ is at
least 2(t + 1)d − 2 > t(t − 1) − 1. Therefore, we can assume |K| = t. Now dt − 1 <
|E(K)| ≤ |K|(|K| − 1)/2 = t(t − 1)/2 is only possible if |E(K)| = t(t − 1)/2
(i.e., K is a clique) and it follows that there are exactly dt − 1 variables vi with
f ′ (vi ) > f (vi ) (i.e., x ∈ K).
⊓
⊔
Now we are ready to present the main hardness proof of the section:
Lemma 8. If Γ contains a relation R1 that is not Horn and a relation R2 that
is not flip separable, then LS-CSP(Γ ) is W[1]-hard.
Proof. The proof is by reduction from LS-CSP({x ∨ y}). Let (phi1 , f1 , k) be
an instance of LS-CSP({x ∨ y}), i.e., every constraint relation in formula φ1 =
(V, C) is (x ∨ y). Since R1 is not min-closed, we can assume (by permuting the
variables) that for some r1 , r2 ≥ 1, r3 , r4 ≥ 0, if we define
r1

r2

r3

r4

z }| { z }| { z }| { z }| {
R1′ (x, y, w0 , w1 ) = R1 (x, . . . , x, y, . . . , y, w0 , . . . , w0 , w1 , . . . , w1 ),
then (0, 1, 0, 1), (1, 0, 0, 1) ∈ R1′ , but (0, 0, 0, 1) 6∈ R1′ . Since R1′ is obtained from
R1 by identifying variables, we can use the relation R1′ when specifying instances
of LS-CSP(Γ ). We consider two cases:
Case 1: (1, 1, 0, 1) ∈ R1′ . In this case R1′ (x, y, 0, 1) = x ∨ y, hence it is
easy to simulate LS-CSP({x ∨ y}). The only difficulty is how to simulate the
constants 0 and 1. We do this as follows. Let us construct a formula φ2 that
has every variable of V and new variables q0j , q1j for every 1 ≤ j ≤ k + 1 (these
new variables will play the role of the constants). We define assignment f2 of
φ2 by setting f2 (x) = f1 (x) for x ∈ V and f2 (q0j ) = 0 and f2 (q1j ) = 1 for
1 ≤ j ≤ k + 1. For 1 ≤ a, b, c ≤ k + 1, we add constraint c1a,b,c = R1′ (q1a , q0b , q0b , q1c ),
it is clearly satisfied by assignment f2 . To simulate a constraint x ∨ y, we add
c2x,y,j = R1′ (x, y, q0j , q11 ) for every 1 ≤ j ≤ k + 1.
It is easy to see that if there is a solution f1′ for the original instance (φ1 , f1 , k),
then by setting f2′ (x) = f1′ (x) for every x ∈ V and f2′ (q0j ) = 0, f2′ (q1j ) = 1 for
every 1 ≤ j ≤ k + 1 gives a solution f2′ for the constructed instance (φ2 , f2 , k).
We claim the converse is also true: if f2′ is a solution for the instance (φ2 , f2 , k),
then the restriction of f2′ to V gives a solution for (φ1 , f1 , k). Since the distance
of f2 and f2′ is at most k, there are 1 ≤ b, c ≤ k + 1 with f2′ (q0b ) = 0 and
f2′ (q1c ) = 1. Because of the constraint c1a,b,c , we have that f2′ (q1a ) = 1 for every
8

1 ≤ a ≤ k + 1. It follows that f2′ restricted V is a satisfying assignment of
φ1 : for every constraint x ∨ y ∈ C, the constraint c2x,y,b prevents the possibility
f2′ (x) = f2′ (y) = 0. We have seen that f2′ (q0j ) ≥ f2 (q0j ) and f2′ (q1j ) ≥ f2 (q1j ) for
every 1 ≤ j ≤ k + 1. Now w(f2′ ) < w(f2 ) implies that the weight of f2′ on V has
to be less than the weight of f2 on V . Thus w(f1′ ) < w(f1 ).
Case 2: (1, 1, 0, 1) 6∈ R1′ , which means that R1′ (x, y, 0, 1) is x 6= y. In this case
we have to rely on the fact that R2 is not flip separable to simulate the constraint
x ∨ y. We construct formula φ2 and its satisfying assignment f2 as follows. Each
variable x is replaced by 3 variables x1 , x2 , x3 . We set f2 (x1 ) = f2 (x2 ) = f1 (x)
and f2 (x3 ) = 1 − f1 (x). Furthermore, for 1 ≤ j ≤ 3k + 1, we add the variables
q0j and q1j and set f2 (q0j ) = 0 and f2 (q1j ) = 1.
For every 1 ≤ a, b, c ≤ 3k + 1, we add the constraint c1a,b,c = R1′ (q1a , q0b , q0b , q1c ),
as in the previous case. For every x ∈ V , 1 ≤ j ≤ 3k + 1, and ℓ = 1, 2, we
add c2x,ℓ,j = R1′ (xℓ , x3 , q0j , q11 ), as we shall see, the role of these constraints is to
ensure f2′ (x1 ) = f2′ (x2 ) 6= f2′ (x3 ).
Since R2 is not flip separable, there is a tuple (s1 , . . . , sr ) ∈ R2 that has flip
sets S1 ⊂ S2 , but S2 \ S1 is not a flip set. For every constraint x ∨ y of φ1 , we
add 3k + 1 constraints to φ2 as follows. First, for 1 ≤ i ≤ r and 1 ≤ j ≤ 3k + 1,
we define variable vij as

x1 if i ∈ S1 and si = 0,





x3 if i ∈ S1 and si = 1,



y
if i ∈ S2 \ S1 and si = 1,
1
vij =
y3 if i ∈ S2 \ S1 and si = 0,





q11 if i 6∈ S2 and si = 1,


 j
q0 if i 6∈ S2 and si = 0.
For every 1 ≤ j ≤ 3k + 1, we add the constraint c3x,y,j = R2 (v1j , . . . , vrj ). For
example, assume that (0, 1, 0, 1) ∈ R2 and this tuple has flip sets S1 = {1, 2}
and S2 = {1, 2, 3, 4}, but S2 \ S1 = {3, 4} is not a flip set. This means that
(0, 1, 0, 1), (1, 0, 1, 0), (1, 0, 0, 1) ∈ R2 and (0, 1, 1, 0) 6∈ R2 . In this case, constraint
c3x,y,j is R2 (x1 , x3 , y3 , y1 ). Assuming f (x1 ) 6= f (x3 ) and f (y1 ) 6= f (y3 ), any
combination of values on x1 and y1 satisfies the constraint, except if f (x1 ) =
f (y1 ) = 0. Thus the constraint effectively acts as a constraint x1 ∨ y1 .
Finally, we set the maximum allowed distance to k ′ := 3k. This completes
the description of the constructed instance (φ2 , f2 , k ′ ).
Assume first that f1′ is a solution for the instance (φ1 , f1 , k). Define f2′ (x1 ) =
′
f2 (x2 ) = f1′ (x) and f2′ (x3 ) = 1 − f1′ (x) for every x ∈ V , and define f2′ (q0j ) = 0,
f2′ (q1j ) = 1 for every 1 ≤ j ≤ 3k + 1. The fact w(f1′ ) < w(f1 ) implies w(f2′ ) <
w(f2 ). Furthermore, the distance of f2 and f2′ is exactly three times the distance
of f1 and f1′ , i.e., at most 3k. We claim that f2′ satisfies the constraints of φ2 .
This is easy to see for c1a,b,c and c2x,ℓ,j . For c3x,y,j , this can be seen as follows:
– If f2′ (x) = 0, f2′ (y) = 1, then because (s1 , . . . , sr ) ∈ R2 .
– If f2′ (x) = 1, f2′ (y) = 0, then because S2 is a flip set.
9

– If f2′ (x) = 1, f2′ (y) = 1, then because S1 is a flip set.
For the other direction, assume that f2′ is a solution for instance (φ2 , f2 , k ′ ).
Define f1′ (x) = f2′ (x1 ) for every x ∈ V ; we claim that f1′ is a solution for instance
(φ1 , f1 , k). Since the distance of f2 and f2′ is at most 3k, there are 1 ≤ b, c ≤ 3k+1
with f2′ (q0b ) = 0 and f2′ (q1c ) = 1. Because of the constraint c1a,b,c , we have that
f2′ (q1a ) = 1 for every 1 ≤ a ≤ 3k + 1. The constraints c2x,1,b and c2x,2,b ensure
that f2′ (x1 ) = f2′ (x2 ) = 1 − f2′ (x3 ) (since (0, 0, 0, 1) 6∈ R1′ and (1, 1, 0, 1) 6∈ R1′ ).
It follows that the distance of f1 and f1′ is at most k: f1 (x) 6= f1′ (x) implies
f2 (xℓ ) 6= f2′ (xℓ ) for ℓ = 1, 2, 3, hence this can hold for at most k different
x ∈ V . Moreover, w(f1′ ) < w(f1 ): this follows from the facts w(f2′ ) < w(f2 ) and
f2′ (q0j ) ≥ f2 (q0k ), f2′ (q1j ) ≥ f2 (q1k ) (1 ≤ j ≤ 3k + 1).
We claim that every constraint x ∨ y of φ1 is satisfied. Assume that f1′ (x) =
′
f1 (y) = f2′ (x1 ) = f2′ (y1 ) = 0. Now c3x,y,b is not satisfied: this follows from the
fact that S2 \ S1 is not a flip set for (s1 , . . . , sr ) (with respect to R2 ).
⊓
⊔

4

Characterizing polynomial-time solvability

In this section, we completely characterize those finite sets Γ of Boolean relations
for which LS-CSP(Γ ) is polynomial-time solvable.
Theorem 9. Let Γ be a finite set of Boolean relations. The problem LS-CSP(Γ )
is in PTIME if every relation in Γ is IHS-B− or every relation in Γ is width-2
affine. In all other cases, LS-CSP(Γ ) is NP-hard.
Proof. If every relation in Γ is IHS-B−, then Corollary 5 gives a polynomialtime algorithm. If every relation in Γ is width-2 affine then the following simple
algorithm solves LS-CSP(Γ ): for a given instance (φ, f, k), compute the graph
whose vertices are the variables in φ and two vertices are connected if there is
a constraint in φ imposed on them. If there is a connected component of this
graph which has at most k vertices and such that f assigns more 1’s in this
component than it does 0’s, then flipping the values in this component gives a
required lighter solution. If such a component does not exists, then there is no
lighter solution within distance k from f .
By Lemma 8, if Γ contains a relation that is not Horn and a relation that is
not flip separable then LS-CSP(Γ ) is NP-hard. (Note that the proof is actually a
polynomial-time reduction from an NP-hard problem.) Therefore, we can assume
that every relation in Γ is Horn or every relation in Γ is flip separable. We now
give the proof for the former case, while the proof for the latter case can be
found in Appendix.
Assume now that Γ is Horn, and there is a relation R ∈ Γ that is not IHS-B−.
We prove that LS-CSP({R}) is NP-hard. It is shown in the proof of Lemma 5.27
of [3] that then R is at least ternary and one can permute the coordinates in R
and then substitute 0 and 1 in R in such a way that that the ternary relation
R′ (x, y, z) = R(x, y, z, 0, . . . , 0, 1, . . . , 1) has the following properties:
1. R′ contains tuples (1, 1, 1), (0, 1, 0), (1, 0, 0), (0, 0, 0), and
10

2. R′ does not contain the tuple (1, 1, 0).
Note that if (0, 0, 1) ∈ R′ then R′ (x, x, y) is x → y. If (0, 0, 1) 6∈ R′ then,
since R (and hence R′ ) is Horn (i.e., min-closed), at least one of of the tuples
(1, 0, 1) and (0, 1, 1) is not in R′ . Then it is easy to check that at least one of
the relations R′ (x, y, x) and R′ (y, x, x) is x → y. Hence, we can use constraints
of the form x → y when specifying instances of LS-CSP({R′ }).
We reduce Minimum Dominating Set to LS-CSP({R′ }). Let G(V, E) be
a graph with n vertices and m edges where a dominating set of size at most t
has to be found. Let v1 , . . . , vn be the vertices of G. Let S = 3m. We construct
a formula with nS + 2m + 1 variables as follows:
– There is a special variable x.
– For every 1 ≤ i ≤ n, there are S variables xi,1 , . . . , xi,S . There is a constraint
xi,j → xi,j ′ for every 1 ≤ j, j ′ ≤ n.
– For every 1 ≤ i ≤ n, if vs1 , . . . , vsd are the neighbors of vi , then there
are d variables yi,1 , . . . , yi,d and the following constraints: xs1 ,1 → yi,1 ,
R′ (xs2 ,1 , yi,1 , yi,2 ), R′ (xs3 ,1 , yi,2 , yi,3 ), . . . , R′ (xsd ,1 , yi,d−1 , yi,d ), R′ (xi,1 , yi,d , x).
– For every variable z, there is a constraint x → z.
Observe that the number of variables of type yi,j is exactly 2m. Setting every
variable to 1 is a satisfying assignment. Set k := St + S − 1.
Assume that there is a satisfying assignment where the number of 0’s is at
most k (but positive). Variable x has to be 0, otherwise every other variable is
1. If xi,1 is 0, then xi,j is 0 for every 1 ≤ j ≤ S. Thus k < S(t + 1) implies that
there are at most t values of i such that xi,1 is 0. Let D consist of all vertices
vi such that xi,1 is 0. We claim that D is a dominating set. Suppose that some
vertex vi is not dominated. This means that if vs1 , . . . , vsd are the neighbors of
vi , then the variables xs1 ,1 , . . . , xsd ,1 , xi,1 all have the value 1. However, this
means that these variables force variables yi,1 , . . . , yi,d and variable x to value
1, a contradiction. Thus D is a dominating set of size at most t.
The reverse direction is also easy to see. Assume that G has a dominating set
D of size at most t. For every 1 ≤ i ≤ n and 1 ≤ j ≤ S, set variable xi,j to 1 if
and only vi is not contained in D. Set x to 0. It is easy to see that this assignment
can be extended to the variables yi,j to obtain a satisfying assignment: indeed,
if vs1 , . . . , vsd are the neighbors of vi and none of them is in D then vi ∈ D,
and we set yi,1 = . . . = yi,d = 1. Otherwise, if j is minimal such that vsj ∈ D,
we set yi,1 = . . . = yi,j−1 = 1 and yi,q = 0 for q ≥ j. This satisfying assignment
contains at most St + 2m + 1 ≤ k variables with value 0, as required.
Finally, we reduce LS-CSP({R′ }) to LS-CSP({R}) (and so to LS-CSP(Γ )).
Take an instance (φ, f, k) of LS-CSP({R′ }), let V be the variables of φ and
c1 , . . . , cp the constraints of φ. We build an instance φ′ of LS-CSP({R}) as
follows.
1. For each 1 ≤ i ≤ max(p, k + 1), introduce new variables xi0 , xi1 .
2. For each constraint ci = R′ (x, y, z) in formula φ, replace it by the constraint
R(x, y, z, xi0 , . . . , xi0 , xi1 , . . . , xi1 ).
11

3. For each ordered pair (i, j) where 1 ≤ i, j ≤ max(p, k+1), add the constraints
R(xi0 , xi0 , xj0 , xj0 , . . . , xj0 , xj1 , . . . , xj1 ) and R(xj1 , xj1 , xi1 , xj0 , . . . , xj0 , xj1 , . . . , xj1 ).
Finally, extend f so that, for all i, we have xi0 = 0 and xi1 = 1. It is clear that
the obtained mapping f ′ is a solution to the new instance. Note that, by the
choice of R′ , the tuple (1, 1, 0, 0, . . . , 0, 1, . . . , 1) does not belong to R. Hence, the
constraints added in step (3) above ensure that if a variable of the form xi0 or
xi1 in f ′ is flipped then, in order to get a solution to φ′ different from f ′ , one
must flip at least one of xi0 or xi1 for each 1 ≤ i ≤ max(p, k + 1). Consequently,
all solutions to φ′ that lie within distance k from f ′ must agree with f ′ on all
such variables. In other words, searching for such a solution, it makes sense to
flip only variables from V . Thus, clearly, the instances (φ, f, k) and (φ′ , f ′ , k) are
equivalent.
⊓
⊔

References
1. P. Chapdelaine and N. Creignou. The complexity of Boolean constraint satisfaction
local search problems. Annals of Mathematics and Artificial Intelligence, 43:51–63,
2005.
2. D. Cohen and P. Jeavons. The complexity of constraint languages. In F. Rossi,
P. van Beek, and T. Walsh, editors, Handbook of Constraint Programming, chapter 8. Elsevier, 2006.
3. N. Creignou, S. Khanna, and M. Sudan. Complexity Classifications of Boolean Constraint Satisfaction Problems, volume 7 of SIAM Monographs on Discrete Mathematics and Applications. 2001.
4. P. Crescenzi and G. Rossi. On the Hamming distance of constraint satisfaction
problems. Theoretical Computer Science, 288(1):85–100, 2002.
5. E. Dantsin, A. Goerdt, E. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou,
2
P. Raghavan, and U. Schöning. A deterministic (2 − k+1
)n algorithm for k-SAT
based on local search. Theoretical Computer Science, 289:69–83, 2002.
6. R. Downey and M. Fellows. Parameterized Complexity. Springer, 1999.
7. M. Fellows. Parameterized complexity: new developments and research frontiers.
In Aspects of Complexity (Kaikura, 2000), volume 4 of de Gruyter Series in Logic
and Applications, pages 51–72. 2001.
8. J. Flüm and M. Grohe. Parameterized Complexity Theory. Springer, 2006.
9. J. Gu, P. Purdom, J. Franko, and B.W. Wah. Algorithms for the Satisfiability
Problem. Cambridge University Press, Cambridge, MA, 2000.
10. E. Hirsch. SAT local search algorithms: worst-case study. Journal of Automated
Reasoning, 24:127–143, 2000.
11. H. Hoos and E. Tsang. Local search methods. In F. Rossi, P. van Beek, and
T. Walsh, editors, Handbook of Constraint Programming, chapter 5. Elsevier, 2006.
12. L. Kirousis and Ph. Kolaitis. The complexity of minimal satisfiability problems.
Information and Computation, 187:20–39, 2003.
13. D. Marx. Parameterized complexity of constraint satisfaction problems. Computational Complexity, 14:153–183, 2005.
14. D. Marx. Searching the k-change neighborhood for TSP is W[1]-hard. Operations
Research Letters, 36:31–36, 2008.
15. C. Moore and J. M. Robson. Hard tiling problems with simple tiles. Discrete
Comput. Geom., 26(4):573–590, 2001.

12

16. T.J. Schaefer. The complexity of satisfiability problems. In STOC’78, pages 216–
226, 1978.

13

Appendix
The following proposition completes the proof of Theorem 9.
Proposition 10. If R is a flip separable relation that is not width-2 affine then
LS-CSP({R}) is NP-hard.
The above proposition will be proved through a sequence of lemmas, the
main lemmas being Lemma 16 and Lemma 19.
We need three auxiliary lemmas that will be used in the subsequent proofs.
Lemma 11. Let R is the set of solutions to a Γ -formula φ, and let R′ =
prJ (R) where J = {j | prj (R) = {0, 1}}. Then the problems LS-CSP(Γ ) and
LS-CSP(Γ ∪ {R′ }) are polynomial-time equivalent.
Proof. Note that, for any fixed j 6∈ J, each solution to φ takes the same value on
the corresponding variable. In every instance of CSP(Γ ∪ {R′ }), every constraint
of the form c = R′ (s) can be replaced by the constraints from φ where variables
from s keep their places, while all other variables are new and do not appear
elsewhere. This transformation (with the distance k unchanged) is a polynomialtime reduction from LS-CSP(Γ ∪ {R′ }) to LS-CSP(Γ )
⊓
⊔
Let C0 = {0} and C1 = {1}, and let Γ c = Γ ∪ {C0 , C1 }.
Lemma 12. If Γ contains at least one of the relations = or 6= then LS-CSP(Γ )
is polynomial-time equivalent to LS-CSP(Γ c ).
Proof. Assume that Γ contains the equality relation, the other case is very similar. We only need to provide a reduction from LS-CSP(Γ c ) to LS-CSP(Γ ).
Let (φ, f, k) be an instance of the former problem. For every variable x in φ
such that φ contains the constraint C0 (x) or C1 (x) (i.e., the value of variable
x is forced to be a constant 0 or 1), remove this constraint, introduce k new
variables yx,1 , . . . , yx,k , and add new constraints x = yx,i , (i = 1, . . . , k). Call the
obtained Γ -formula φ′ . Extend f to a solution f ′ of φ′ by setting f ′ (yx,i ) = f (x)
for all i, and consider the instance (φ′ , f ′ , k) of LS-CSP(Γ ). The equality constraints in φ′ ensure that every solution to φ′ whose distance is at most k from
f ′ must coincide with f ′ on all variables of the form yx,i . It is clear now that the
instances (φ, f, k) and (φ′ , f ′ , k) are equivalent.
⊓
⊔
Let R1 be an arbitrary n-ary relation (n ≥ 2) and let R2 be an (n + 1)-ary
relation such that (a1 , . . . , an , an+1 ) ∈ R2 ⇔ (a1 , . . . , an ) ∈ R1 and an 6= an+1 .
Lemma 13. The problems LS-CSP({R1 , 6=}) and LS-CSP({R2 , 6=}) are polynomial time equivalent.
Proof. It is clear that LS-CSP({R2 , 6=}) reduces to LS-CSP({R1 , 6=}), by simply replacing each constraint involving R2 by its definition via R1 and 6=. Let us
reduce LS-CSP({R1 , 6=}) to LS-CSP({R2 , 6=}). Let (φ, f, k) be an instance of
LS-CSP({R1 , 6=}) where φ is over a set V of variables. For each variable x ∈ V ,
14

introduce two new variables x′ , x′′ along with constraints x 6= x′ , x′ 6= x′′ . Replace every constraint of the form R1 (xi1 , . . . , xin ) in φ by R2 (xi1 , . . . , xin , x′in ),
and leave all other constraints in φ unchanged. Let φ′ be the obtained instance of
CSP({R2 , 6=}). Clearly, f has a unique extension to a solution f ′ to I ′ . It is clear
that the instance (φ′ , f ′ , 3k) of LS-CSP({R2 , 6=}) is equivalent to (φ, f, k). ⊓
⊔
We consider affine constraints first.
Lemma 14. If Γ contains the ternary relation defined by equation x+y +z = 1,
then LS-CSP(Γ ) is NP-hard.
Proof. First, we show that we can assume that the relation 6= is in Γ . Notice
that if R is the set of all solutions to the instance x + y + z = 1, z + z + z = 1.
Then pr{3} (R) = 1 while pr{1,2} (R) is the equality relation. By Lemma 11, we
may assume that the relation = is in Γ . Then, by Lemma 12, we can assume
that C0 , C1 ∈ Γ . By considering the instance C0 (z), x + y + z = 1 and using Lemma 11 again, we get that LS-CSP(Γ ) is polynomial-time equivalent to
LS-CSP(Γ ∪ {6=}).
The hardness proof is by reduction from CSP(R1-in-3 ), which is known to
be NP-hard even if every variable appears in exactly 3 constraints and each
constraint contains 3 distinct variables [15]. (This implies that the number of
variables equals the number of constraints and the weight of every solution is
exactly n/3, where n is the number of variables.) Given a CSP(R1-in-3 ) formula
φ with n variables x1 , . . . , xn , we construct a Γ -formula φ′ with variables
– xi,j for 1 ≤ i ≤ n, 1 ≤ j ≤ 2n,
– vt for every 1 ≤ t ≤ n,
– yj for every 0 ≤ j ≤ 2n2 .
For every 1 ≤ i ≤ n, 1 ≤ j, j ′ ≤ 2n, we add the constraint xi,j = xi,j ′ . For
every 1 ≤ j, j ′ ≤ 2n2 , we add the constraint yj = yj ′ . Assume that the t-th
constraint in φ is on variables xa , xb , xc . For 1 ≤ j ≤ 2n, we add the constraints
xa,j + xb,j + vt = 1 and xc,j + vt + y0 = 1. Finally, we add the constraint
y0 6= y1 . Define assignment f such that f (vt ) = 1 for 1 ≤ t ≤ n and f (yj ) = 1
for 1 ≤ i ≤ 2n2 , and every other variable is 0. The weight of f is 2n2 + n. Set
k := 2n2 + 1 + n + 2n · n/3. This completes the description of the reduction.
Assume that φ has a solution f0 . Define f ′ such that f ′ (xi,j ) = f0 (xi ) (1 ≤
i ≤ n, 1 ≤ j ≤ 2n), f ′ (y0 ) = 1, f ′ (yj ) = 0 (1 ≤ j ≤ 2n2 ). This assignment can
be extended to each vt in a unique way: if the t-th constraint in φ is on variables
xa , xb , xc , then exactly two of the variables xa,1 , xb,1 , xc,1 , y0 have value 1, hence
we can set vt accordingly. Thus we can obtain a satisfying assignment f ′ this
way. Observe that the weight of f0 is exactly n/3: each variable with value 1 in
f0 appears in exactly 3 constraints and each constraint contains exactly one such
variable. Thus the weight of f ′ is at most 2n · n/3 + 1 + n < 2n2 + n, strictly less
than the weight of f . Assignments f and f ′ differ on at most 2n2 +1+n+2n·n/3 =
k variables.
Assume now that φ′ has a satisfying assignment f ′ with w(f ′ ) < w(f ) and
dist(f, f ′ ) ≤ k. We claim that f ′ (y0 ) = 1 and f ′ (yi ) = 0 (1 ≤ i ≤ 2n2 ).
15

Otherwise, w(f ′ ) < w(f ) would imply that f ′ (vt ) = 0 for at least one 1 ≤ t ≤ n.
But this means that there is at least one 1 ≤ i ≤ n such that f ′ (xi,j ) = 1 for
every 1 ≤ j ≤ 2n. Thus the weight of f ′ is at least 2n2 + 2n > 2n2 + n, a
contradiction.
Define f0 (xi ) := f ′ (xi,1 ) for every 1 ≤ i ≤ n. The weight of f0 is at most n/3:
otherwise, dist(f, f ′ ) would be at least 2n(n/3+1)+2n2 +1 > k. Let xa , xb , xc be
the variables in the t-th constraint in φ. The facts f ′ (xa,1 )+ f ′ (xb,1 )+ f ′ (vt ) = 1,
f ′ (xc,1 ) + f ′ (vt ) + f ′ (y0 ) = 1 and f ′ (y0 ) = 1 imply that at least one of f ′ (xa,1 ),
f ′ (xb,1 ), f ′ (xc,1 ) is 1. Thus if we denote by X the set of those variables of φ that
have value 1 in f0 , then each constraint in φ contains at least one variable of X.
Moreover, it is not possible that a constraint contains more than one variables
of X. To see this, observe that each variable is contained in 3 constraints, thus
|X| ≤ n/3 implies that the variables of X appear in at most n constraints.
However, we have seen that each constraint contains at least one variable of X,
hence the variables of X appear in exactly n contraints. Equality is possible only
if any two variables of X appear in disjoint constraints, that is, no constraint
contains more than one variables from X. Therefore, f0 is a solution for the
instance φ.
⊓
⊔
Define the 6-ary affine relation R6 by the following system of equations:
x1 + x2 + x3 = 1, xi + xi+3 = 1(1 ≤ i ≤ 3). Let J be a subset of {1, . . . , 6}, and
let RJ denote the projection of R6 onto the set of indices J.
Lemma 15. LS-CSP({RJ }) is NP-hard for every J ⊆ {1, . . . , 6} containing at
least one number from each pair i, i + 3 where i = 1, 2, 3.
Proof. Note that the relation R6 does not change if the first equation in the
system is replaced by x4 + x2 + x3 = 0. We will assume that 1, 2, 3 ∈ J. All other
cases are very similar. As in the (beginning of the) proof of Lemma 14, we can
argue that LS-CSP({RJ }) is polynomial-time equivalent to LS-CSP({RJ , 6=})
Now the lemma follows from Lemmas 14 and 13.
⊓
⊔
Lemma 16. LS-CSP({R}) is NP-hard if R is affine, but not of width 2.
Proof. First, we show that it is enough to prove the result for Γ = {R, C0 , C1 },
that is, that LS-CSP(Γ ) and LS-CSP({R}) are polynomial-time equivalent. If
R is neither 0- nor 1-valid, then fix a tuple in R that contains both 0 and 1,
say (0, . . . , 0, 1, . . . , 1), and consider the relation R′ (x, y) = R(x, . . . , x, y, . . . , y),
where positions of the x’s correspond to the 0’s in the tuple. It is clear that either
R1 = {(0, 1)} in which case we are done, or R1 is the disequality relation, and
then we are done by Lemma 12. If R is 0-valid, but not 1-valid, then take a tuple
a ∈ R that contains a minimal positive number of 1’s, say (0, . . . , 0, 1, . . . , 1).
The fact that R is affine and 0-valid
P implies that it can be defined by a system
of linear equations of the form
xi = 0. It follows that the number of 1’s in a
is at least two. Consider the instance R(z, . . . , z, x, y, . . . , y), R(z, . . . , z) where
the z’s in the first constraint correspond to the 0’s in a. by the choice of a,
the projection on x, y of the set of solutions of this instance is the equality
16

relation, while the projection on z is C0 . Now we can use Lemmas 11 and 12.
The argument is very similar if R is 1-valid, but not 0-valid. If R is both 0- and
1-valid then take any tuple, say (0, . . . , 0, 1, . . . , 1) 6∈ R and consider the relation
R′ (x, y) = R(x, . . . , x, y, . . . , y), where positions of the x’s correspond to 0’s in
the tuple. Since R′ is affine, it can only be the equality relation, and we are done
again.
Now let R′ be a minimium arity relation which can be obtained from R
by substituting constants and identifying variables (note that such a relation
is also affine) and which is not of width-2. We claim that R′ , possibly after
permuting variables, is a relation of the form RJ , as in Lemma 15. By Lemma 11,
establishing this claim would finish the proof of the present lemma.
Note that by the minimality of (the arity of) R′ , none of the projections of
′
R onto a single coordinate can be one-element, and none of the projections of
R′ onto a pair of coordinates can be the equality relation. Thus every binary
projection is either the disequality relation or {0, 1}2 (note that the binary projection cannot contain 3 tuples, since R′ is affine). Furthermore, if two different
binary projections of R′ are disequality relations then the corresponding pairs
of coordinates are disjoint. Let R′′ be a largest arity projection of R′ such that
every binary projection of R′′ is {0, 1}2. Note that, to prove the lemma, it is
sufficient to show that R′′ is ternary and can be described by a single equation
x1 + x2 + x3 = a, a ∈ {0, 1}. It is easy to see that then a relation of the form
RJ can obtained from R′ by permuting coordinates: every variable of R not in
{x1 , x2 , x3 } forms a disequality relation with one of x1 , x2 , x3 .
Consider the relations R0′′ = R′′ (x1 , . . . , xn , 0) and R1′′ = R′′ (x1 , . . . , xn , 1).
By the choice of R′ , both of these relations are of width-2 affine, that is each
of them can be expressed by a system of equations of the form xi + xj = a,
a ∈ {0, 1}. Note that it is impossible that, for a pair of coordinates i, j, exactly
one of the projections of R0′′ and R1′′ onto i, j is the full relation {0, 1}2 . Indeed,
this would imply that the size of the projection of R′′ onto {i, j} would not be
a power of 2. Therefore, if, for a pair of indices i, j, one of the projections of R0′′
and R1′′ onto i, j is the equality relation then the other must be the disequality
relation (to ensure that the projection of R′′ onto {i, j} is {0, 1}2). It follows
that R′′ can be described by the following system of equations: for each pair
i, j such that pri,j (R0′′ ) is the equality relation the system contains the equation
xi + xj + xn+1 = 0, and for each pair i, j such that pri,j (R0′′ ) is the disequality
relation the system contains the equation xi + xj + xn+1 = 1, and there are no
other equations in the system.
Note that if some xi with 1 ≤ i ≤ n participates in at least two equations in
this system (which also involve xj and xj ′ ) then the projection of R′′ onto j, j ′
would not be {0, 1}2, which is a contradiction. Hence, the only variable that may
appear in more than one equation is xn+1 . Assume that the system contains at
least two equations, say, x1 + x2 + xn+1 = a and x3 + x4 + xn+1 = b. Then, by
identifying x4 with xn+1 in R′ , we would be able to obtain a relation which is
affine but not width-2 (because of the equation x1 + x2 + xn+1 = a), and has
arity smaller than the arity of R′ , which is a contradiction.
17

⊓
⊔

The lemma is proved.

It remains to consider the case when Γ contains a relation that is flip separable, but not affine. Again, we first consider one particular relation.
Lemma 17. LS-CSP({R1-in-3 }) is NP-hard.
Proof. First, we show that we can assume that the relation 6= is available. Consider the instance R1-in-3 (x, y, z0 ), R1-in-3 (z0 , z0 , z1 ). It is easy to see that the
projection on x, y of the set of all solutions of this instance is 6=, and Lemma 11
implies that it is now sufficient to prove that LS-CSP({R1-in-3, 6=}) is NP-hard.
The proof is by reduction from LS-CSP({x ∨ y}). Let (φ1 , f1 , k) be an instance of LS-CSP({x∨y}) with n variables and m constraints. Set S := 10n2 m2 .
We construct a formula φ2 with the following variables:
– For each variable v of φ1 with f (v) = 1, there is a variable x0v and S − 2m
variables x1v,1 , . . . , x1v,S−2m .
– For each variable v of φ1 with f (v) = 0, there is a variable x0v and S variables
x1v,1 , . . . , x1v,S .
– For each constraint c of φ1 , there is a variable yc .
The constraints of φ2 are as follows:
– For every variable v of φ1 with f (v) = 1, there is a constraint x0v 6= x1v,i
(1 ≤ i ≤ S − 2m).
– For every variable v of φ1 with f (v) = 0, there is a constraint x0v 6= x1v,i
(1 ≤ i ≤ S).
– For every constraint c = (u ∨ v) of φ1 , there is a constraint R1-in-3 (x0u , x0v , yc ).
We observe that the satisfying assignments of φ2 are in one-to-one correspondence with the satisfying assignments of φ1 . First, since x0v 6= x1v,i for every i,
we have that x1v,i1 = x1v,i2 for every i1 , i2 . Given a satisfying assignment f of
φ2 , we can obtain an assignment of φ1 by setting f (v) = f (x1v,1 ). Observe that
this gives a satisfying assignment of φ1 : if c = (u ∨ v) is a constraint of φ1 , then
f (u) = f (v) = 0 would imply f (x0u ) = f (x0v ) = 1, which would mean that the
constraint R1-in-3 (x0u , x0v , yc ) is not satisfied. On the other hand, if f satisfies φ1 ,
then setting f (x1v,1 ) = f (v) has a unique satisfying extension to φ2 .
Let f2 be the assignment of φ2 corresponding to assignment f1 of φ1 . Set
k ′ := k(S + 1) + m. We claim that (φ2 , f2 , k ′ ) is a yes-instance if and only if
(φ1 , f1 , k) is a yes-instance.
Let f1′ be an arbitrary satisfying assignment of φ1 and let f2′ be the corresponding assignment of φ2 . Let B (resp., B ′ ) contain variable v of φ1 if and only
if f1 (v) = 1 (resp., f1′ (v) = 1). Assignments f2 and f2′ differ on every variable
x0v , x1v,i with v ∈ |B \ B ′ | ∪ |B ′ \ B|, and possibly on some of the variables yc .
Counting the number of 0’s and 1’s on these variables, it follows that the weight
of f2′ is at least
w(f2 ) + |B ′ \ B|(S − 1) − |B \ B ′ |(S − 2m − 1) − m
18

(1)

and at most
w(f2 ) + |B ′ \ B|(S − 1) − |B \ B ′ |(S − 2m − 1) + m,

(2)

where the ±m term accounts for the variables of the form yc .
To prove that (φ2 , f2 , k ′ ) is a yes-instance if and only if (φ1 , f1 , k) is a yesinstance, first we assume that (φ1 , f1 , k) has a solution f1′ ; let f2′ be the corresponding assignment of φ2 . Define B and B ′ as above. It is easy to see that the
distance of f2 and f2′ is at most |B \ B ′ |(S − 2m + 1) + |B ′ \ B|(S + 1) + m ≤
k(S + 1) + m = k ′ . From |B ′ | < |B| we have |B ′ \ B| < |B \ B ′ |. Thus by (2),
the weight of f2′ is at most
w(f2 ) + |B ′ \ B|(S − 1) − |B \ B ′ |(S − 2m − 1) + m
≤ w(f2 ) + |B ′ \ B|(S − 1) − (|B ′ \ B| + 1)(S − 2m − 1) + m
= w(f2 ) + |B ′ \ B|2m + 3m + 1 − S < w(f2 ),
since S is sufficiently large.
For the second direction, suppose that there is a solution f2′ for instance
(φ2 , f2 , k ′ ). Let f1′ be the corresponding satisfying assignment, and define B and
B ′ as before. First we show that the distance of f1′ and f1 is at most k, i.e.,
|B ′ \ B| + |B \ B ′ | ≤ k. Assignments f2 and f2′ differ on every vertex of x1v,i for
v ∈ |B ′ \B|+|B \B ′ | and 1 ≤ i ≤ S −2m. Thus |B ′ \B|+|B \B ′ | > k would imply
that the distance of f2 and f2′ is at least (k+1)(S −2m) = k(S +1)+S −k−2m >
k(S +1)+m = k ′ , since S is sufficiently large. Let us show that |B ′ \B| < |B \B ′ |.
Suppose first that |B \ B ′ | = 0. By (1), the weight of f2′ is at least
w(f2 ) + |B ′ \ B|(S − 1) − |B \ B ′ |(S − 2m − 1) − m ≥ w(f2 ) + (S − 1) − m ≥ w(f2 ),
contradicting the assumption w(f2′ ) < w(f2 ). Suppose now that |B ′ \ B| ≥
|B \ B ′ | ≥ 1. Now the weight of f2′ is at least
w(f2 ) + |B ′ \ B|(S − 1) − |B \ B ′ |(S − 2m − 1) − m
≥ w(f2 )+|B\B ′ |(S−1)−|B\B ′ |(S−2m−1)−m = w(f2 )+|B\B ′ |2m−m > w(f2 ),
⊓
⊔

again a contradiction.

Consider the 6-ary relation T6 defined as follows: (a1 , . . . , a6 ) ∈ T6 if and only
if (a1 , a2 , a3 ) ∈ R1-in-3 and ai 6= ai+3 (1 ≤ i ≤ 3). Let J be a subset of {1, . . . , 6}
and let TJ denote the projection of T6 onto the set of indices J. Similarly to
Lemma 15, we have:
Lemma 18. LS-CSP({TJ }) is NP-hard if J contains at least one number from
each pair i, i + 3 where i = 1, 2, 3.
Lemma 19. LS-CSP({R}) is NP-hard if R is flip separable but not affine.
19

Proof. Assume first that R is 0-valid. Then we can assume that the relation C0 is
available. Indeed, if R is not 1-valid then R(x, . . . , x) is this relation. If R is also 1valid then we can get C0 and C1 as in the proof of Lemma 16. Note that a relation
obtained from a flip separable relation by substituting constants and identifying
coordinates is again flip separable. It is shown in the proof of Lemma 5.30 of [3]
that, since R is not affine, it is possible to permute coordinates in R in such a
way that the relation R′ (x, y, z) defined as R(0, . . . , 0, x, . . . , x, y, . . . , y, z, . . . , z)
satisfies the following properties:
– The tuples (0, 0, 0), (0, 1, 1), (1, 0, 1) belong to R′ , and
– the tuple (1, 1, 0) does not belong to R′ .
Since R′ is flip separable, it is easy to see that if one of the tuples from R1-in-3
belongs to R′ then all of them do. However, in this case (1, 0, 0) ∈ R′ has flip sets
{1} and {1, 2}, and therefore {2} should also be a flip set for this tuple, which
is impossible because (1, 1, 0) 6∈ R′ . It follows that R′ ∩ R1-in-3 = ∅. If the tuple
(1, 1, 1) was in R′ then it would have flip sets {1, 2, 3} and {1}, and hence {2, 3}
as well, which is impossible. It follows that R′ = {(0, 0, 0), (0, 1, 1), (1, 0, 1)}. It
is easy to see that R′ is obtained from T{2,3,4} (as in Lemma 18) by a cyclic
permutation of coordinates. The lemma now follows from Lemmas 11 and 18.
If R is 1-valid then a similar reasoning shows that one can obtain the relation {(1, 1, 1), (0, 0, 1), (0, 1, 0)} which is the relation T{3,4,5} with permuted
coordinates.
Assume now that R is neither 0- nor 1-valid. As in the proof of Lemma 16,
one can show that both C0 and C1 can be assumed to be available. It is shown
in the proof of Lemma 5.30 of [3] that if R is Horn then there is an instance
of CSP({R, C0 , C1 }) over variables {x, y, z, u0, u1 } which contains constraints
C0 (u0 ) and C1 (u1 ), and such that the projection on x, y, z of the set of all
solutions to the instance contains (0, 0, 0), (0, 1, 1), (1, 0, 1), but does not contain
(1, 1, 0). This set must be a Horn relation. On the other hand, we showed above
that this set must coincide with {(0, 0, 0), (0, 1, 1), (1, 0, 1)}, which is not Horn,
a contradiction. If R is not Horn, then it is easy to show (see the proof of the
Lemma 5.26 of [3]) that there is an instance of CSP({R, C0 , C1 }) over variables
{x, y, u0 , u1 } which contains constraints C0 (u0 ) and C1 (u1 ), and such that the
projection on x, y is not {0, 1}2 and contains the relation 6=. Since this set must
be a flip separable relation, it is equal to 6=. Again, it is shown in the proof
of Lemma 5.30 of [3] that there exists an instance of CSP({R, 6=, C0 , C1 }) over
variables {x, y, z, x′ , y ′ , z ′ , u0 , u1 } which contains constraints x 6= x′ , y 6= y ′ ,
z 6= z ′ , C0 (u0 ) and C1 (u1 ), and such that the projection on x, y, z of the set R′′
of all solutions to the instance contains (0, 0, 0), (0, 1, 1), (1, 0, 1), but does not
contain (1, 1, 0). Since R′′ is flip separable, it is easy to show (as above) that,
in fact, the projection of R′′ onto x, y, z, x′ , y ′ , z ′ is equal to T6 (with permuted
coordiantes). Now the result follows from by Lemmas 11 and 18.
⊓
⊔

20

