Complexity and Approximability of Parameterized MAX-CSPs

1]Holger Dell
2]Eun Jung Kim
3]Michael Lampis
4]Valia Mitsou[Supported by ERC Starting Grant PARAMTIGHT (No. 280152)]
5]Tobias Mömke[This research is supported by
Deutsche Forschungsgemeinschaft grant BL511/10-1]

[1]
Saarland University and Cluster of Excellence, Saarbrücken

Université Paris Dauphine

[4]
SZTAKI, Hungarian Academy of Sciences, Budapest

[5]
Saarland University, Saarbrücken

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
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

We consider Max-CSPs with the constraint types , , , and ,
and with various parameters $k$, and we attempt to fully classify them into the
following three cases:

* The exact optimum can be computed in $\FPT$ time.

* It is $\W[1]$-hard to compute the exact optimum, but there is a randomized
$\FPT$ approximation scheme (), which computes a
$(1-\epsilon)$-approximation in time $f(k,\epsilon) \cdot \poly(n)$.

* There is no  unless $\FPT=\W[1]$.

For the corresponding standard CSPs, we establish $\FPT$ vs. $\W[1]$-hardness

§ INTRODUCTION

Constraint Satisfaction Problems (s) play a central role in almost all
branches of theoretical computer science. Starting from , the prototypical
NP-complete problem, the computational complexity of s has been widely
studied from various points of view. In this paper we focus on two aspects of
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 s.

Parameterized Complexity. For a parameterized problem $P$, an instance of $P$
is a pair $(x,k) \in \Sigma^*\times \mathbb{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)\cdot |x|^{O(1)})$ for some computable function $f$. Such an algorithm is called an -algorithm.

For two parameterized problems $P$ and $Q$, a parameterized reduction from $P$ to $Q$ is an -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' \le g(k)$ for some computable function $g$. The notion of paramterized reduction defines the hierarchy of parameterized complexity classes
$$\FPT=W[0] \subseteq \W[1] \subseteq \W[2] \subseteq \cdots \subseteq \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 \neq W[1]$. Further  parameterized complexity terminology used in this paper can be found in [8].

Parameterized s. The vast majority of interesting s
are -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  problems for a large range of parameters is given. In
this paper we focus on structurally parameterized s, that is, we
consider s 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  using a (hyper-)graph and leverage the powerful tools
commonly applied to parameterized graph problems (such as tree decompositions)
to solve the .

The typical goal of this line of research is to find the most general
parameterization of a  that still remains fixed-parameter tractable ($\FPT$).
To give a concrete example for a very well-known ,  is $\FPT$ when
parameterized by the treewidth of its incidence graph[See the next
section for a definition of incidence graphs] [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)  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  jumps from
being $\FPT$ to being $\W$-hard. It is of course a natural question how we can deal
with the $\W$-hard cases of a  once they are identified.

Approximation. s also play a central role in the theory
of (polynomial-time) approximation algorithms [35, 20, 4]. In this context we
typically consider a  as an optimization problem () 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 s 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.
2 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 s 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
s where the constraints are respectively , ,  and 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  when parameterized by various graph widths.
The new ingredient in our approach is that, in addition to trying to determine
which parameters make a  $\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 s for which
$\W$-hardness can be (almost) circumvented using approximation, and others which
are inapproximable.

More specifically, our results are as follows: for  constraints, which
corresponds to the standard  () 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 diversity[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.]. 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
($\FPTAS$)[We follow here the standard definition of $\FPTAS$ given in
[23].] for  parameterized by clique-width, that is, an algorithm
which for all $\epsilon>0$ runs in time $f(k,\epsilon)n^{O(1)}$ and returns an
assignment satisfying $(1-\epsilon)\mathrm{OPT}$ clauses. Thus, even though we
establish that solving  exactly is $\W$-hard even for extremely restricted
dense graph parameters,  is well-approximable even in the quite
general case of clique-width. To the best of our knowledge, this is the first
approximation result of this type for a $\W$-hard  problem.

Recalling that  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
and , 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  constraints remains $\FPT$ even for dense
parameters such as clique-width. On the other hand, by modifying our reduction for , we are
able to show not only that maximizing the number of satisfied constraints is $\W[1]$-hard parameterized by neighborhood diversity, but
also that this problem cannot even admit an $\FPTAS$ (like ), unless
W[1]=$\FPT$. We recall that  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 s with  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  is $\FPT$ parameterized by
incidence vertex cover. Then, we use this algorithm as a sub-routine to obtain
an $\FPTAS$ for incidence feedback vertex set. Both of these algorithmic
results also apply to the more general case of  constraints. We leave it
as an interesting open problem to examine if the
approximation algorithm for feedback vertex set can be extended to treewidth.

ref/.style =

[rounded corners]
[fill=hard] (cw) at (0,0) ;
[fill=easy] (tw) at (1,1) ;
[fill=easy] (fvs) at (3,1) ;
[fill=hard,label=[ref]above:L<ref>] (nd) at (2,0)
[fill=easy] (vc) at (4,0) ;
[draw,latex-] (cw) – (tw);
[draw,latex-] (tw) – (fvs);
[draw,latex-] (fvs) – (vc);
[draw,latex-] (cw) – (nd);
[draw,latex-] (nd) – (vc);

at (2,-1) CNF-SAT;

[rounded corners]
[fill=hard] (cw) at (0,0) ;
[fill=hard] (tw) at (1,1) ;
[fill=hard,label=[ref]above:T<ref>] (fvs) at (3,1) ;
[fill=hard,label=[ref]above:T<ref>] (nd) at (2,0) ;
[fill=easy] (vc) at (4,0) ;
[draw,latex-] (cw) – (tw);
[draw,latex-] (tw) – (fvs);
[draw,latex-] (fvs) – (vc);
[draw,latex-] (cw) – (nd);
[draw,latex-] (nd) – (vc);

at (2,-1) MAJORITY-CSP;

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 $\p{\fvs} \rightarrow \p{\tw}$ for CNF-SAT indicates that there is a
reduction from CNF-SAT parameterized by $\p{\fvs}$ to CNF-SAT parameterized by
$\p{\tw}$. In fact, the reductions we depict here are trivial since, for
example, $\p{\fvs}$ is bounded by a function of $\p{\tw}$.

[rounded corners]
[fill=medium,label=[ref]above:T<ref>] (cw) at (0,0)
[fill=easy] (tw) at (1,1) ;
[fill=easy] (fvs) at (3,1) ;
[fill=medium] (nd) at (2,0) ;
[fill=easy] (vc) at (4,0) ;
[draw,latex-] (cw) – (tw);
[draw,latex-] (tw) – (fvs);
[draw,latex-] (fvs) – (vc);
[draw,latex-] (cw) – (nd);
[draw,latex-] (nd) – (vc);

at (2,-1) MAX-CNF-SAT;

[rounded corners]
[pattern=north east lines,pattern color=medium] (cw) at (0,0) ;
[pattern=north east lines,pattern color=medium] (tw) at (1,1) ;
[fill=medium,label=[ref]above:T<ref>] (fvs) at (3,1) ;
[pattern=north east lines,pattern color=medium] (nd) at (2,0) ;
[fill=easy,label=[ref]above:T<ref>] (vc) at (4,0) ;
[draw,latex-] (cw) – (tw);
[draw,latex-] (tw) – (fvs);
[draw,latex-] (fvs) – (vc);
[draw,latex-] (cw) – (nd);
[draw,latex-] (nd) – (vc);

at (2,-1) MAX-MAJORITY-CSP;

[rounded corners]
[fill=hard] (cw) at (0,0) ;
[fill=easy] (tw) at (1,1) ;
[fill=easy] (fvs) at (3,1) ;
[fill=hard,label=[ref]above:T<ref>] (nd) at (2,0) ;
[fill=easy] (vc) at (4,0) ;
[draw,latex-] (cw) – (tw);
[draw,latex-] (tw) – (fvs);
[draw,latex-] (fvs) – (vc);
[draw,latex-] (cw) – (nd);
[draw,latex-] (nd) – (vc);

at (2,-1) MAX-DNF-SAT;

[rounded corners]
[fill=easy,label=[ref]above:T<ref>] (cw) at (0,0) ;
[fill=easy] (tw) at (1,1) ;
[fill=easy] (fvs) at (3,1) ;
[fill=easy] (nd) at (2,0) ;
[fill=easy] (vc) at (4,0) ;
[draw,latex-] (cw) – (tw);
[draw,latex-] (tw) – (fvs);
[draw,latex-] (fvs) – (vc);
[draw,latex-] (cw) – (nd);
[draw,latex-] (nd) – (vc);

at (2,-1) MAX-PARITY-CSP;

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
Red means that the problem is W[1]-hard to compute exactly, and
there is no  unless $\cc{FPT}=\cc{W[1]}$.
Blue means that the problem is W[1]-hard to compute exactly, and
there is an .
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 .

§ PRELIMINARIES

Boolean . A Boolean Constraint Satisfaction Problem,  in short, $\psi$ is defined as a set $\set{ C_1, \ldots, C_m}$ of $m$
constraints over a set $X(\psi)=\set{x_1,\dotsc,x_n}$ of $n$ variables and
their negations.  Each constraint $C_i$ is regarded as a function of literals
(positive or negative appearances of variables) mapped to the set $\set{0,1}$,
where literals can take the values $0$ or $1$. Furthermore, we define $|C_j|$
to denote the arity of constraint $C_j$ (the number of literals that occur in
$C$) and $|\psi|=m$ the number of constraints in $\psi$. For simplicity, we
also write $l_i \in C_j$ for a literal $l_i$ and a constraint $C_j$ if $l_i$
appears in $C_j$.

We will be dealing with Boolean  for four
well-studied Boolean functions:  constraints,  constraints, (or ) constraints and  constraints. We say that an assignment
$t:X\rightarrow\set{0,1}$ satisfies a constraint $C$ of type:

* , if $\exists l_i \in C$, $t(l_i)=1$;

* , if $\forall l_i \in C$, $t(l_i)=1$;

* , if it satisfies some equation $\Sigma_{l_i\in C} t(l_i) = b$ (for
$b\in\{0,1\}$) modulo 2;

* , if at least $\lceil\sfrac{|C|}{2}\rceil$ literals in $C$ are set
to $1$. More generally, we may consider  constraints, where a certain
threshold number of literals must be set to true to satisfy the constraint.

Let $\occ(\psi)=\sum_{C \in \psi} |C|$ be the total number of variable
occurrences in $\psi$, that is, the total size of the formula.
For a variable $x$, we write $\psi_x$ for the set of all constraints $C\in\psi$
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 $|\psi_x|$.

We are dealing also with s, where given a set of constraints $\psi$, 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  constraints, the  and  problems correspond to
the more widely known  and  problems.  In this case we call the
constraints clauses. When the constraint function is , the problem is called .  In that case, the constraints are called
terms. The problem  is also known as MAX-LIN-2
(satisfy a maximum number of given linear equations modulo 2).

Incidence graph and structural parameters. For a  $\psi$, the incidence graph $\G{\psi}$
is defined as the bipartite graph where we construct one vertex $v_i$ for each
(unsigned) variable $x_i$ and one vertex $u_j$ for each constraint $C_j$ and
connect $v_i$ with $u_j$ if $x_i \in C_j$.

We are interested in parameterizations of the incidence graph $\p[\G{\psi}]{\op{p}}$
(or simply $\p{\op{p}}$ if $\G{\psi}$ is clear from the context), where
$\op{p}$ is a structural parameter of $\G{\psi}$.  We are mostly interested in
the two most widely studied graph parameters, treewidth $\p{\tw}$ and
clique-width $\p{\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 $\p{\nd}$.
A graph $G(V,E)$ has neighborhood diversity $\nd(G) = k$ if we can partition
$V$ into $k$ sets $V_1, \dots, V_k$ such that, for all $v\in V$ and all
$i\in\{1,\dots,k\}$, either $v$ is adjacent to every vertex in $V_i$ 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 $\p{\vc}$ and
the feedback vertex set number $\p{\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.

(cw) at (0,0) ;
(tw) at (1,1) ;
(fvs) at (3,1) ;
(nd) at (2,0) ;
(vc) at (4,0) ;
[draw,latex-] (cw) – (tw);
[draw,latex-] (tw) – (fvs);
[draw,latex-] (fvs) – (vc);
[draw,latex-] (cw) – (nd);
[draw,latex-] (nd) – (vc);

The structural parameters we study and their relationships.
For example, the arrow between $\p\cw$ and $\p\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:\mathbf N\to\mathbf N$
so that $\p\cw\le f(\p\tw)$.
On the other hand,  and  as well as  and  cannot be
bounded by each other in general.

§  AND

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, s of literals.
An optimal solution for  can be computed in $\FPT$ when parameterized by
the treewidth $\p{\tw}$ of the incidence graph [1], and hence  can
be solved in the same time.
When parameterized by the clique-width $\p{\cw}$ of the incidence graph, all
known exact algorithms for  and  run in $\XP$ time [30, 27].
Moreover, we do not expect these problems to be in  since they are both
$\W[1]$-hard parameterized by $\p{\cw}$ [25].

In Section <ref>, we construct an approximation scheme for  that
runs in $\FPT$ time.
Intuitively, our algorithm works as follows: given a formula $\phi$ 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 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 <ref>, 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  to $\W[1]$.
To this end, we have to look for a graph parameter that is bounded by a function
of $\p\cw$ (where the problem is hard) but can leave the $\p\tw$ unbounded (where it's
In fact, [25] shows that the problem is $\W[1]$-hard parameterized by
the modular incidence treewidth $\p\mtw$, which lies between
$\p\cw$ and $\p\tw$.
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.
We study the incidence neighborhood diversity $\p{\nd}$, which is
incomparable to $\p{\tw}$; however, $\p{\mtw}$ is bounded when $\p{\nd}$ is.
We prove that  remains $\W[1]$-hard parameterized by $\p{\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 $\p{\mtw}\le k$ because
contracting all modules leaves a graph of order at most $k$, which
trivially has treewidth at most $k$.

§.§ Approximation Algorithm parameterized by

There is a randomized algorithm such that, for every $\epsilon >0$ and given a CNF formula $\psi$ with $n$
variables, $m$ clauses, and incidence clique-width $\cw$, runs in time $f(\epsilon,\cw)
\cdot \poly(n+m)$, and outputs a truth assignment that satisfies
at least $(1-\epsilon)\cdot \mathrm{OPT}$ clauses in expectation.

We formulate the following basic lemma about probability distributions.

For all $\epsilon,L > 0$ there is a $c=c(\epsilon,L)>0$ such that all $c' \ge c$ and all
sequences $p_1,\dots,p_{c'} \geq 0$ with $\sum_{i=1}^{c'} p_i \leq 1$ have an index $d\leq
c/L$ with the property

\[
p_{[d,L\cdot d]} \doteq \sum_{j=d}^{L\cdot d} p_j < \epsilon\,.
\]

Let $\epsilon,L>0$.
We set $c=c(\epsilon,L)$ below.
Assume for contradiction that $p_{[d,L\cdot d]}\geq \epsilon$ holds for all
$d\in [1,c/L]$.
If there are $1/\epsilon + 1$ disjoint intervals $[a_1,L\cdot
a_1],\dots,[a_{1/\epsilon+1},L\cdot a_{1/\epsilon+1}]\subseteq [1,c]$,
then we arrive at a contradiction with the fact that the $p_i$'s are
non-negative and sum to at most one.
Clearly there exists a constant $c=c(\epsilon,L)$ such that $1/\epsilon + 1$
disjoint intervals of the form $[a,La]$ fit into $[1,c]$.
This proves the claim.

For an arbitrary given $\epsilon>0$, we fix $L=\epsilon^{-4}$.
We use Lemma <ref> as follows:
For a CNF formula $\psi$, we define $p_i$ as the fraction of clauses of
size $i$, that is,

\begin{align*}
p_i \doteq \frac{\Bigl|\setc[\Big]{ C\in\psi}{|C|=i}\Bigr|}{\abs{\psi}}\,.
\end{align*}

Then Lemma <ref> gives us a number $d\leq c(\epsilon)$ such that
the total fraction of clauses whose size is between $d$ and $\epsilon^{-4}d$ is
bounded by $\epsilon$.
It is now natural to partition all clauses into short, medium, and long clauses.
More precisely, we define $\psi=\psi^{<d}\dotcup\psi^{[d,D]}\dotcup\psi^{>D}$
for $D=\epsilon^{-4}d$ as follows:

\begin{align*}
\psi^{<d}&\doteq\setc[\Big]{C\in\psi}{ \abs{C} < d }\,,\\
\psi^{[d,D]}&\doteq\setc[\Big]{C\in\psi}{ d \leq \abs{C} \leq D}\,,
\text{and}\\
\psi^{>D}&\doteq\setc[\Big]{C\in\psi}{ \abs{C} > D}\,.
\end{align*}

An immediate corollary to Lemma <ref> is thus that we can choose
$d\leq c(\epsilon)$ in such a way that $|\psi^{[d,D]}|\leq \epsilon |\psi|$.

For all $\epsilon > 0$ there is some $c=c(\epsilon)>0$ such that all CNF
formulas $\psi$ have some $d=d(\epsilon)\in[1,c]$ with
\abs{\psi^{[d,\epsilon^{-4}d]}} \leq \epsilon \cdot |\psi|\,.

If $\psi^{[d,D]}=\emptyset$ holds for $D=\epsilon^{-4}d$ and
$d\in[1,c(\epsilon)]$, we say that $\psi$ is $\epsilon$-well separated.
We call $\psi$ $\epsilon'$-balanced if, in addition, we have
$|\psi^{<d}|\ge\epsilon'm$ and $|\psi^{>D}| \ge \epsilon' m$.

Let $\psi$ be an $\epsilon$-well separated formula (and thus $V=V(\psi^{<d}) \cup

Then, for each subset $\hat{\psi} \subseteq \psi^{>D}$ with $|\hat{\psi}| >
\epsilon^2 m$, there is a variable $y$ such that
$|\psi^{<d}_y| \le \epsilon^2 |\hat{\psi}_y|$.

That is, for every set $\hat\psi$ that contains a significant fraction of long
clauses, there is a variable that occurs $\abs{\hat\psi_y}$ times in $\hat\psi$,
but only at most an $\epsilon^2$-fraction of that in the short clauses.

Let $\hat\psi\subseteq\psi^{>D}$ with $\abs{\hat\psi} > \epsilon^2m$.
Note that the total number of literal occurrences in $\hat\psi$ is
$\occ(\hat{\psi}) > D \cdot \epsilon^2 \cdot m = \epsilon^{-2} d m$.
In contrast, $\occ(\psi^{<d}) < d m$.
Now suppose that there was no variable $y$ with the claimed properties, that
is, suppose that every variable $y$ satisfies $\abs{\psi^{<d}_y} > \epsilon^2
\abs{\hat\psi_y}$.
Then the total number of variable occurrences in $\psi^{<d}$ can be bounded from below as

\[
\occ(\psi^{<d})=\sum_{y} \abs{\psi^{<d}_y} > \sum_{y} \epsilon^2
|\hat{\psi}_{y}| = \epsilon^2 \occ(\hat{\psi}) > d\cdot m\,.
\]

This yields a contradiction and thus proves the claim.

The algorithm $A$ works as follows.
Let $\epsilon' = \epsilon^2$, and we assume w.l.o.g. that $\epsilon < 1/8$.
Given a CNF formula $\phi$, we compute an $\epsilon'$-well separated formula
$\psi$ by dropping all clauses in $\phi^{[d,D]}$.
Corollary <ref> guarantees that the fraction of deleted clauses
is bounded by $\epsilon'$.
If $\psi$ is not $\epsilon/2$-balanced, we discard the smaller side (with fewer clauses)
and only handle the larger one:
If $\psi^{<d}$ is the larger side, we compute an optimal assignment for
$\psi^{<d}$ in FPT time, by using the result of Gurski and Wanke [16].
This way the total number of unsatisfied clauses is at most $\epsilon m/2$, and together with
the unsatisfied clauses due to applying Corollary <ref>, the total number of unsatisfied clauses is smaller than  $\epsilon m$. Since $\mathrm{OPT} > m/2$, we get the approximation guarantee.

If $\psi^{>D}$ is the larger side, we use a random assignment.
This way, at most $\epsilon m/2$ clauses from $\psi^{<d}$ are violated, and in expectation
at most a $2^{-D}$ fraction of clauses from $\psi^{>D}$ are violated. Since $2^{-D}$ is smaller than $\epsilon/4$,
we conclude that – together with unsatisfied clauses due to applying Corollary <ref> – at least
$(1-\epsilon)m$ clauses are satisfied in expectation.

This finishes the analysis of unbalanced formulas, and in the remaining proof we may assume that
$\psi$ is $\epsilon/2$-balanced.
To handle this case, we determine a set of variables $Y$ such that

* there are at most $\epsilon m/4$ short clauses with variables from $Y$ and

* there are at most $\epsilon^2 m$ long clauses that contain $\le 1/\epsilon$ 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 $\epsilon' m = \epsilon^2 m$ unsatisfied clauses due to applying Corollary <ref>,
$\epsilon m/4$ short clauses clauses that we did not consider when satisfying clauses from $\psi^{<d}$,
and $\epsilon^2 m$ clauses from $\psi^{>D}$ that we did not consider in the random assignment. Additionally,
in expectation there are less than $2^{-1/\epsilon}m$ clauses left unsatisfied from the
remaining $|\psi^{>D}| - \epsilon^2 m$ clauses from $\psi^{>D}$. Since we assumed that $\epsilon < 1/8$, the theorem follows.

To construct the set $Y$, we iteratively apply Lemma <ref> with the parameter $\epsilon/4$.
Initially, we set $\hat\psi = \psi^{>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/\epsilon$ inactive variables (i. e., variables from $Y$),
we remove $C$ from $\hat\psi$.
We continue this process until $|\hat\psi| \le \epsilon^2$.
Note that applying Lemma <ref> for $\epsilon/4$ but having an $\epsilon'$-well separated formula ensures that at all times,
all clauses in $\hat\psi$ have sufficiently many literals to apply Lemma <ref>.
Therefore the process terminates and the generated set $Y$ has the aimed-for properties since $|Y| \le m/\epsilon$.

§.§ Hardness parameterized by neighborhood

A constraint on $r$ variables is a relation $R\subseteq\{0,1\}^r$.
We define the unary constraints $U_0=\{0\}$ and $U_1=\{1\}$, which corresponds
to clauses $(\neg x)$ and $(x)$, respectively.
We define the equality $=$ and disequality $\neq$ constraints on two groups of
Boolean variables $x = x_1 \dots x_n$ and $y= y_1\dots y_n$ in infix notation in
the usual way:
For an assignment $a$ to the $x$- and $y$-variables, we say that $a \models x=y$
if and only if, for all $i\in[n]$, we have $a(x_i)=a(y_i)$, that is, the
assignment sets $x_i$ to the same value as $y_i$; as usual, $x\neq y$ is
interpreted as the negation of $x=y$.

CNF-SAT parameterized by $\p{\nd}$ is $\W[1]$-hard, where $\p{\nd}$ is the
neighborhood diversity of the input's incidence graph.

We devise an FPT-reduction from  to CNF-SAT.
Given a $k$-partite graph $G$, whose parts $V_1,\dots,V_k$ all have the same
size $n$, we construct $k$ groups of variables $x_1,\dots,x_k$, which together
are supposed to represent a $k$-clique in $G$, should one exist.
Each group $x_i$ consists of $\log n$ Boolean variables and represents the
supposed clique's vertex in the part $V_i$.
Without loss of generality, we assume that $\log n$ is an integer.

Starting from the empty CNF formula, we construct a formula $\phi$ on the
$x$-variables as follows.
First choose, for each $i\in[k]$, an arbitrary bijection $\mathrm{bin}_i : V_i
\to \{0,1\}^{\log n}$ that maps any vertex $u\in V_i$ to its binary
representation $\mathrm{bin}(u)$; for convenience, we drop the index $i$.
For each $i,j\in[k]$ with $i < j$, and for each non-edge $(u,v)\not\in
E(V_i,V_j)$ between $V_i$ and $V_j$, we add the following constraint
$C_{i,j,u,v}$ to $\phi$:

\[
x_ix_j \neq \mathrm{bin}(u)\mathrm{bin}(v)\,.
\]

Clearly, this constraint excludes exactly one of the $2^{2\log n}$ possible
assignments to $x_ix_j$, and so it can be written as an OR of literals of the
In the end, $\phi$ is a CNF formula with $|E(G)|$ clauses.

For the completeness of the reduction, let $v_i\in V_i$ for all $i\in[k]$ be
such that $v_1,\dots,v_k$ is a clique in $G$.
For all $i\in[k]$, set $x_i = \mathrm{bin}(v_i)$.
This assignment satisfies all constraints: for all $(u,v)\not\in E(V_i,V_j)$,
we have that $\mathrm{bin}(v_i)\mathrm{bin}(v_j)\neq
\mathrm{bin}(u)\mathrm{bin}(v)$ because $(v_i,v_j)$ is an edge and $(u,v)$ is
not, and $\mathrm{bin}$ is a bijection.

For the soundness of the reduction, let $a_1,\dots,a_k\in\{0,1\}^{k\log n}$ be
a satisfying assignment of $\phi$.
For each $i\in[k]$, let $v_i$ be the unique vertex in $V_i$ for which
$\mathrm{bin}(v_i) = a_i$.
Let $i,j\in[k]$ with $i < j$.
Since the assignment satisfies all constraints of $\phi$, it must be the case
that $(v_i,v_j)$ is an edge in $G$.
For if it was a non-edge, its corresponding constraint in $\phi$ would have
excluded the assignment $a_ia_j$ for $x_ix_j$.
Hence $v_1,\dots,v_k$ is a clique in $G$.

It remains to argue that the neighborhood diversity of the incidence graph
of $\phi$ is at most $k + \binom{k}{2}$.
The modules of the incidence graph are the variable group $x_h$ for each
$h\in[k]$ and the clause group $\{C_{i,j,u,v}\}$ for each $i,j\in [k]$ with $i
< j$.
Indeed, the incidence graph between $x_{h}$ and $C_{i,j,*,*}$ is a bipartite
clique if $h\in\{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 $\p{\nd}$, which finishes the proof of the

§ FROM TREEWIDTH TO CLIQUE-WIDTH

In the previous section, we have seen that  is fixed-parameter tractable
when parameterized by $\p{\tw}$, which is a sparse graph parameter, and it is
W[1]-hard to compute exactly and has an $\FPTAS$ when parameterized by $\p{\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 , depending on which types of
constraints are allowed.

By modifying our reduction for  we show that , the problem of
maximizing the number of satisfied  constraints is W[1]-hard parameterized by
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 $\FPTAS$ unless FPT=W[1].
Thus, while  is FPT parameterized by $\p{\tw}$, it does not even appear to
have an FPT approximation scheme when parameterized by $\p{\nd}$.

Suppose that there exists an $\FPTAS$ which, given $\epsilon >0$ and an
instance $\phi$ of , computes a $(1-\epsilon)$-approximate solution and
runs in time $f(\p{\nd},\epsilon)\cdot \poly(n)$, where $\p{\nd}$ is the
neighborhood diversity of the incidence graph of $\phi$.
Then $\FPT = \W[1]$.

We devise an -reduction from  that is similar to the one in our proof
of Theorem <ref>.

Given a $k$-partite graph $G$ whose parts $V_1,\dots,V_k$ have size $n$ each,
we construct $k$ groups $x_1,\dots,x_k$ of $\log n$ variables each, and
$\binom{k}{2}$ groups of  constraints $C_{i,j,u,v}$ for each integers
$i,j\in[k]$ with $i < j$ and edge $(u,v) \in E(V_i,V_j)$ between $V_i$ and

\[
x_ix_j = \mathrm{bin}(u)\mathrm{bin}(v)
\]

Here, $\mathrm{bin}(u) \in \{0,1\}^{\log n}$ is some binary representation of
$u\in V_i$.
Note that the constraint $C_{i,j,u,v}$ is satisfied by exactly one of the
$2^{2\log n}$ assignments to the variables $x_ix_j$, and so this constraint
can be written as an AND of literals of these variables.
Apart from producing $\phi$, the reduction also sets the approximation
parameter $\epsilon = k^{-2}$ so that $(1-\epsilon) \binom{k}{2} >
\binom{k}{2} - 1$ holds.
The neighborhood diversity of the incidence graph of $\phi$ is at most
$k+\binom{k}{2}$ by a completely analogous argument as in the proof of
Theorem <ref>.

We now prove that an $\FPTAS$ for $\MDNF$ 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
Then the assignment $x_1 \dots x_k =
\mathrm{bin}(v_1) \dots \mathrm{bin}(v_k)$ satisfies the $\binom{k}{2}$
constraints $C_{i,j,v_i,v_j}$ for each $i,j\in[k]$ with $i<j$.
Thus the assumed $\FPTAS$ will return a solution that satisfies at least
$(1-\epsilon)\binom{k}{2} > \binom{k}{2}-1$ constraints.
Since the number of satisfied constraints is an integer, it must thus be at
least $\binom{k}{2}$ (and in fact is equal to $\binom{k}{2}$ in this case).
For the soundness, if $G$ has no $k$-clique, then at most $\binom{k}{2} - 1$
constraints can be simultaneously satisfied, and so the assumed $\FPTAS$ can
not return a solution whose value is larger than that.

Finally, note that the overall algorithm above solves the Multicolor Clique
problem in time $f(\p{\nd},\epsilon) \poly(n) \le g(k)\poly(n)$, which is
; thus an $\FPTAS$ for $\MDNF$ would imply that $\FPT=\W[1]$.

When parameterized by ,  and  are both , and when
parameterized by a dense graph parameter, such as $\p{\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 s stay
both for sparse as well as dense incidence graph parameters.
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  is FPT, regardless of
whether the parameter is the treewidth or the clique-width of the incidence
Our intuition for why  appears to be so much easier than  is that
negations are (almost) irrelevant, and so the incidence graph seems to capture
most of the structure relevant to the complexity of the  instance.

Given an instance $\phi$ for , we can find an optimal solution in time
$f(\p{\cw})|\phi|^{O(1)}$, where $\p{\cw}$ is the clique-width of the
incidence graph of $\phi$.

We rely on the meta-theorem of [5] that all problem which can be
expressed in the optimization version of CMSO$_1$ can be solved exactly in
linear time.
In the logic CMSO$_1$, 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  in CMSO$_1$, observe that when given a linear equation
$\sum_i l_i = b$ over $\operatorname{GF}(2)$, where $b\in\{0,1\}$ and the
$l_i$ are literals (either $x_i$ or $1-x_i = 1+x_i$), we may view it
equivalently as a constraint of the form $\sum_i x_i = b'$, where all the
$x_i$ 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
The structure we construct is a bipartite directed graph $G$ with the
bipartition $L\dotcup R$, which is represented by an edge relation $E$.
For each linear equation $\sum_i x_i = b$, we introduce a vertex $\ell$
in $L$, for each variable we introduce a vertex $x_i$ in $R$, and we set
$E(\ell,x_i)$ if and only if $x_i$ appears in equation $\ell$.
Moreover, we have the unit constraints $U_0$ and $U_1$, and we set $U_b(\ell)$
if and only if $b$ is the right-hand side of $\ell$.

The CMSO$_1$ formula that we construct is looking for the largest set
$S\subseteq L$ of constraint-vertices such that there exists a set of
variables $X\subseteq R$ which satisfies the following: every vertex $\ell\in
S$ where $U_b(\ell)$ holds has a number of neighbors in $X$ that is equal
to $b$ modulo two, for every $b\in\{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$.

§ MAJORITY AND THRESHOLD CSPS

In this section we deal with CSPs where each constraint is a  or a 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.  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  and , and the
resulting s with  and .

and  constraints are of course some of the most natural and
well-studied predicates in many contexts: for example,  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].  constraints also play a central role in learning theory [10, 17]
and in hardness of approximation [7].

§.§ Hardness of exact algorithms

We consider the problem whether a CSP with  constraints is satisfiable.
This problem is -complete.
We parameterize the problem by the size $\p{\fvs}$ of the smallest feedback
vertex set, or by the neighborhood diversity $\p{\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  constraints.
Thus, neither dense nor sparse incidence graph parameters appear to put the
problem in .

In order to ease notation in the upcoming proofs, we note that -constraints
are quite expressive.
For example, they can express clauses
$\ell_1 \vee\dots\vee \ell_d$
since this is the same as requiring that at least one of the $d$ literals is
Similarly, stipulating that at least $d$ literals be true is the same as a term
Finally, we can stipulate AT-MOST-ONE$(\ell_1,\dots,\ell_d)$, that is, that at
most one of the literals is set to true, by using the -constraint that at
least $d-1$ of the literals $\neg\ell_1,\dots,\neg\ell_d$ are true.

parameterized by $\p{\fvs}$ is $\W[1]$-hard.

We reduce from the  problem.
Let $G(V_1,\ldots , V_k,E)$ be a $k$-partite graph with $\abs{V_i}=n$ for each
$i\in\{1,\dots,k\}$, and we regard the vertices of $V_i$ to be identified with
integers from 1 to $n$.
Let $E_{ij}$ be the edge set between $V_i$ and $V_j$ for every $1\leq i<j\leq
We construct the output formula $\phi$ of $\THR$ using the following gadgets for
every $i$ and every pair $1\leq i<j\leq k$:

* Vertex selection gadget for $V_i$: For each vertex $\ell \in V_i$,
we create a sequence of $\ell$ variables $P_{\ell}$ for $\phi$ and name the
first and the last variable in the sequence $p_{\ell}$ and $p'_{\ell}$
respectively (in particular, if $\ell=1$, we have $p_1=p'_1$).
For every two consecutive variables $y,z \in P_{\ell}$, we add an
OR-constraint $C=(y\vee \neg{z})$.
These constraints guarantee that, in any satisfying assignment and for every
$\ell$, if $p'_\ell$ is set to true, then all variables in $P_\ell$, including
$p_\ell$, are set to true as well.

Given the $n$ variable sets $P_1,\ldots ,P_n$, we add two constraints $X_i$
and $Y_i$ as follows:

\begin{align*}
X_i=\text{AT-MOST-ONE}(p_\ell : \ell \in V_i)
\quad \text{and} \quad
Y_i=\text{AT-LEAST-ONE}(p'_\ell :\ell \in V_i)
\,.
\end{align*}

The constraint $Y_i$ enforces at least one $p'_{\ell}$ is set to true, which
propagates through all variables in $P_\ell$ to $p_{\ell}$.
Conversely, the constraint $X_i$ requires that at most one $p_{\ell}$ be set
to true.
Hence, any satisfying assignment will have exactly one $\ell\in V_i$ for which
$p_{\ell}$ is set to true; moreover, all variables in the set $P_{\ell}$ are
set to true, and all the variables in $P_{\ell'}$ for $\ell'\in
V_i\setminus\{\ell\}$ are set to false.

* Edge selection gadget for $E_{ij}$:
The gadget for $E_{ij}$ is similar to that for $V_i$.
For each edge $e=(k,\ell) \in E_{ij}$ with $k\in V_i$ and $\ell \in V_j$, we
create a sequence of $n+1-\ell$ variables $Q_{e}$ and name the first and the
last variable in the sequence $q_{e}$ and $q'_e$ respectively.
For every two consecutive variables $y,z \in Q_{e}$, we add an OR-constraint
$C=(y\vee \neg{z})$.
Given the variable sets $Q_e$ for each $e\in E_{ij}$, we add two constraints
$X_{ij}$ and $Y_{ij}$ as follows:

\begin{align*}
X_{ij}=\text{AT-MOST-ONE}(q_e : e \in E_{ij})
\quad \text{and} \quad
Y_{ij}=\text{AT-LEAST-ONE}(q'_e :e \in E_{ij})
\,.
\end{align*}

By the same argument as for the vertex selection gadget, we have exactly one
variable $q_e$ set to true, in which case all variables of $Q_e$ are set to
true and all variables in $Q_{e'}$ are set to false for all $e'\neq e$.

* Incidence verification gadget between $V_i$ and $E_{ij}$:
For every edge $e=k\ell \in E_{ij}$ with $k\in V_i$,  we create an
OR-constraint $C_{ke}=(p_k\vee \neg{q_{e}})$.
This guarantees that any satisfying assignment that sets $q_e$ to true also
sets $p_k$ to true.

* Incidence verification gadget between $V_j$ and $E_{ij}$:
We add two constraints $C_{ij}$, $C'_{ij}$ and their $t$-values as

\begin{align*}
\text{AT-LEAST}_{n+1}
\paren*{
\bigcup_{e\in E_{ij}} Q_e \cup \bigcup_{\ell\in V_j} P_\ell
}\,, \text{and}\\
\text{AT-MOST}_{n+1}
\paren*{
\bigcup_{e\in E_{ij}} Q_e \cup \bigcup_{\ell\in V_j} P_\ell
\end{align*}

Any satisfying assignment will thus set exactly $n+1$ variables to true among
all the variables in the $Q_e$ sets for $e\in E_{ij}$ and the $P_\ell$ sets
for $\ell\in V_j$.
In particular, there must be a natural number $\ell$ such that $\ell$ of the
true variables are in the $P$-sets, and $n+1-\ell$ 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_{\ell'}$.
Since $\abs{P_{\ell'}} = \ell'$ for all $\ell'\in\{1,\dots,n\}$, we have that
$\ell>0$ and that the selected set is exactly $P_\ell$.
Moreover, exactly one of the sets $Q_e$ is selected due to the constraints on
the $Q_e$-variables.
Since $n+1 = |Q_e| + |P_\ell| = |Q_e| + \ell$ holds if and only if $e=k\ell$
for some for some $k\in V_i$, the selected set $Q_e$ must correspond to an
edge $e$ incident to $\ell\in V_j$.

For the completeness of the reduction, let $S$ be a $k$-clique of $G$. Then we
set all $\ell$ variables of $P_{\ell}$ from the vertex selection gadget for
$V_i$ to true if $\ell\in V_i$ is chosen for the $k$-clique $S$. Also we set all
$n+1-\ell$ variables of $Q_e$, where $e=(k,\ell)$,  from the edge selection
gadget for $E_{ij}$ to true if $k\in V_i$ and $\ell \in V_j$ are chosen for $S$.
It is not difficult to check that this assignment satisfies $\phi$.

Conversely, suppose $\phi$ has a satisfying assignment. From the above argument,
for each $V_i$ there is exactly one variable set to true among all $p_{\ell}$'s
for  $1\leq \ell\leq n$. Likewise, for each $E_{ij}$, exactly one variable $q_e$
is selected. From the property of the incidence verification gadget
between $V_i$ and $E_{ij}$, whenever $q_e$ from the edge selection gadget for
$E_{ij}$ is selected, $p_k$ such that $k$ is the vertex in $V_i$ incident
with $e$ in $G$ must be set to true. Lastly, by the property of incidence
verification gadget between $V_j$ and $E_{ij}$, that $q_e$ with $e=(k,\ell)$ is
selected implies that exactly $\ell$ variables are set to true in the vertex
selection gadget for $V_j$. From the property of the vertex selection gadget,
this means that $P_{\ell}$ is selected and thus $p_{\ell}$ is set to true.
Hence, for every $e=(k,\ell)\in E_{ij}$, whenever $q_e$ is set to true, both
$p_k$ and $p_{\ell}$ are set to true. By selecting the vertices of $G$
corresponding to $k\in V_i$ such that $p_k$ is set to true, we find a $k$-clique
of $G$.

Consider the set of constraints
\[F=\{X_i,Y_i:1\leq i\leq k\}\cup
\{X_{ij},Y_{ij},C_{ij},C'_{ij}:1\leq i<j\leq k\}.\]
Consider the graph
obtained by deleting $F$ from the incidence graph of $\phi$. Each component
involves a variable set $P_k$,  for some vertex $k \in V_i$, and $Q_e$ for all
edges $e=(k,\ell)$ such that $\ell \in V_j$ 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 $\phi$ has a feedback vertex set of size $O(k^2)$.
This completes the proof.

$\MAJ$ parameterized by $\p{\fvs}$ is $\W[1]$-hard, where $\p{\fvs}$ is the
minimal size of a feedback vertex set of the instance's incidence graph.

We devise an -reduction from  to  that keeps $\p{\fvs}$ the
The result then follows from Theorem <ref>.

The reduction's input is a CSP $\phi$ with threshold constraints, and the
output is a CSP $\phi'$ 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 $\phi$ 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 $(\neg y)$ with threshold equal to 1. Notice that this does not change $\p(\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) =\sfrac{|C|}{2} + d$ for some integer $d$, we
add $2|d|$ fresh dummy variables $y_1,\dots,y_{2|d|}$ as positive literals to obtain a constraint $C'$
whose threshold we set to $t(C')=\sfrac{|C'|}{2}=\sfrac{|C|}{2}+|d|$;
thus, $C'$ is a majority constraint, and we include it into $\phi'$.
If $d>0$, we additionally add the constraint $(\neg y_i)$ for each $i\in[d]$
to force the dummy variables to be false. If $d<0$, we add the constraints $(y_i)$ for each  $i\in[d]$
to force the dummy variables to be true.

For the correctness of the reduction, note that any satisfying assignment
of $\phi'$ sets any dummy variable $y$ to false if $\phi'$ contains the
constraint $(\neg y)$ since $y$ occurs exactly once as a positive literal. Likewise, any satisfying assignment of $\phi'$ sets any dummy variable $y$ to true if $\phi'$ 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 $\phi$ is satisfiable if and only if $\phi'$ 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 $\p{\fvs}(\phi)=\p{\fvs}(\phi')$, and our reduction has the claimed

and  parameterized by the incidence neighborhood diversity
$\p{\nd}$ are $\W[1]$-hard.

First note that OR-constraints are special cases of -constraints, and so
the hardness of  follows from Lemma <ref>, where we establish
the hardness of .
Next we reduce from  to  so that the the neighborhood
diversity of the new instance is linearly bounded by that of the original instance.
For this, let $\varphi$ be a CNF-formula and consider its incidence graph with
neighborhood diversity $k$.
Let $G_1,\dots,G_t$ be the $t\le k$ modules corresponding to constraints of
That is, every constraint in $G_i$ depends on the same set of vertices, and in
particular, every constraint in $G_i$ has the same arity $a_i$.
Now for each $i$, we add a set $Z_i$ of $a_i-1$ fresh dummy variables as well
as the constraints $(z)$ forcing all $z\in Z_i$ to true.
We convert each constraint of $G_i$ to a -constraint by adding the
variable set $Z_i$ to every constraint in $G_i$.
Since the $z\in Z_i$ are forced to true, each constraint always contains
$a_i-1$ variables set to true among its $2 a_i - 1$ variables.
Thus the new -constraint is satisfied if and only if the old OR-constraint
The reductions adds at most $k$ groups $Z_i$ of variables, which form modules
in the incidence graph, and so the incidence neighborhood diversity of the
output instance is at most $2k$.

§.§ Exact Algorithm parameterized by vertex cover

Motivated by the negative result of Theorem <ref> we now
investigate the complexity of  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.

parameterized by the incidence vertex cover $\p{\vc}$ is $\FPT$.

Given a  $\phi$ with -constraints over a variable set $X$, and a
size-$k$ vertex cover $S$ of the incidence graph, we define
$S_X, S_\phi \subseteq S$ to be the vertices of $S$ corresponding to variables
and constraints, respectively.
The algorithm starts by branching into $2^{\abs{S_X}}\le 2^k$ cases,
corresponding to truth assignments $\sigma$ on the variables in $S_X$.
Since $S$ is a vertex cover, all variables of constraints $C\in \phi\setminus
S_\phi$ are contained in $S_X$, and so we can compute how many of these
constraints are satisfied by $\sigma$; let's call this number $N_\sigma$.
After fixing the variables in $S_X$ and removing the constraints in
$\phi\setminus S_\phi$, what remains is a  $\phi'$ with at most $k$
Let $N'_{\sigma}$ be the maximum number of constraints that can be
simultaneously satisfied in $\phi'$.
Then $\max_\sigma N_\sigma + N'_\sigma$ is the maximum number of constraints
of $\phi$ that can be simultaneously satisfied.
Thus it remains to compute $N'_{\sigma}$ in -time.

Let $\phi'$ be a  with $k$ constraints.
We reduce it to $2^k$ instances $\phi''$ of the standard -version of ,
by guessing for each constraint whether or not it is satisfied by an optimal
The size of the largest subset of constraints that can be simultaneously
satisfied is then precisely the optimal value of the -instance.

Finally, to solve , we further reduce $\phi''$ to an integer linear
program (ILP) with $3^k$ variables.
This suffices since solving ILPs is  when parameterized by the number of
variables [22].
Let $k$ be the number of constraints of $\phi''$.
We associate with each variable $x$ of $\phi''$ the vector
$v(x)\in\set{-1,0,1}^k$ with

\begin{align*}
\begin{cases}
1 & \text{if $x$ occurs positively in the $i$-th constraint,}
\\
-1 & \text{if $x$ occurs negatively in the $i$-th constraint, and}
\\
0 & \text{if $x$ does not occur in the $i$-th constraint.}
\end{cases}
\end{align*}

For each vector $v\in\set{-1,0,+1}^k$, we add a variable $\ell_v$ to the ILP and
the constraints $0\le \ell_v \le B_v$, where $B_v\in\mathbf N$ is the number
of variables $x$ with $v(x)=v$.
The variable $\ell_v$ is supposed to indicate how many of the variables of
type $v$ are set to true.
Finally, we translate each constraint $C_i\in\phi''$ to a linear equation.
Let $T_i$ be the threshold of the constraint, and let $n_i$ be the number of
variables that occur as negative literals in $C_i$.
Then we add the following inequality to the ILP:

\begin{align}\label{eq:ILP}
\paren[\Big]{
\sum_{\substack{v\in\set{-1,0,1}^k\\v_i=1}}\ell_v
\paren[\Big]{
\sum_{\substack{v\in\set{-1,0,1}^k\\v_i=-1}}\ell_v
\ge
\,.
\end{align}

To prove the completeness of this reduction, let $\phi''$ have a satisfying
assignment $\sigma$.
Then we set $\ell_v$ to be the number of variables $x$ with $v(x)=v$ such that
This satisfies $0\le\ell_v\le B_v$.
All other linear constraints are generated from some constraint $C_i$ of
$\phi''$, which is satisfied by $\sigma$.
The first term in the difference of (<ref>) is exactly the number of
variables $x$ that are set to true under $\sigma$ and that occur positively in
$C_i$, and the second term is the number of variables $x$ that are set to
false and that occur negatively in $C_i$; thus, the left-hand side is the
number of literals set to true and the right-hand side is the threshold
of $C_i$, and so $\eqref{eq:ILP}$ holds.

For the soundness, assume there is a solution $\paren{\ell_v}_v$ for the ILP.
Then we construct an assignment $\sigma$ as follows: For each $v$, arbitrarily
select $\ell_v$ of the $B_v$ variables with $v(x)=v$ to true, and set the
others to false.
Then for each constraint $C_i$ of $\phi''$, the linear constraint
(<ref>) guarantees that $C_i$ is satisfied.
This finishes the correctness proof of the final reduction; overall, we solve
in -time when parameterized by .

§.§ Approximation Algorithm parameterized by feedback vertex set

The results of Theorem <ref> naturally pose the following question:
can we evade the W-hardness of  by designing an $\FPTAS$ 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  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  with
constraints of arity two already generalizes Max-2SAT, and is hence
On the other hand,  can easily be 2-approximated by considering
any assignment and its negation. Hence, the natural goal here is an
approximation ratio of $(1-\epsilon)$.
Using Corollary <ref> as a sub-routine we achieve this with an

There exists a polynomial-time algorithm that, given an instance $\phi$ of  whose incidence graph is acyclic,
finds an optimal assignment to $\phi$. Furthermore, there is a truth assignment satisfying at least half of the constraints simultaneously.

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 $C_1,\ldots , C_p$ (possibly $p=0$) be the children of $v$.
All of $C_1,\ldots , C_p$ are exactly the constraints of the form $(v)$ or $(\neg 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 $C_1,\ldots , C_p$. If there is a tie, that is, if $p=0$ or there are equal number of constraints
of the form $(v)$ and $(\neg 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 $\phi'$ be
the resulting instance. We claim that for any assignment to $\phi'$, additionally setting $v$ to true satisfies
as many constraints of $\phi$ 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 $(\neg 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 $\phi$ 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.

There exists an $\FPTAS$ which, given $\epsilon >0$ and an instance $\phi$ of
, computes a $(1-\epsilon)$-approximate solution and runs in time
$f(\p{\fvs},\epsilon)\cdot \poly(n)$, where $\p{\fvs}$ is the size of the
smallest feedback vertex set of the incidence graph of $\phi$.

If $|\phi|\le (1+\sfrac{2}{\epsilon})k$, the the number of constraints is
bounded by a function of $k$ and $\epsilon$, and we can use the -algorithm from Theorem

Therefore, we assume that $|\phi| > (1+\sfrac{2}{\epsilon})k$. With a similar argument as in the
proof of Theorem <ref> we can consider that the
$\fvs(\G{\phi})$ 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 $\phi'$ be the resulting instance.
Note that the incidence graph of $\phi'$ is acyclic. We invoke the polynomial-time algorithm of
Lemma <ref> to find an optimal assignment to $\phi'$.

Call the produced solution
$\textrm{SOL}(\phi)$ and the optimal solution $\textrm{OPT}(\phi)$.  From the optimality of the solution on $\phi'$, we have:
$\textrm{OPT}(\phi)\ge \textrm{OPT}(\phi')\ge \textrm{OPT}(\phi) - k$. Now, observe that $\textrm{OPT}(\phi')\ge
|\phi'|/2$ by Lemma <ref>. Therefore $\textrm{OPT}(\phi) >
k/{\epsilon}$ which gives $\frac{\textrm{OPT}-k}{\textrm{OPT}} >

[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
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
Theory Comput. Syst., 33(2):125–150, 2000.

[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
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,

[14]
S. Gaspers and S. Szeider.
Guarantees and limits of preprocessing in constraint satisfaction and
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
K\({}_{\mbox{n, n}}\).
In U. Brandes and D. Wagner, editors, Graph-Theoretic Concepts
in Computer Science, 26th International Workshop, WG 2000, Konstanz,
Germany, June 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.

[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.
CoRR, abs/1107.1177, 2011.

[33]
S. Szeider.
The parameterized complexity of constraint satisfaction and
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),