Complexity of Local Search for CSPs Parameterized by Constraint Difference

The parameterized complexity of local search, whose goal is to improve the current solution to a strictly better solution nearby, was indeed studied in the parameterized complexity literature. Fellows, Fomin, Lokshtanov, Rosamond, Saurabh, and Villanger [8] study various problems like $r$-Center, Vertex Cover, Odd Cycle Transversal, Max-Cut, and Max-Bisection on special classes of sparse graphs like planar, minor-free, and bounded-degree graphs, and Szeider [25] considers a similar framework for SAT and MaxSAT.

This (strict) local search model can be relaxed to another model called permissive local search [19]. Here we are given a solution $S$, and the goal is to find a solution $S^{\prime }$ which has lower cost (which may differ from $S$ in more than $k$ vertices), or correctly conclude that every solution which differs from $S$ in at most $k$ vertices has higher cost. This model has been studied for a few problems - including a variant of stable marriage [19], Vertex Cover [9] and also in the context of Min Ones CSPs [14], extending Marx’s complete classification of the parameterized complexity of CSPs based on if there is a solution with exactly $k$ ones [17].

One crucial difference between our model and all previous models on CSPs is how the distance between the two solutions is defined. The previous papers define it as the number of variables with different values in two solutions, but our definition concerns the set of constraints whose satisfaction changes between two solutions. In fact, recall that our definition of a solution is an arbitrary set $𝒫$ of constraints not necessarily feasible (i.e., corresponding to a variable assignment), which allows $𝒫=𝒞$ and captures algorithms parameterized by the number of unsatisfied constraints. In that sense, our model is slightly broader than traditional local search where one maintains a feasible solution and tries to strictly improve in every step.

Fixed parameter tractability of CSPs parameterized by the number of unsatisfied constraints has been an important and active research area [2, 11, 12, 13], where a complete classification for Boolean relations was obtained very recently. Their definition of CSPs is strictly more general than ours, where each constraint language contains multiple predicates, even with different arities. It is an exciting research direction to extend our framework for every CSP.

Our negative results can be interpreted as demonstrating the importance of near-perfect instances for classical FPT algorithms. For instance, we show ImproveMaxCSP(2SAT) is $W[1]$-hard while MinCSP(2SAT) is known to admit an FPT algorithm [23, 22, 6, 21], so the fact that the optimal solution indeed satisfies all but $k$ constraints affects the parameterized complexity.

There are several natural research directions based on this paper. We believe that the following directions will be interesting to study further:

1. 1.

   The most immediate one is to extend our characterization for all CSPs. One notable set of boolean relations whose complexity is still open in our model is $\{x=y,x\wedge \neg y\}$.

2. 2.

   A natural variant of our model is when the solution is represented as an assignment to the variables, which is guaranteed to have a Hamming distance at most $k$ to a strictly better solution. For Min Ones CSP, where the goal is to find a satisfying assignment with the minimum number of true variables, this variant has been studied previously [14].

3. 3.

   Other than CSPs, one framework that captures numerous results in the FPT literature is covering (resp. packing) problems, especially on graphs, where we want to select the smallest (resp. largest) subset $S\subseteq U$ subject to some covering (resp. packing) constraints. Local search naturally extends to this setting (i.e., we are given $S^{\prime }\subseteq U$ with $|S^{\prime }\mathrm{\Delta }S|\le k$), and it will be interesting to see if classical FPT results on graph covering/packing problems extend to this model, including Multicut [3, 18], Min Bisection [5], $k$-Cut [10], Disjoint Paths [24].

4. 4.

   In the approximation algorithms literature, there are numerous studies about CSPs on structured instances, most notably dense and expanding instances (see [1] and references therein). It would be interesting to see whether these structures, if suitably parameterized, help the problems become more tractable in our model.

In this section we recall basic definitions of constraint satisfaction problems.

For integer $r\in {\mathbb{N}}^{+}$, a boolean relation $R$ is a subset of ${𝔽}_2^r$. The integer $r$ is called the arity of $R$. For a boolean relation $R$ of arity $r$ and $b\in {𝔽}_2^r$, define the boolean relation $R\oplus b:=\{\alpha \oplus b\mid \alpha \in R\},$ where $\oplus$ is the addition operator over ${𝔽}_2^r$. When considering $R$ as a clause in a CSP instance, $\oplus$ operator can be seen as variable negations. For a relation $R$ with index $[r]$ and $S\subseteq [r],$ define the projection relation ${\pi }_S(R)=\{{\alpha }_S\mid \alpha \in R\}$, where ${\alpha }_S$ means extracting the value on coordinates in $S$.

A boolean relation $R$ of arity $r$ is symmetric if for all $(x_1,\mathrm{\cdots },x_r)\in {𝔽}_2^r$ and any permutation $p:[r]\to [r]$, $(x_1,\mathrm{\cdots },x_r)\in R\iff (x_{p(1)},\mathrm{\cdots },x_{p(r)})\in R$. Equivalently, $R$ is symmetric if there exists $S\subseteq \{0,1,\mathrm{\cdots },r\}$ such that $(x_1,\mathrm{\cdots },x_r)\in R\iff {\sum }_{i=1}^r{x}_i\in S$ (where the addition is performed in $\mathbb{Z}$). We define $\mathrm{SymRel}(r,S)$ to be such $R$.

A boolean constraint language is a set of boolean relations. Two constraint languages are equivalent if they contain exactly the same set of relations. A clause $C$ over a boolean constraint language $\mathrm{\Gamma }$ is a pair $(V_C,R_C)$, where $R_C\in \mathrm{\Gamma }$ and $V_C=(v_{C,1},\mathrm{\dots },v_{C,r})$ is an $r$-tuple of variables where $r$ is the arity of $R_C$. We refer to $V_C$ as the scope of the clause $C$. An assignment $\alpha :V_C\to \{0,1\}$ satisfies clause $(V_C,R_C)$ if $(\alpha (v_{C,1}),\mathrm{\dots },\alpha (v_{C,r}))\in R_C$, and $\alpha$ violates the clause otherwise.

In this paper, we only consider a restricted set of boolean constraint languages, where the language $\mathrm{\Gamma }$ includes all possible negation patterns $R\oplus b$ for some symmetric predicate $R$ of arity $r$ and $b\in {𝔽}_2^r$. We use the notation $\mathrm{SymLang}\text{-}\mathrm{N}(R)=\{R\oplus b\mid b\in {𝔽}_2^r\}$ for such $\mathrm{\Gamma }$, where $\mathrm{SymLang}\text{-}\mathrm{N}$ stands for “symmetric language with negation”. We further define $\mathrm{SymLang}\text{-}\mathrm{N}(r,S)$ to be $\mathrm{SymLang}\text{-}\mathrm{N}(\mathrm{SymRel}(r,S))$.

For a boolean constraint language $\mathrm{\Gamma }$, a $\text{CSP}(\mathrm{\Gamma })$ instance $I$ is a pair $(V_I,{𝒞}_I)$, where $V_I$ is the set of variables, and ${𝒞}_I$ is the set of clauses over the boolean constraint language $\mathrm{\Gamma }$, all of which have scope inside $V_I$. We say a variable $v$ is incident to a clause $C$ if $v$ belongs to the scope of $C$.

For an assignment $\alpha :V_I\to \{0,1\}$, define ${𝒞}_I(\alpha )$ to be the set of clauses $\alpha$ satisfies in $I$. We further define $cos{t}_I(\alpha )=|𝒞\backslash {𝒞}_I(\alpha )|$, the number of unsatisfied clauses, to be the cost of the assignment. We define the size of an instance $I$ as $\max (|V_I|,|{𝒞}_I|)$ and denote it by $n_I$. We ignore the subscripts when the instance is clear in the context.

Now we give formal definitions for the problems we consider. We first define MinCSP($\mathrm{\Gamma }$), and then define our central problem ImproveMaxCSP($\mathrm{\Gamma }$). In this paper, our main goal is to characterize the parameterized complexity of ImproveMaxCSP($\mathrm{\Gamma }$) when $\mathrm{\Gamma }=\mathrm{SymLang}\text{-}\mathrm{N}(r,S)$ for some $r\in {\mathbb{N}}^{+}$ and $S\subseteq \{0,1,\mathrm{\cdots },r\}$.

From the definition, MinCSP($\mathrm{\Gamma }$) is a special case of ImproveMaxCSP($\mathrm{\Gamma }$) by setting $𝒫$ to be the constraint set $𝒞$.

A boolean constraint language $\mathrm{\Gamma }$ is trivial if $\mathrm{\Gamma }=\mathrm{\varnothing }$ or $\mathrm{\Gamma }=\{{\{0,1\}}^r\}$ for some $r\in {\mathbb{N}}^{+}$ and nontrivial otherwise. When $\mathrm{\Gamma }$ is trivial, MinCSP($\mathrm{\Gamma }$) and ImproveMaxCSP($\mathrm{\Gamma }$) can be solved by trivial algorithms. So in the following we only consider nontrivial boolean constraint languages.

For simplicity, we abbreviate boolean constraint languages mentioned in the paper. Here we introduce the following simple but useful claim in identifying equivalence between boolean constraint languages.

Having defined our framework, we first provide the formal version of Theorem 1:

As $\text{MinCSP}(\mathrm{\Gamma })$ is a special case of ImproveMaxCSP$(\mathrm{\Gamma })$, the W[1]-hardness of the former implies that of the latter. The recent characterization of parameterized tractability of $\text{MinCSP}(\mathrm{\Gamma })$ [13] implies the following theorem.

It remains to study the remaining problems.

For ImproveMaxCSP$(r\mathit{and})$, a color-coding combined with the LP rounding for Densest Subhypergraph yields the following result proved in Section 3.

For $r\mathrm{AE}$, its tractability depends on $r$. When $r=2$, we use the celebrated unbreakability framework [10, 4, 5, 16] to design a parameterized algorithm in Section 4.

However, for $r\mathrm{AE}$ with $r\ge 3$, we show nontrivial reductions from Paired Minimum $st$-Cut to show the following hardness.

Finally, for $\le 1\text{-}\mathrm{out}\text{-}\mathrm{of}\text{-}r\mathrm{SAT}$, we prove that even the first nontrivial case $r=2$, which is equivalent to $2\mathrm{S}\mathrm{A}\mathrm{T}$, is already W[1]-hard. Even though $\text{MinCSP}(2\mathrm{S}\mathrm{A}\mathrm{T})$ is in FPT, this result follows from the (slightly informal) fact that Vertex Cover and Independent Set are equivalent in our model.

The hardness proofs can be found in the full version. It is easy to see that the other theorems imply Theorem 3 in a straightforward way.

In this section we recall basic definitions about hypergraphs. A hypergraph $H(V,E)$ is a generalization of graph where an edge can contain multiple vertices. For $e\in E$ and $v\in V$, say $v$ is incident to $e$ and $e$ is incident to $v$ if $e$ contains $v$. For a hypergraph $H$ and $V_0\subseteq V$, we denote $H(V_0)$ as the induced subhypergraph of $V_0$ in $H$, and denote $E(H(V_0))$ to be the edge set of the induced subhypergraph.

In the main algorithm in this section (provided in Theorem 14), we need to solve the following problem:

The problem is closely related to Densest Subgraph (See [15] for a survey) and has a polynomial-time algorithm based on similar algorithms for Densest Subgraph. One algorithm is to observe that $|E(H(V_0))|-{\sum }_{v\in V_0}w(v)$ is supermodular and run a submodular minimization algorithm.²²2We thank an anonymous reviewer for this observation. The below is an LP-based algorithm specific to our setting.

Given an instance $(I,k,𝒫)$, we say that $𝒫$ is satisfiable if some assignment satisfies all clauses in $𝒫$. We will give an algorithm that runs in $2^{O(k\log k)}{n}^{O(1)}$ time and solves $\text{ImproveMaxCSP}({\cup }_{r^{\prime }\le r}{r}^{\prime }\mathit{and})$ when the instance satisfies an additional promise that $𝒫$ is satisfiable.

When this additional promise is satisfied, it is easy to find an assignment satisfying all the clauses of $𝒫$ in polynomial time, so in the following we assume that the instance $(I,k,𝒫)$ is equipped with such an assignment $\alpha$. In the full version, we show how to transform any instance into instances where this additional promise is true.

Equipped with this additional assignment, we then restructure the instance in the following way: Define $k^{\prime }:=k+|𝒫\mathrm{\Delta }{C}_I(\alpha )|$ and ${𝒫}^{\prime }:=C_I(\alpha )$, and replace $(I,k,𝒫,\alpha )$ with $(I,k^{\prime },{𝒫}^{\prime },\alpha )$, to keep $𝒫$ to be maximal in accordance with $\alpha$. In other words, we reset $𝒫$ to be the set of clauses satisfied by $\alpha$. If the instance satisfies the promise (that some good assignment is close to the $𝒫$), the good assignment satisfies at most $|𝒫|+k$ clauses, which implies that $|𝒫\mathrm{\Delta }{C}_I(\alpha )|\le k$, and $k^{\prime }\le 2k$. If $k^{\prime }>2k$, we return an arbitrary assignment (to handle cases where the promise is not met).

Now we show that, there exists an good assignment close to $𝒫$ whose Hamming distance to $\alpha$ is small.

We recall useful definitions about graphs. Let $G=(V,E)$ be a multigraph, where parallel edges and loops are allowed. For two disjoint vertex sets $A,B\subseteq V$, we denote by $E(A,B)$ the set of edges between $A$ and $B$. When $(A,B)$ is a partition, then $E(A,B)$ is the set of edges in the corresponding cut. For a vertex subset $V^{\prime }\subseteq V$, we denote by $G(V^{\prime })$ the subgraph of $G$ induced by $V^{\prime }.$ We write $E(G(V^{\prime }))$ for the set of edges in $G(V^{\prime }).$ For a set $E^{\prime }\subseteq E,$ we denote by $G\setminus E^{\prime }$ the multigraph $(V,E\setminus E^{\prime }).$ For $S\subseteq V$, we let $N(S):=\{v\in V\setminus S:\exists u\in S\text{ such that }(u,v)\in E\}$ be the open neighborhood of $S$. We say two cuts $(A,B)$ and $(X,Y)$ are $k$-close if $|E(A,B)\mathrm{\Delta }E(X,Y)|\le k$. When the graph is clear in the context, we define $n=\max (|V|,|E|)$ to be the size of the graph.

Notice that we can see clauses as edges connecting variables, assigning boolean values to variables as partitioning the variable set into two sets, and the equality and non-equality constraints correspond to uncut and cut constraints respectively. This motivates us to introduce the following graph problem. Given a graph $G=(V,E)$, an edge type function $t:E\to \{0,1\}$ and a partition $(A,B)$ of $V$, define $C(A,B)=(t^{-1}(1)\cap E(A,B))\cup (t^{-1}(0)\cap (E\backslash E(A,B))$ to be the set of edges satisfied by $(A,B)$, where edges of type $1$ need to be separated, while edges of type $0$ should be inside some vertex set.

Clearly, if the given graph for ImproveMaxCut-Uncut is not connected, we can solve each connected component separately, so connectivity of $G$ does not lose any generality for the problem. The following claim is straightforward.

In the following, we present the algorithm for ImproveMaxCut-Uncut.

We first apply a pre-processing algorithm to the given ImproveMaxCut-Uncut instance, intending to make it in accordance with some partition of the vertex set.

In the rest of this section, we prove the following theorem:

We first show how this theorem implies the main theorem.