Complexity and Approximability of
Parameterized MAX-CSPs
Holger Dell1 , Eun Jung Kim2 , Michael Lampis3 , Valia Mitsou∗4 , and Tobias Mömke†5
1

Saarland University and Cluster of Excellence, Saarbrücken, hdell@mmci.uni-saarland.de
Université Paris Dauphine, eunjungkim78@gmail.com, michail.lampis@dauphine.fr
4
SZTAKI, Hungarian Academy of Sciences, Budapest, vmitsou@sztaki.hu
5
Saarland University, Saarbrücken, moemke@cs.uni-saarland.de

arXiv:1511.05546v2 [cs.CC] 23 Jan 2017

2,3

January 24, 2017

Abstract
We study the optimization version of constraint satisfaction problems (Max-CSPs)
in the framework of parameterized complexity; the goal is to compute the maximum
fraction of constraints that can be satisfied simultaneously. In standard CSPs, we
want to decide whether this fraction equals one. The parameters we investigate
are structural measures, such as the treewidth or the clique-width of the variable–
constraint incidence graph of the CSP instance.
We consider Max-CSPs with the constraint types AND, OR, PARITY, and
MAJORITY, and with various parameters k, and we attempt to fully classify them
into the following three cases:
1. The exact optimum can be computed in FPT time.
2. It is W[1]-hard to compute the exact optimum, but there is a randomized FPT
approximation scheme (FPT-AS), which computes a (1 − ǫ)-approximation in
time f (k, ǫ) · poly(n).
3. There is no FPT-AS unless FPT = W[1].
For the corresponding standard CSPs, we establish FPT vs. W[1]-hardness results.

1 Introduction
Constraint Satisfaction Problems (CSPs) play a central role in almost all branches of
theoretical computer science. Starting from CNF-SAT, the prototypical NP-complete
problem, the computational complexity of CSPs has been widely studied from various
∗
†

Supported by ERC Starting Grant PARAMTIGHT (No. 280152)
This research is supported by Deutsche Forschungsgemeinschaft grant BL511/10-1

1

points of view. In this paper we focus on two aspects of CSP complexity which, though
extremely well-investigated, have mostly been considered separately so far in the literature: parameterized complexity and approximability. We study four standard predicates
and contribute some of the first results indicating that the point of view of approximability considerably enriches the parameterized complexity landscape of CSPs.
Parameterized Complexity. For a parameterized problem P , an instance of P is a pair
(x, k) ∈ Σ∗ × N, where the second part k of the instance is called the parameter. A
parameterized problem P is fixed-parameter tractable (FPT in short) if there is an algorithm solving any input instance (x, k) of P in time O(f (k)·|x|O(1) ) for some computable
function f . Such an algorithm is called an FPT-algorithm.
For two parameterized problems P and Q, a parameterized reduction from P to Q is
an FPT-algorithm which, given an instance (x, k) of P , outputs an instance (x′ , k′ ) of
Q such that (i) (x, k) is a yes-instance if and only if (x′ , k′ ) is a yes-instance, and (ii)
k′ ≤ g(k) for some computable function g. The notion of paramterized reduction defines
the hierarchy of parameterized complexity classes
FPT = W [0] ⊆ W[1] ⊆ W[2] ⊆ · · · ⊆ XP,
where each class is the family of problems admitting a parameterized-reduction to some
basic problem. The central assumption in parameterized complexity is FPT 6= W [1].
Further parameterized complexity terminology used in this paper can be found in [8].
Parameterized CSPs. The vast majority of interesting CSPs are NP-hard [29, 19].
This has motivated the study of such problems from a parameterized complexity point
of view, and indeed this topic has attracted considerable attention in the literature
[15, 34, 12, 26, 14, 33]. We refer the reader to [28] where an extensive classification
of CSP problems for a large range of parameters is given. In this paper we focus on
structurally parameterized CSPs, that is, we consider CSPs where the parameter is some
measure of the structure of the input instance. The central idea behind this approach is
to represent the structure of the CSP using a (hyper-)graph and leverage the powerful
tools commonly applied to parameterized graph problems (such as tree decompositions)
to solve the CSP.
The typical goal of this line of research is to find the most general parameterization of
a CSP that still remains fixed-parameter tractable (FPT). To give a concrete example
for a very well-known CSP, CNF-SAT is FPT when parameterized by the treewidth of its
incidence graph1 [31] but it is W-hard for more general parameters such as clique-width
[24], or even the more restricted modular treewidth [25]. General (boolean) CSP on the
other hand, where the description of each constraint is part of the input is known to
be a harder problem: it is already W[1]-hard parameterized by the incidence treewidth,
but FPT parameterized by the treewidth of the primal graph [32]. Thus, parameterized
investigations aim to locate the boundary where a CSP jumps from being FPT to being
1

See the next section for a definition of incidence graphs

2

W-hard. It is of course a natural question how we can deal with the W-hard cases of a
CSP once they are identified.
Approximation. CSPs also play a central role in the theory of (polynomial-time) approximation algorithms [35, 20, 4]. In this context we typically consider a CSP as an
optimization problem (MAX-CSP) where the goal is to find an assignment to the variables that satisfies as many of the constraints as possible. Unfortunately, essentially all
non-trivial CSPs are hard to approximate (APX-hard) from this point of view [6, 19],
even those where deciding if an assignment can satisfy all constraints is in P (e.g. 2CNFSAT or Horn SAT). Thus, research in this area typically focuses on discovering exactly
the best approximation ratio that can be achieved in polynomial time. Amazingly, for
many natural CSPs this happens to be exactly the ratio achieved by a completely random assignment [18]. This motivates the question of whether we can find natural cases
where non-trivial efficient approximations are possible.
Results. In this paper we consider four different types of CSPs where the constraints
are respectively OR, AND, PARITY and MAJORITY functions. Our approach follows,
for the most part, the standard parameterized complexity script: we consider the input
instance’s incidence graph and try to determine the complexity of the CSP when parameterized by various graph widths. The new ingredient in our approach is that, in
addition to trying to determine which parameters make a CSP FPT or W-hard, we also
ask if the optimization versions of W-hard cases can be well-approximated. We believe
that this is a question of special interest since, as it turns out, there are CSPs for which
W-hardness can be (almost) circumvented using approximation, and others which are
inapproximable.
More specifically, our results are as follows: for OR constraints, which corresponds
to the standard CNF-SAT (MAX-CNF-SAT) problem, we present a new hardness proof
establishing that deciding a formula’s satisfiability is W-hard even if parameterized by
the incidence graph’s neighborhood diversity2 . Neighborhood diversity is a parameter
much more restricted than modular treewidth (already a restriction of clique-width) [21],
for which the strongest previously known W[1]-hardness result was known [25]. We complement this negative result with a strong positive approximation result: there exists a
randomized FPT Approximation Scheme (FPT-AS)3 for MAX-CNF-SAT parameterized
by clique-width, that is, an algorithm which for all ǫ > 0 runs in time f (k, ǫ)nO(1) and returns an assignment satisfying (1 − ǫ)OPT clauses. Thus, even though we establish that
solving CNF-SAT exactly is W-hard even for extremely restricted dense graph parameters, MAX-CNF-SAT is well-approximable even in the quite general case of clique-width.
2

Akin to neighborhood diversity is the twin-cover number proposed in [11]. On bipartite graphs such as
incidence graphs of CSPs, the twin-cover number is essentially the same as the vertex cover number:
it differs only on a graph consisting of a single edge, in which the twin-cover number equals 0 while
the vertex cover number is 1. Hence, we do not consider the twin-cover number separately as a
structural parameter in this paper.
3
We follow here the standard definition of FPT-AS given in [23].

3

tw∗
cw∗

fvs
L3.5
nd∗

∗

T5.2
fvs∗

tw∗
vc∗

cw∗

CNF-SAT

T5.3
nd∗

vc∗

MAJORITY-CSP

Figure 1: The parameterized complexity status of CNF-SAT and MAJORITY-CSP. The
boxes depict different parameterizations of each problem: red means that the
problem is W[1]-hard and green means that the problem is FPT. Recall that
DNF-SAT and PARITY-CSP are polynomial-time computable. An arrow indicates the existence of an approximation-preserving reduction from the problem
at the tail to the problem at the head, so for example, the arrow fvs∗ → tw∗ for
CNF-SAT indicates that there is a reduction from CNF-SAT parameterized
by fvs∗ to CNF-SAT parameterized by tw∗ . In fact, the reductions we depict
here are trivial since, for example, fvs∗ is bounded by a function of tw∗ .
To the best of our knowledge, this is the first approximation result of this type for a
W-hard MAX-CSP problem.
Recalling that MAX-CNF-SAT is FPT parameterized by the treewidth of the incidence
graph, we consider other problems for which the jump from treewidth to clique-width
could have interesting complexity consequences. We show that MAX-DNF-SAT and
MAX-PARITY, which are FPT parameterized by treewidth, exhibit two wildly different
behaviors. On the one hand, the problem of maximizing the largest possible number
of satisfied PARITY constraints remains FPT even for dense parameters such as cliquewidth. On the other hand, by modifying our reduction for CNF-SAT, we are able to
show not only that maximizing the number of satisfied AND constraints is W[1]-hard
parameterized by neighborhood diversity, but also that this problem cannot even admit
an FPT-AS (like MAX-CNF-SAT), unless W[1]=FPT. We recall that PARITY and
AND constraints are similar in other aspects: for example, for both we can decide in
polynomial time if an assignment satisfying all constraints exists.
Finally, we consider CSPs with MAJORITY constraints, that is, constraints which
are satisfied if at least half their literals are true. We give a reduction establishing that
this is an interesting case of a natural constraint type for which deciding satisfiability
is already W[1]-hard parameterized by treewidth (we actually show W[1]-hardness for
the more restricted case of incidence feedback vertex set) and by neighborhood diversity.
We complement this negative result with two algorithmic results: first, we show that the
corresponding MAX-CSP is FPT parameterized by incidence vertex cover. Then, we use
this algorithm as a sub-routine to obtain an FPT-AS for incidence feedback vertex set.
Both of these algorithmic results also apply to the more general case of THRESHOLD
constraints. We leave it as an interesting open problem to examine if the approximation
algorithm for feedback vertex set can be extended to treewidth.

4

tw∗
T3.1
cw∗

fvs

∗

∗

vc∗

nd

cw∗

nd

MAX-MAJORITY-CSP

fvs∗
T4.1
nd∗

T5.4
vc∗

∗

cw∗

MAX-CNF-SAT

tw∗

T5.6
fvs∗

tw∗

fvs∗

tw∗
T4.2
cw∗

vc∗

MAX-DNF-SAT

nd∗

vc∗

MAX-PARITY-CSP

Figure 2: The parameterized complexity status of MAX-CSP problems. The gray labels above the boxes indicate the theorem in which we establish the result;
previously known results are displayed without reference. Red means that
the problem is W[1]-hard to compute exactly, and there is no FPT-AS unless
FPT = W[1]. Blue means that the problem is W[1]-hard to compute exactly,
and there is an FPT-AS. Green means that the problem is FPT to compute
exactly. The blue/white stripes mean that it’s W[1]-hard to compute exactly,
and it’s open whether there is an FPT-AS.

5

2 Preliminaries
Boolean CSP. A Boolean Constraint Satisfaction Problem, CSP in short, ψ is defined
as a set {C1 , . . . , Cm } of m constraints over a set X(ψ) = {x1 , . . . , xn } of n variables
and their negations. Each constraint Ci is regarded as a function of literals (positive
or negative appearances of variables) mapped to the set {0, 1}, where literals can take
the values 0 or 1. Furthermore, we define |Cj | to denote the arity of constraint Cj (the
number of literals that occur in C) and |ψ| = m the number of constraints in ψ. For
simplicity, we also write li ∈ Cj for a literal li and a constraint Cj if li appears in Cj .
We will be dealing with Boolean CSP for four well-studied Boolean functions: OR constraints, AND constraints, PARITY (or XOR) constraints and MAJORITY constraints.
We say that an assignment t : X → {0, 1} satisfies a constraint C of type:
◦ OR, if ∃li ∈ C, t(li ) = 1;
◦ AND, if ∀li ∈ C, t(li ) = 1;
◦ PARITY, if it satisfies some equation Σli ∈C t(li ) = b (for b ∈ {0, 1}) modulo 2;
◦ MAJORITY, if at least ⌈|C|/2⌉ literals in C are set to 1. More generally, we may
consider THRESHOLD constraints, where a certain threshold number of literals
must be set to true to satisfy the constraint.
Let occ(ψ) = C∈ψ |C| be the total number of variable occurrences in ψ, that is, the
total size of the formula. For a variable x, we write ψx for the set of all constraints C ∈ ψ
where x occurs either positively or negatively; for the functions we consider without loss
of generality, no constraint contains both literals. Thus, the total number of occurrences
of a variable x is equal to |ψx |.
We are dealing also with MAX-CSPs, where given a set of constraints ψ, we are interested in finding an assignment to the variables that maximizes the number of satisfied
constraints. The natural decision version of this problem is, given a target k, decide
whether there exists an assignment that satisfies at least k constraints. Clearly, the
problem where we want to decide whether we can satisfy all the constraints is a special
case of the above decision problem since we can set k = m, but in some cases we consider
this simpler decision version, particularly when we want to show hardness.
In the case of OR constraints, the CSP and MAX-CSP problems correspond to the
more widely known CNF-SAT and MAX-CNF-SAT problems. In this case we call the
constraints clauses. When the constraint function is AND, the MAX-CSP problem
is called MAX-DNF-SAT. In that case, the constraints are called terms. The problem
MAX-PARITY is also known as MAX-LIN-2 (satisfy a maximum number of given linear
equations modulo 2).
P

Incidence graph and structural parameters. For a CSP ψ, the incidence graph G∗ψ
is defined as the bipartite graph where we construct one vertex vi for each (unsigned)
variable xi and one vertex uj for each constraint Cj and connect vi with uj if xi ∈ Cj .

6

fvs∗

tw∗
cw∗

nd∗

vc∗

Figure 3: The structural parameters we study and their relationships. For example, the
arrow between cw∗ and tw∗ means that if the treewidth is bounded, then
the clique-width is bounded as well — more precisely, there is a monotone
computable function f : N → N so that cw∗ ≤ f (tw∗ ). On the other hand,
tw∗ and nd∗ as well as fvs∗ and nd∗ cannot be bounded by each other in
general.
We are interested in parameterizations of the incidence graph p(G∗ψ ) (or simply p∗ if
is clear from the context), where p is a structural parameter of G∗ψ . We are mostly
interested in the two most widely studied graph parameters, treewidth tw∗ and cliquewidth cw∗ . The definitions of treewidth and clique-width are rather lengthy, and we
refer the reader to standard parameterized complexity textbooks for the definitions, for
example [8].
Another structural parameter we study is the incidence neighborhood diversity denoted
as nd∗ . A graph G(V, E) has neighborhood diversity nd(G) = k if we can partition V
into k sets V1 , . . . , Vk such that, for all v ∈ V and all i ∈ {1, . . . , k}, either v is adjacent
to every vertex in Vi or it is adjacent to none of them. In other words, nd(G) = k if V
can be partitioned into k modules that are either cliques or independent sets. We also
investigate the complexity of CSPs parameterized by the vertex cover number vc∗ and
the feedback vertex set number fvs∗ of the incidence graph, that is, the minimum number
of vertices that need to be deleted to make the graph edgeless and acyclic, respectively.
G∗ψ

3 CNF-SAT and MAX-CNF-SAT
In this section, we consider one of the most fundamental problems in computer science:
the satisfiability problem for CNF formulas, which can be viewed as a constraint satisfaction problem where the only allowed constraints are clauses, that is, ORs of literals.
An optimal solution for MAX-CNF-SAT can be computed in FPT when parameterized
by the treewidth tw∗ of the incidence graph [1], and hence CNF-SAT can be solved in
the same time. When parameterized by the clique-width cw∗ of the incidence graph,
all known exact algorithms for CNF-SAT and MAX-CNF-SAT run in XP time [30, 27].
Moreover, we do not expect these problems to be in FPT since they are both W[1]-hard
parameterized by cw∗ [25].
In Section 3.1, we construct an approximation scheme for MAX-CNF-SAT that runs
in FPT time. Intuitively, our algorithm works as follows: given a formula φ with ‘small’
incidence clique-width, we first examine the formula to see if it contains many or few
‘large’ clauses. If the formula contains relatively few large clauses, then we simply disregard them. We then know that the incidence graph does not contain ‘large’ bi-cliques,
so by a theorem of Gurski and Wanke [16] the remaining formula has small treewidth

7

and we can solve the problem. If on the other hand the original formula contains almost
exclusively large clauses, then we observe that we can rely on a random assignment to
satisfy almost everything.
The hard part of our algorithm is then how to deal with the general case of formulas
that may contain clauses of varying arities, for which we use a combination of the ideas
for the two basic cases. In particular, after locating and deleting a negligibly small set
of ‘medium’ clauses, we use a counting argument to find a set of variables that appear
almost exclusively in large clauses. By setting these variables randomly we satisfy almost
all large clauses, and we can then use treewidth to handle the remaining instance.
In Section 3.2, we explore a class of CSP instances that is smaller than the class of
bounded incidence clique-width instances; our goal is to understand which incidence
graph parameter is responsible for the transition from FPT to W[1]. To this end, we
have to look for a graph parameter that is bounded by a function of cw∗ (where the
problem is hard) but can leave the tw∗ unbounded (where it’s FPT). In fact, [25] shows
that the problem is W[1]-hard parameterized by the modular incidence treewidth mtw∗ ,
which lies between cw∗ and tw∗ .4 We study the incidence neighborhood diversity nd∗ ,
which is incomparable to tw∗ ; however, mtw∗ is bounded when nd∗ is. We prove that
CNF-SAT remains W[1]-hard parameterized by nd∗ .
Formulas whose incidence graph has neighborhood diversity at most k seem very
restrictive: there are only at most k variable- and clause-types, where all variables of
the same type belong to the same clauses and all clauses of the same type involve the
same variables. This class of formulas is a subset of formulas with mtw∗ ≤ k because
contracting all modules leaves a graph of order at most k, which trivially has treewidth
at most k.

3.1 Approximation Algorithm parameterized by clique-width
Theorem 3.1. There is a randomized algorithm such that, for every ǫ > 0 and given a
CNF formula ψ with n variables, m clauses, and incidence clique-width cw, runs in time
f (ǫ, cw) · poly(n + m), and outputs a truth assignment that satisfies at least (1 − ǫ) · OPT
clauses in expectation.
We formulate the following basic lemma about probability distributions.
Lemma 3.2. For all ǫ, L > 0 there is a c = c(ǫ, L) > 0 such that all c′ ≥ c and all
P′
sequences p1 , . . . , pc′ ≥ 0 with ci=1 pi ≤ 1 have an index d ≤ c/L with the property
L·d
. X
p[d,L·d] =
pj < ǫ .
j=d

4

A CNF formula has bounded modular incidence treewidth if its incidence graph has bounded treewidth
after merging variable/clause modules into a single vertex. Here, a variable/clause module is a set of
vertices, corresponding to variables/clauses respectively, with same neighborhood outside of the set.
In fact, the reduction in [25] constructs a formula whose incidence graph has small feedback vertex
set after contracting modules.

8

Proof. Let ǫ, L > 0. We set c = c(ǫ, L) below. Assume for contradiction that p[d,L·d] ≥ ǫ
holds for all d ∈ [1, c/L]. If there are 1/ǫ + 1 disjoint intervals [a1 , L · a1 ], . . . , [a1/ǫ+1 , L ·
a1/ǫ+1 ] ⊆ [1, c], then we arrive at a contradiction with the fact that the pi ’s are nonnegative and sum to at most one. Clearly there exists a constant c = c(ǫ, L) such that
1/ǫ + 1 disjoint intervals of the form [a, La] fit into [1, c]. This proves the claim.
For an arbitrary given ǫ > 0, we fix L = ǫ−4 . We use Lemma 3.2 as follows: For a
CNF formula ψ, we define pi as the fraction of clauses of size i, that is,
.
pi =

n

C ∈ ψ |C| = i

o

|ψ|

.

Then Lemma 3.2 gives us a number d ≤ c(ǫ) such that the total fraction of clauses whose
size is between d and ǫ−4 d is bounded by ǫ. It is now natural to partition all clauses into
short, medium, and long clauses. More precisely, we define ψ = ψ <d ∪˙ ψ [d,D] ∪˙ ψ >D for
D = ǫ−4 d as follows:
o
. n
ψ <d = C ∈ ψ |C| < d ,
o
. n
ψ [d,D] = C ∈ ψ d ≤ |C| ≤ D , and
o
. n
ψ >D = C ∈ ψ |C| > D .

An immediate corollary to Lemma 3.2 is thus that we can choose d ≤ c(ǫ) in such a way
that |ψ [d,D] | ≤ ǫ|ψ|.
Corollary 3.3. For all ǫ > 0 there is some c = c(ǫ) > 0 such that all CNF formulas ψ
−4
have some d = d(ǫ) ∈ [1, c] with |ψ [d,ǫ d] | ≤ ǫ · |ψ| .
If ψ [d,D] = ∅ holds for D = ǫ−4 d and d ∈ [1, c(ǫ)], we say that ψ is ǫ-well separated.
We call ψ ǫ′ -balanced if, in addition, we have |ψ <d | ≥ ǫ′ m and |ψ >D | ≥ ǫ′ m.
Lemma 3.4. Let ψ be an ǫ-well separated formula (and thus V = V (ψ <d ) ∪ V (ψ >D )).
Then, for each subset ψ̂ ⊆ ψ >D with |ψ̂| > ǫ2 m, there is a variable y such that
<d
|ψy | ≤ ǫ2 |ψ̂y |.
That is, for every set ψ̂ that contains a significant fraction of long clauses, there is a
variable that occurs |ψ̂y | times in ψ̂, but only at most an ǫ2 -fraction of that in the short
clauses.
Proof. Let ψ̂ ⊆ ψ >D with |ψ̂| > ǫ2 m. Note that the total number of literal occurrences
in ψ̂ is occ(ψ̂) > D · ǫ2 · m = ǫ−2 dm. In contrast, occ(ψ <d ) < dm. Now suppose that
there was no variable y with the claimed properties, that is, suppose that every variable
y satisfies |ψy<d | > ǫ2 |ψ̂y |. Then the total number of variable occurrences in ψ <d can be
bounded from below as follows:
occ(ψ <d ) =

X
y

|ψy<d | >

X

ǫ2 |ψ̂y | = ǫ2 occ(ψ̂) > d · m .

y

This yields a contradiction and thus proves the claim.

9

Proof of Theorem 3.1. The algorithm A works as follows. Let ǫ′ = ǫ2 , and we assume
w.l.o.g. that ǫ < 1/8. Given a CNF formula φ, we compute an ǫ′ -well separated formula
ψ by dropping all clauses in φ[d,D] . Corollary 3.3 guarantees that the fraction of deleted
clauses is bounded by ǫ′ . If ψ is not ǫ/2-balanced, we discard the smaller side (with
fewer clauses) and only handle the larger one: If ψ <d is the larger side, we compute an
optimal assignment for ψ <d in FPT time, by using the result of Gurski and Wanke [16].
This way the total number of unsatisfied clauses is at most ǫm/2, and together with the
unsatisfied clauses due to applying Corollary 3.3, the total number of unsatisfied clauses
is smaller than ǫm. Since OPT > m/2, we get the approximation guarantee.
If ψ >D is the larger side, we use a random assignment. This way, at most ǫm/2
clauses from ψ <d are violated, and in expectation at most a 2−D fraction of clauses
from ψ >D are violated. Since 2−D is smaller than ǫ/4, we conclude that – together with
unsatisfied clauses due to applying Corollary 3.3 – at least (1 − ǫ)m clauses are satisfied
in expectation.
This finishes the analysis of unbalanced formulas, and in the remaining proof we may
assume that ψ is ǫ/2-balanced. To handle this case, we determine a set of variables Y
such that
◦ there are at most ǫm/4 short clauses with variables from Y and
◦ there are at most ǫ2 m long clauses that contain ≤ 1/ǫ variables from Y .
Before we construct Y , let us verify that the properties of Y imply the correctness
of the theorem. Our algorithm computes a satisfying assignment of the short clauses
without variables from Y , again using the result of Gurski and Wanke [16]. Afterwards
it assigns values uniformly at random to the variables in Y .
There are at most ǫ′ m = ǫ2 m unsatisfied clauses due to applying Corollary 3.3, ǫm/4
short clauses clauses that we did not consider when satisfying clauses from ψ <d , and
ǫ2 m clauses from ψ >D that we did not consider in the random assignment. Additionally,
in expectation there are less than 2−1/ǫ m clauses left unsatisfied from the remaining
|ψ >D | − ǫ2 m clauses from ψ >D . Since we assumed that ǫ < 1/8, the theorem follows.
To construct the set Y , we iteratively apply Lemma 3.4 with the parameter ǫ/4.
Initially, we set ψ̂ = ψ >D . In each iteration, we identify a variable y according to the
lemma and add the variable to Y . In the subsequent iterations, we mark y to be inactive
and handle it as if it was not contained in any clause. Whenever we identify a clause C
that has at least 1/ǫ inactive variables (i. e., variables from Y ), we remove C from ψ̂. We
continue this process until |ψ̂| ≤ ǫ2 . Note that applying Lemma 3.4 for ǫ/4 but having
an ǫ′ -well separated formula ensures that at all times, all clauses in ψ̂ have sufficiently
many literals to apply Lemma 3.4. Therefore the process terminates and the generated
set Y has the aimed-for properties since |Y | ≤ m/ǫ.

3.2 Hardness parameterized by neighborhood diversity
A constraint on r variables is a relation R ⊆ {0, 1}r . We define the unary constraints
U0 = {0} and U1 = {1}, which corresponds to clauses (¬x) and (x), respectively. We

10

define the equality = and disequality 6= constraints on two groups of Boolean variables
x = x1 . . . xn and y = y1 . . . yn in infix notation in the usual way: For an assignment a
to the x- and y-variables, we say that a |= x = y if and only if, for all i ∈ [n], we have
a(xi ) = a(yi ), that is, the assignment sets xi to the same value as yi ; as usual, x 6= y is
interpreted as the negation of x = y.
Lemma 3.5. CNF-SAT parameterized by nd∗ is W[1]-hard, where nd∗ is the neighborhood diversity of the input’s incidence graph.
Proof. We devise an FPT-reduction from k-Multicolored Clique to CNF-SAT. Given a
k-partite graph G, whose parts V1 , . . . , Vk all have the same size n, we construct k groups
of variables x1 , . . . , xk , which together are supposed to represent a k-clique in G, should
one exist. Each group xi consists of log n Boolean variables and represents the supposed
clique’s vertex in the part Vi . Without loss of generality, we assume that log n is an
integer.
Starting from the empty CNF formula, we construct a formula φ on the x-variables as
follows. First choose, for each i ∈ [k], an arbitrary bijection bini : Vi → {0, 1}log n that
maps any vertex u ∈ Vi to its binary representation bin(u); for convenience, we drop the
index i. For each i, j ∈ [k] with i < j, and for each non-edge (u, v) 6∈ E(Vi , Vj ) between
Vi and Vj , we add the following constraint Ci,j,u,v to φ:
xi xj 6= bin(u)bin(v) .
Clearly, this constraint excludes exactly one of the 22 log n possible assignments to xi xj ,
and so it can be written as an OR of literals of the x-variables. In the end, φ is a CNF
formula with |E(G)| clauses.
For the completeness of the reduction, let vi ∈ Vi for all i ∈ [k] be such that v1 , . . . , vk
is a clique in G. For all i ∈ [k], set xi = bin(vi ). This assignment satisfies all constraints:
for all (u, v) 6∈ E(Vi , Vj ), we have that bin(vi )bin(vj ) 6= bin(u)bin(v) because (vi , vj ) is
an edge and (u, v) is not, and bin is a bijection.
For the soundness of the reduction, let a1 , . . . , ak ∈ {0, 1}k log n be a satisfying assignment of φ. For each i ∈ [k], let vi be the unique vertex in Vi for which bin(vi ) = ai . Let
i, j ∈ [k] with i < j. Since the assignment satisfies all constraints of φ, it must be the
case that (vi , vj ) is an edge in G. For if it was a non-edge, its corresponding constraint
in φ would have excluded the assignment ai aj for xi xj . Hence v1 , . . . , vk is a clique in G.
It remains to argue that the neighborhood diversity of the incidence graph of φ is at
most k + k2 . The modules of the incidence graph are the variable group xh for each
h ∈ [k] and the clause group {Ci,j,u,v } for each i, j ∈ [k] with i < j. Indeed, the incidence
graph between xh and Ci,j,∗,∗ is a bipartite clique if h ∈ {i, j}, and otherwise it is an
independent set.
We constructed an FPT-reduction from the W[1]-complete problem Multicolored Clique
to CNF-SAT parameterized by nd∗ , which finishes the proof of the theorem.

11

4 From Treewidth to Clique-width
In the previous section, we have seen that MAX-CNF-SAT is fixed-parameter tractable
when parameterized by tw∗ , which is a sparse graph parameter, and it is W[1]-hard
to compute exactly and has an FPT-AS when parameterized by cw∗ , which is a dense
graph parameter. In this section we observe that the transition from sparse to dense
parameters has different effects on the complexity of MAX-CSP, depending on which
types of constraints are allowed.
By modifying our reduction for CNF-SAT we show that MAX-DNF-SAT, the problem
of maximizing the number of satisfied AND constraints is W[1]-hard parameterized by
nd∗ . Furthermore, because the maximum number of constraints that could be satisfied
in our reduction is also bounded by some function of the parameter, we show that the
problem does not have an FPT-AS unless FPT=W[1]. Thus, while MAX-DNF-SAT is
FPT parameterized by tw∗ , it does not even appear to have an FPT approximation
scheme when parameterized by nd∗ .
Theorem 4.1. Suppose that there exists an FPT-AS which, given ǫ > 0 and an instance φ of MAX-DNF-SAT, computes a (1 − ǫ)-approximate solution and runs in time
f (nd∗ , ǫ) · poly(n), where nd∗ is the neighborhood diversity of the incidence graph of φ.
Then FPT = W[1].
Proof. We devise an FPT-reduction from k-Multicolored Clique that is similar to the
one in our proof of Theorem 3.5.
Given a k-partite graph G whose parts V1 , . .. , Vk have size n each, we construct k
groups x1 , . . . , xk of log n variables each, and k2 groups of AND constraints Ci,j,u,v for
each integers i, j ∈ [k] with i < j and edge (u, v) ∈ E(Vi , Vj ) between Vi and Vj :
xi xj = bin(u)bin(v)
Here, bin(u) ∈ {0, 1}log n is some binary representation of u ∈ Vi . Note that the constraint Ci,j,u,v is satisfied by exactly one of the 22 log n assignments to the variables xi xj ,
and so this constraint can be written as an AND of literals of these variables. Apart
from producing
φ, the reduction also sets the approximation parameter ǫ = k−2 so that


(1 − ǫ) k2 > k2 − 1 holds. The neighborhood diversity of the incidence graph of φ is at

most k + k2 by a completely analogous argument as in the proof of Theorem 3.5.
We now prove that an FPT-AS for MAX-DNF-SAT would allow us to distinguish
whether G has a k-clique or not. For the completeness of the reduction, let G have a
k-clique v1 , . . . , vk . Then the assignment x1 . . . xk = bin(v1 ) . . . bin(vk ) satisfies the k2
constraints Ci,j,vi ,vj for each i, j ∈ [k] with i < j. Thus the assumed FPT-AS will return


a solution that satisfies at least (1 − ǫ) k2 > k2 − 1 constraints. Since the number of


satisfied constraints is an integer, it must thus be at least k2 (and in fact is equal to k2

in this case). For the soundness, if G has no k-clique, then at most k2 − 1 constraints
can be simultaneously satisfied, and so the assumed FPT-AS can not return a solution
whose value is larger than that.

12

Finally, note that the overall algorithm above solves the Multicolor Clique problem in
time f (nd∗ , ǫ) poly(n) ≤ g(k) poly(n), which is FPT; thus an FPT-AS for MAX-DNF-SAT
would imply that FPT = W[1].
When parameterized by tw∗ , MAX-CNF-SAT and MAX-DNF-SAT are both FPT,
and when parameterized by a dense graph parameter, such as nd∗ , the former problem
is hard but approximable while the latter problem is hard even to approximate. We
next consider natural constraint types where the corresponding CSPs stay FPT both for
sparse as well as dense incidence graph parameters. MAX-PARITY wants to find an
assignment that satisfies the maximum number of linear equations modulo two. While
deciding whether there is an assignment that satisfies all equations is in P (by Gauss
elimination), the maximization version is a typical APX-hard problem [18]. Here we show
that computing the optimal solution of MAX-PARITY is FPT, regardless of whether the
parameter is the treewidth or the clique-width of the incidence graph. Our intuition for
why MAX-PARITY appears to be so much easier than CNF-SAT is that negations are
(almost) irrelevant, and so the incidence graph seems to capture most of the structure
relevant to the complexity of the CSP instance.
Theorem 4.2. Given an instance φ for MAX-PARITY, we can find an optimal solution
in time f (cw∗ )|φ|O(1) , where cw∗ is the clique-width of the incidence graph of φ.
Proof. We rely on the meta-theorem of [5] that all problem which can be expressed in
the optimization version of CMSO1 can be solved exactly in linear time. In the logic
CMSO1 , we are allowed to express problems via first-order formulas with additional
second-order quantifiers that are only allowed to quantify over subsets of the universe
of the input structure, and with counting constraints that stipulate the cardinalities of
these sets modulo a constant number.
To express MAX-PARITY in CMSO1 , observe that when given a linear equation
P
(either xi or 1 − xi = 1 + xi ),
i li = b over GF(2), where b ∈ {0, 1} and the li are literals
P
we may view it equivalently as a constraint of the form i xi = b′ , where all the xi are
variables and b′ = b if and only if the original constraint contains an even number of
negated literals on the left hand side.
Having performed the above pre-processing we can now express our problem in CMSO1 .
The structure we construct is a bipartite directed graph G with the bipartition L ∪˙ R,
P
which is represented by an edge relation E. For each linear equation i xi = b, we
introduce a vertex ℓ in L, for each variable we introduce a vertex xi in R, and we set
E(ℓ, xi ) if and only if xi appears in equation ℓ. Moreover, we have the unit constraints
U0 and U1 , and we set Ub (ℓ) if and only if b is the right-hand side of ℓ.
The CMSO1 formula that we construct is looking for the largest set S ⊆ L of constraintvertices such that there exists a set of variables X ⊆ R which satisfies the following: every
vertex ℓ ∈ S where Ub (ℓ) holds has a number of neighbors in X that is equal to b modulo
two, for every b ∈ {0, 1}. By construction, the maximum such set S corresponds to the
maximum set of linear equations that can be satisfied simultaneously by an assignment
represented by X.

13

5 Majority and Threshold CSPs
In this section we deal with CSPs where each constraint is a MAJORITY or a THRESHOLD constraint. In this problem, each constraint is supplied with an integer value t (the
threshold) and it is satisfied if and only if at least t of its literals are set to true. MAJORITY is the special case of this predicate where t is always equal to half the arity
of each constraint. We denote the resulting satisfiability problem with MAJORITY
and THRESHOLD, and the resulting MAX-CSPs with MAX-MAJORITY and MAXTHRESHOLD.
MAJORITY and THRESHOLD constraints are of course some of the most natural and
well-studied predicates in many contexts: for example, MAX-CSP for such constraints
contains the complexity of finding an assignment that satisfies as many inequalities
as possible in a 0-1 Integer Linear Program whose coefficients are in {−1, 0, 1}. This
problem, sometimes called Maximum Feasible Subset has been well-studied in the
literature [9, 3, 2]. MAJORITY constraints also play a central role in learning theory
[10, 17] and in hardness of approximation [7].

5.1 Hardness of exact algorithms
We consider the problem whether a CSP with THRESHOLD constraints is satisfiable.
This problem is NP-complete. We parameterize the problem by the size fvs∗ of the
smallest feedback vertex set, or by the neighborhood diversity nd∗ of the instance’s
incidence graph. As we will see, these parameterized problems turn out to be hard, even
for the special case of MAJORITY constraints. Thus, neither dense nor sparse incidence
graph parameters appear to put the problem in FPT.
In order to ease notation in the upcoming proofs, we note that THRESHOLD-constraints
are quite expressive. For example, they can express clauses ℓ1 ∨ · · · ∨ ℓd since this is the
same as requiring that at least one of the d literals is true. Similarly, stipulating that
at least d literals be true is the same as a term ℓ1 ∧ · · · ∧ ℓd . Finally, we can stipulate
AT-MOST-ONE(ℓ1 , . . . , ℓd ), that is, that at most one of the literals is set to true, by
using the THRESHOLD-constraint that at least d − 1 of the literals ¬ℓ1 , . . . , ¬ℓd are
true.
Theorem 5.1. THRESHOLD parameterized by fvs∗ is W[1]-hard.
Proof. We reduce from the k-Multicolored Clique problem. Let G(V1 , . . . , Vk , E) be a
k-partite graph with |Vi | = n for each i ∈ {1, . . . , k}, and we regard the vertices of Vi
to be identified with integers from 1 to n. Let Eij be the edge set between Vi and Vj
for every 1 ≤ i < j ≤ k. We construct the output formula φ of THRESHOLD using the
following gadgets for every i and every pair 1 ≤ i < j ≤ k:
◦ Vertex selection gadget for Vi : For each vertex ℓ ∈ Vi , we create a sequence of ℓ
variables Pℓ for φ and name the first and the last variable in the sequence pℓ and
p′ℓ respectively (in particular, if ℓ = 1, we have p1 = p′1 ). For every two consecutive
variables y, z ∈ Pℓ , we add an OR-constraint C = (y ∨ ¬z). These constraints

14

guarantee that, in any satisfying assignment and for every ℓ, if p′ℓ is set to true,
then all variables in Pℓ , including pℓ , are set to true as well.
Given the n variable sets P1 , . . . , Pn , we add two constraints Xi and Yi as follows:
Xi = AT-MOST-ONE(pℓ : ℓ ∈ Vi ) and

Yi = AT-LEAST-ONE(p′ℓ : ℓ ∈ Vi ) .

The constraint Yi enforces at least one p′ℓ is set to true, which propagates through
all variables in Pℓ to pℓ . Conversely, the constraint Xi requires that at most one
pℓ be set to true. Hence, any satisfying assignment will have exactly one ℓ ∈ Vi for
which pℓ is set to true; moreover, all variables in the set Pℓ are set to true, and all
the variables in Pℓ′ for ℓ′ ∈ Vi \ {ℓ} are set to false.
◦ Edge selection gadget for Eij : The gadget for Eij is similar to that for Vi . For
each edge e = (k, ℓ) ∈ Eij with k ∈ Vi and ℓ ∈ Vj , we create a sequence of
n + 1 − ℓ variables Qe and name the first and the last variable in the sequence
qe and qe′ respectively. For every two consecutive variables y, z ∈ Qe , we add an
OR-constraint C = (y ∨ ¬z). Given the variable sets Qe for each e ∈ Eij , we add
two constraints Xij and Yij as follows:
Xij = AT-MOST-ONE(qe : e ∈ Eij ) and

Yij = AT-LEAST-ONE(qe′ : e ∈ Eij ) .

By the same argument as for the vertex selection gadget, we have exactly one
variable qe set to true, in which case all variables of Qe are set to true and all
variables in Qe′ are set to false for all e′ 6= e.
◦ Incidence verification gadget between Vi and Eij : For every edge e = kℓ ∈ Eij with
k ∈ Vi , we create an OR-constraint Cke = (pk ∨ ¬qe ). This guarantees that any
satisfying assignment that sets qe to true also sets pk to true.
′
◦ Incidence verification gadget between Vj and Eij : We add two constraints Cij , Cij
and their t-values as



Cij = AT-LEASTn+1 


′
Cij
= AT-MOSTn+1 

[

Qe ∪

[



e∈Eij

ℓ∈Vj

[

[

e∈Eij

Qe ∪

ℓ∈Vj

Pℓ  , and


Pℓ  .

Any satisfying assignment will thus set exactly n + 1 variables to true among all
the variables in the Qe sets for e ∈ Eij and the Pℓ sets for ℓ ∈ Vj . In particular,
there must be a natural number ℓ such that ℓ of the true variables are in the P -sets,
and n + 1 − ℓ of the true variables are in the Q-sets. By the constraints on the
P -variables, the set of true variables is equal to exactly one of the sets Pℓ′ . Since
|Pℓ′ | = ℓ′ for all ℓ′ ∈ {1, . . . , n}, we have that ℓ > 0 and that the selected set is
exactly Pℓ . Moreover, exactly one of the sets Qe is selected due to the constraints
on the Qe -variables. Since n + 1 = |Qe | + |Pℓ | = |Qe | + ℓ holds if and only if e = kℓ
for some for some k ∈ Vi , the selected set Qe must correspond to an edge e incident
to ℓ ∈ Vj .

15

For the completeness of the reduction, let S be a k-clique of G. Then we set all ℓ
variables of Pℓ from the vertex selection gadget for Vi to true if ℓ ∈ Vi is chosen for the
k-clique S. Also we set all n + 1 − ℓ variables of Qe , where e = (k, ℓ), from the edge
selection gadget for Eij to true if k ∈ Vi and ℓ ∈ Vj are chosen for S. It is not difficult
to check that this assignment satisfies φ.
Conversely, suppose φ has a satisfying assignment. From the above argument, for each
Vi there is exactly one variable set to true among all pℓ ’s for 1 ≤ ℓ ≤ n. Likewise, for each
Eij , exactly one variable qe is selected. From the property of the incidence verification
gadget between Vi and Eij , whenever qe from the edge selection gadget for Eij is selected,
pk such that k is the vertex in Vi incident with e in G must be set to true. Lastly, by
the property of incidence verification gadget between Vj and Eij , that qe with e = (k, ℓ)
is selected implies that exactly ℓ variables are set to true in the vertex selection gadget
for Vj . From the property of the vertex selection gadget, this means that Pℓ is selected
and thus pℓ is set to true. Hence, for every e = (k, ℓ) ∈ Eij , whenever qe is set to true,
both pk and pℓ are set to true. By selecting the vertices of G corresponding to k ∈ Vi
such that pk is set to true, we find a k-clique of G.
Consider the set of constraints
′
F = {Xi , Yi : 1 ≤ i ≤ k} ∪ {Xij , Yij , Cij , Cij
: 1 ≤ i < j ≤ k}.

Consider the graph obtained by deleting F from the incidence graph of φ. Each component involves a variable set Pk , for some vertex k ∈ Vi , and Qe for all edges e = (k, ℓ)
such that ℓ ∈ Vj for some j > i. It is easy to see that each component is in fact a graph
obtained by subdividing edges of a star. Hence the incidence graph of φ has a feedback
vertex set of size O(k2 ). This completes the proof.
Theorem 5.2. MAJORITY parameterized by fvs∗ is W[1]-hard, where fvs∗ is the minimal size of a feedback vertex set of the instance’s incidence graph.
Proof. We devise an FPT-reduction from THRESHOLD to MAJORITY that keeps fvs∗
the same. The result then follows from Theorem 5.1.
The reduction’s input is a CSP φ with threshold constraints, and the output is a
CSP φ′ with majority constraints. We transform threshold into majority constraints by
adding fresh variables, some of which are forced to be either true or false.
Without loss of generality, we may assume that the arity of each constraint C in φ is
even; if C has odd number of literals, we add a dummy variable y to C as a positive
literal and add a new constraint (¬y) with threshold equal to 1. Notice that this does
not change (∗ fvs). Clearly, the output instance is satisfiable if and only if the original
instance is satisfiable.
For each constraint C that has the threshold t(C) = |C|/2 + d for some integer d, we
add 2|d| fresh dummy variables y1 , . . . , y2|d| as positive literals to obtain a constraint C ′
whose threshold we set to t(C ′ ) = |C ′ |/2 = |C|/2 + |d|; thus, C ′ is a majority constraint,
and we include it into φ′ . If d > 0, we additionally add the constraint (¬yi ) for each
i ∈ [d] to force the dummy variables to be false. If d < 0, we add the constraints (yi ) for
each i ∈ [d] to force the dummy variables to be true.

16

For the correctness of the reduction, note that any satisfying assignment of φ′ sets any
dummy variable y to false if φ′ contains the constraint (¬y) since y occurs exactly once
as a positive literal. Likewise, any satisfying assignment of φ′ sets any dummy variable
y to true if φ′ contains the constraint (y). Thus, any assignment to the old variables
satisfies a constraint C if and only if setting the y-variables as just specified sets at least
half of the literals in C ′ to true. Thus φ is satisfiable if and only if φ′ is.
Adding new variables to a constraint corresponds to adding leaves to the corresponding
constraint vertex in the incidence graph, which does not create any new cycles. Adding
a single unit clause for a y-variable also does not create new cycles as this just adds a leaf
to some leaf. Thus fvs∗ (φ) = fvs∗ (φ′ ), and our reduction has the claimed properties.
Theorem 5.3. THRESHOLD and MAJORITY parameterized by the incidence neighborhood diversity nd∗ are W[1]-hard.
Proof. First note that OR-constraints are special cases of THRESHOLD-constraints,
and so the hardness of THRESHOLD follows from Lemma 3.5, where we establish
the hardness of CNF-SAT. Next we reduce from CNF-SAT to MAJORITY so that
the the neighborhood diversity of the new instance is linearly bounded by that of the
original instance. For this, let ϕ be a CNF-formula and consider its incidence graph
with neighborhood diversity k. Let G1 , . . . , Gt be the t ≤ k modules corresponding to
constraints of ϕ. That is, every constraint in Gi depends on the same set of vertices,
and in particular, every constraint in Gi has the same arity ai . Now for each i, we
add a set Zi of ai − 1 fresh dummy variables as well as the constraints (z) forcing
all z ∈ Zi to true. We convert each constraint of Gi to a MAJORITY-constraint by
adding the variable set Zi to every constraint in Gi . Since the z ∈ Zi are forced to true,
each constraint always contains ai − 1 variables set to true among its 2ai − 1 variables.
Thus the new MAJORITY-constraint is satisfied if and only if the old OR-constraint
was. The reductions adds at most k groups Zi of variables, which form modules in the
incidence graph, and so the incidence neighborhood diversity of the output instance is
at most 2k.

5.2 Exact Algorithm parameterized by vertex cover
Motivated by the negative result of Theorem 5.2 we now investigate the complexity
of MAJORITY for more restricted parameters. The first parameter we consider is the
vertex cover of the incidence graph. This is a natural, though quite restrictive, parameter
which is often considered for problems which are W-hard for treewidth.
Theorem 5.4. MAX-THRESHOLD parameterized by the incidence vertex cover vc∗
is FPT.
Proof. Given a CSP φ with THRESHOLD-constraints over a variable set X, and a
size-k vertex cover S of the incidence graph, we define SX , Sφ ⊆ S to be the vertices
of S corresponding to variables and constraints, respectively. The algorithm starts by
branching into 2|SX | ≤ 2k cases, corresponding to truth assignments σ on the variables
in SX . Since S is a vertex cover, all variables of constraints C ∈ φ \ Sφ are contained

17

in SX , and so we can compute how many of these constraints are satisfied by σ; let’s
call this number Nσ . After fixing the variables in SX and removing the constraints in
φ \ Sφ , what remains is a CSP φ′ with at most k constraints. Let Nσ′ be the maximum
number of constraints that can be simultaneously satisfied in φ′ . Then maxσ Nσ + Nσ′
is the maximum number of constraints of φ that can be simultaneously satisfied. Thus
it remains to compute Nσ′ in FPT-time.
Let φ′ be a MAX-CSP with k constraints. We reduce it to 2k instances φ′′ of the
standard CSP-version of THRESHOLD, by guessing for each constraint whether or not
it is satisfied by an optimal solution. The size of the largest subset of constraints that can
be simultaneously satisfied is then precisely the optimal value of the MAX-CSP-instance.
Finally, to solve THRESHOLD, we further reduce φ′′ to an integer linear program
(ILP) with 3k variables. This suffices since solving ILPs is FPT when parameterized by
the number of variables [22]. Let k be the number of constraints of φ′′ . We associate
with each variable x of φ′′ the vector v(x) ∈ {−1, 0, 1}k with



1

if x occurs positively in the i-th constraint,
v(x)i = −1 if x occurs negatively in the i-th constraint, and


0
if x does not occur in the i-th constraint.
For each vector v ∈ {−1, 0, +1}k , we add a variable ℓv to the ILP and the constraints
0 ≤ ℓv ≤ Bv , where Bv ∈ N is the number of variables x with v(x) = v. The variable
ℓv is supposed to indicate how many of the variables of type v are set to true. Finally,
we translate each constraint Ci ∈ φ′′ to a linear equation. Let Ti be the threshold of the
constraint, and let ni be the number of variables that occur as negative literals in Ci .
Then we add the following inequality to the ILP:


X





ℓv − n i −
k

X



ℓv ≥ Ti .

(1)

k

v∈{−1,0,1}
vi =−1

v∈{−1,0,1}
vi =1

To prove the completeness of this reduction, let φ′′ have a satisfying assignment σ.
Then we set ℓv to be the number of variables x with v(x) = v such that σ(x) = 1. This
satisfies 0 ≤ ℓv ≤ Bv . All other linear constraints are generated from some constraint Ci
of φ′′ , which is satisfied by σ. The first term in the difference of (1) is exactly the number
of variables x that are set to true under σ and that occur positively in Ci , and the second
term is the number of variables x that are set to false and that occur negatively in Ci ;
thus, the left-hand side is the number of literals set to true and the right-hand side is
the threshold of Ci , and so (1) holds.
For the soundness, assume there is a solution (ℓv )v for the ILP. Then we construct
an assignment σ as follows: For each v, arbitrarily select ℓv of the Bv variables with
v(x) = v to true, and set the others to false. Then for each constraint Ci of φ′′ , the linear
constraint (1) guarantees that Ci is satisfied. This finishes the correctness proof of the
final reduction; overall, we solve MAX-THRESHOLD in FPT-time when parameterized
by vc∗ .

18

5.3 Approximation Algorithm parameterized by feedback vertex set
The results of Theorem 5.2 naturally pose the following question: can we evade the
W-hardness of MAJORITY by designing an FPT-AS for the problem? In this section,
though we do not resolve this question, we give some first positive indication that this
may be possible. We consider MAX-MAJORITY parameterized by the incidence graph’s
feedback vertex set. This is a natural, well-studied parameter that generalizes vertex
cover but is a restriction of treewidth. It is also connected to the concept of back-door
sets to acyclicity, which is well-studied in the parameterized CSP literature [24, 13].
Observe that approximating this CSP is non-trivial, since MAX-MAJORITY with
constraints of arity two already generalizes Max-2SAT, and is hence APX-hard. On
the other hand, MAX-MAJORITY can easily be 2-approximated by considering any
assignment and its negation. Hence, the natural goal here is an approximation ratio of
(1 − ǫ). Using Corollary 5.4 as a sub-routine we achieve this with an FPT-AS.
Lemma 5.5. There exists a polynomial-time algorithm that, given an instance φ of
MAX-THRESHOLD whose incidence graph is acyclic, finds an optimal assignment to
φ. Furthermore, there is a truth assignment satisfying at least half of the constraints
simultaneously.
Proof. We assume that the incidence graph is connected since the application of an
algorithm for each connected components will lead to an optimal solution to the original
instance. We may assume that there is no isolated vertex or a constraint vertex whose
threshold is equal to zero: if one exists, we can remove the corresponding variable or
constraint without changing the set of optimal solutions.
Consider the incidence graph as a tree each rooted at a variable vertex. Pick a variable
vertex v which is farthest from the root. Let C1 , . . . , Cp (possibly p = 0) be the children
of v. All of C1 , . . . , Cp are exactly the constraints of the form (v) or (¬v) since they are
leaves of the tree and thus contain no variable other than v. Furthermore, there is no
other constraint having v as the sole literal: the only remaining constraint, if one exists,
is the parent C of v and C must be incident with another variable vertex since C cannot
be the root. We set the variable v either to true or false so as to maximize the number
of satisfied constraints among C1 , . . . , Cp . If there is a tie, that is, if p = 0 or there are
equal number of constraints of the form (v) and (¬v), then (i) if v is not the root, we set
v so that v appears in its parent C as a true literal, (ii) otherwise, we set v arbitrarily.
After setting the assignment to v, we remove v and decrease by one the threshold of
all constraints in which v appears as a true literal (and remove all isolated vertices and
constraint vertices whose threshold becomes zero). We repeat the procedure until the
incidence graph becomes empty.
Clearly, the above procedures finds an optimal assignment when v is the root. Suppose
that v is not the root and we set v to true. Let φ′ be the resulting instance. We claim
that for any assignment to φ′ , additionally setting v to true satisfies as many constraints
of φ as setting v to false. Indeed, the claim holds if C, the parent of v, is satisfied by
the extended assignment. If C is not satisfied by the extended assignment, notice that
this is because there are strictly more constraints of the form (v) than those of the form

19

(¬v). Hence, the claim holds in this case as well. A symmetric argument holds when we
set v to false. It follows that the above algorithm finds an optimal assignment to φ in
polynomial time.
Notice that at every step we choose a variable vertex v and set the assignment at v,
at least half of the constraints which are removed at the end of the step are satisfied.
The second part of the statement follows.
Theorem 5.6. There exists an FPT-AS which, given ǫ > 0 and an instance φ of MAXMAJORITY, computes a (1−ǫ)-approximate solution and runs in time f (fvs∗ , ǫ)·poly(n),
where fvs∗ is the size of the smallest feedback vertex set of the incidence graph of φ.
Proof. If |φ| ≤ (1 + 2/ǫ)k, the the number of constraints is bounded by a function of k
and ǫ, and we can use the FPT-algorithm from Theorem 5.4.
Therefore, we assume that |φ| > (1 + 2/ǫ)k. With a similar argument as in the proof
of Theorem 5.4 we can consider that the fvs(G∗φ ) contains only constraint vertices (that
is, we guess the assignment of variables in the feedback vertex set). We now proceed by
simply deleting these constraints from the instance, and let φ′ be the resulting instance.
Note that the incidence graph of φ′ is acyclic. We invoke the polynomial-time algorithm
of Lemma 5.5 to find an optimal assignment to φ′ .
Call the produced solution SOL(φ) and the optimal solution OPT(φ). From the
optimality of the solution on φ′ , we have: OPT(φ) ≥ OPT(φ′ ) ≥ OPT(φ) − k. Now,
observe that OPT(φ′ ) ≥ |φ′ |/2 by Lemma 5.5. Therefore OPT(φ) > k/ǫ which gives
OPT−k
OPT > 1 − ǫ.

References
[1] M. Alekhnovich and A. A. Razborov. Satisfiability, branch-width and Tseitin tautologies. Computational Complexity, 20(4):649–678, 2011.
[2] E. Amaldi and V. Kann. The complexity and approximability of finding maximum
feasible subsystems of linear relations. Theor. Comput. Sci., 147(1&2):181–210,
1995.
[3] E. Amaldi and V. Kann. On the approximability of minimizing nonzero variables
or unsatisfied relations in linear systems. Theor. Comput. Sci., 209(1-2):237–260,
1998.
[4] P. Austrin and S. Khot. A characterization of approximation resistance for even
k-partite csps. In R. D. Kleinberg, editor, Innovations in Theoretical Computer
Science, ITCS ’13, Berkeley, CA, USA, January 9-12, 2013, pages 187–196. ACM,
2013.
[5] B. Courcelle, J. A. Makowsky, and U. Rotics. Linear time solvable optimization
problems on graphs of bounded clique-width. Theory Comput. Syst., 33(2):125–150,
2000.

20

[6] N. Creignou. A dichotomy theorem for maximum generalized satisfiability problems.
Journal of Computer and System Sciences, 51(3):511–522, 1995.
[7] A. De, E. Mossel, and J. Neeman. Majority is stablest: discrete and sos. In D. Boneh,
T. Roughgarden, and J. Feigenbaum, editors, Symposium on Theory of Computing
Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 477–486. ACM,
2013.
[8] R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Texts
in Computer Science. Springer, 2013.
[9] K. M. Elbassioni, R. Raman, S. Ray, and R. Sitters. On the approximability of
the maximum feasible subsystem problem with 0/1-coefficients. In C. Mathieu,
editor, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete
Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 1210–
1219. SIAM, 2009.
[10] V. Feldman, V. Guruswami, P. Raghavendra, and Y. Wu. Agnostic learning of
monomials by halfspaces is hard. SIAM J. Comput., 41(6):1558–1590, 2012.
[11] R. Ganian. Twin-cover: Beyond vertex cover in parameterized algorithmics. In
D. Marx and P. Rossmanith, editors, Proceedings of the 6th International Symposium on Parameterized and Exact Computation (IPEC), volume 7112, pages 259–
271, 2011.
[12] S. Gaspers and S. Szeider. Kernels for global constraints. In T. Walsh, editor, IJCAI
2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, pages 540–545. IJCAI/AAAI,
2011.
[13] S. Gaspers and S. Szeider. Backdoors to acyclic SAT. In A. Czumaj, K. Mehlhorn,
A. M. Pitts, and R. Wattenhofer, editors, Automata, Languages, and Programming
- 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, volume 7391 of Lecture Notes in Computer Science, pages 363–374.
Springer, 2012.
[14] S. Gaspers and S. Szeider. Guarantees and limits of preprocessing in constraint
satisfaction and reasoning. Artif. Intell., 216:1–19, 2014.
[15] M. Grohe. The structure of tractable constraint satisfaction problems. In
R. Kralovic and P. Urzyczyn, editors, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006, Proceedings, volume 4162 of Lecture Notes in Computer
Science, pages 58–72. Springer, 2006.
[16] F. Gurski and E. Wanke. The tree-width of clique-width bounded graphs without
Kn, n . In U. Brandes and D. Wagner, editors, Graph-Theoretic Concepts in Computer Science, 26th International Workshop, WG 2000, Konstanz, Germany, June

21

15-17, 2000, Proceedings, volume 1928 of Lecture Notes in Computer Science, pages
196–205. Springer, 2000.
[17] V. Guruswami and P. Raghavendra. Hardness of learning halfspaces with noise.
SIAM J. Comput., 39(2):742–765, 2009.
[18] J. Håstad. Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001.
[19] S. Khanna, M. Sudan, and D. P. Williamson. A complete classification of the
approximability of maximization problems derived from boolean constraint satisfaction. In F. T. Leighton and P. W. Shor, editors, Proceedings of the Twenty-Ninth
Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May
4-6, 1997, pages 11–20. ACM, 1997.
[20] S. Khot and R. Saket. Approximating csps using LP relaxation. In M. M. Halldórsson, K. Iwama, N. Kobayashi, and B. Speckmann, editors, Automata, Languages,
and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan,
July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer
Science, pages 822–833. Springer, 2015.
[21] M. Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica,
64(1):19–37, 2012.
[22] H. W. Lenstra Jr. Integer programming with a fixed number of variables. Mathematics of operations research, 8(4):538–548, 1983.
[23] D. Marx. Parameterized complexity and approximation algorithms. Comput. J.,
51(1):60–78, 2008.
[24] S. Ordyniak, D. Paulusma, and S. Szeider. Satisfiability of acyclic and almost acyclic
CNF formulas. Theor. Comput. Sci., 481:85–99, 2013.
[25] D. Paulusma, F. Slivovsky, and S. Szeider. Model counting for CNF formulas of
bounded modular treewidth. In N. Portier and T. Wilke, editors, STACS 2013,
February 27 - March 2, 2013, Kiel, Germany, volume 20 of LIPIcs, pages 55–66.
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013.
[26] R. Pichler, S. Rümmele, S. Szeider, and S. Woltran. Tractable answer-set programming with weight constraints: bounded treewidth is not enough. TPLP, 14(2):141–
164, 2014.
[27] S. H. Sæther, J. A. Telle, and M. Vatshelle. Solving maxsat and #sat on structured
CNF formulas. In C. Sinz and U. Egly, editors, SAT 2014 - Vienna, Austria, July
14-17, 2014. Proceedings, volume 8561 of Lecture Notes in Computer Science, pages
16–31. Springer, 2014.
[28] M. Samer and S. Szeider. Constraint satisfaction with bounded treewidth revisited.
J. Comput. Syst. Sci., 76(2):103–114, 2010.

22

[29] T. J. Schaefer. The complexity of satisfiability problems. In R. J. Lipton, W. A.
Burkhard, W. J. Savitch, E. P. Friedman, and A. V. Aho, editors, Proceedings of
the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San
Diego, California, USA, pages 216–226. ACM, 1978.
[30] F. Slivovsky and S. Szeider. Model counting for formulas of bounded clique-width.
In L. Cai, S. Cheng, and T. W. Lam, editors, ISAAC 2013, Hong Kong, China,
Proceedings, volume 8283 of Lecture Notes in Computer Science, pages 677–687.
Springer, 2013.
[31] S. Szeider.
On fixed-parameter tractable parameterizations of SAT.
In
E. Giunchiglia and A. Tacchella, editors, Theory and Applications of Satisfiability
Testing, 6th International Conference, SAT 2003. Santa Margherita Ligure, Italy,
May 5-8, 2003 Selected Revised Papers, volume 2919 of Lecture Notes in Computer
Science, pages 188–202. Springer, 2003.
[32] S. Szeider.
Not so easy problems for tree decomposable graphs.
abs/1107.1177, 2011.

CoRR,

[33] S. Szeider. The parameterized complexity of constraint satisfaction and reasoning.
In H. Tompits, S. Abreu, J. Oetsch, J. Pührer, D. Seipel, M. Umeda, and A. Wolf,
editors, INAP 2011, and WLP 2011, Vienna, Austria, September 28-30, 2011, Revised Selected Papers, volume 7773 of Lecture Notes in Computer Science, pages
27–37. Springer, 2011.
[34] S. Szeider. The parameterized complexity of k-flip local search for SAT and MAX
SAT. Discrete Optimization, 8(1):139–145, 2011.
[35] L. Trevisan. Inapproximability of combinatorial optimization problems. Electronic
Colloquium on Computational Complexity (ECCC), 2004.

23

