Search-Space Reduction for Boolean MinCSPs via Essential Constraints

We extend a recent framework by Bumpus et al. that introduces the notion of $c$-essential objects [6]. Although originally defined within the context of vertex selection problems on graphs, we can rephrase their original definition to apply to MinCSP($ℱ$) problems. Formally, for a given constant $c\in {ℝ}_{\ge 1}$ and an $ℱ$-formula $F$, we call a constraint application in this formula $c$-essential if it is contained in all $c$-approximate solutions to the (Weighted) MinCSP($ℱ$) instance $F$.

One could expect such $c$-essential objects to somehow stand out in the solution space, since we cannot even form a $c$-approximation without them. This might make it feasible to identify such objects during preprocessing, which would be useful for problems like MinCSP($ℱ$) in which the goal is to arrive at a certain structure by deleting a minimum number of objects. All essential objects are in particular part of all optimal solutions, so that, after finding and reducing them from the input, it suffices to solve an instance that looks for a strictly smaller solution. Since many FPT algorithms have a running time that scales exponentially with the solution size, each element of the solution we find during preprocessing decreases the running time by a multiplicative factor. As such, we are interested in preprocessing that finds essential objects, if there are any. This algorithmic task is formalized in the following problem statement, defined for a fixed constraint set $ℱ$ and constant $c\in {ℝ}_{\ge 1}$.

Again we define the unweighted variant of the problem by requiring all weights in the input to be $1$. Note that this problem is, in two ways, easier than the task of simply returning a set containing exactly the $c$-essential constraint applications in an input. First, the output set is allowed to contain more constraint applications, as long as they belong to an optimal solution. Secondly, the algorithm only needs to give a meaningful output if the integer $k$ in its input provides a correct guess or upper bound on the optimal solution of the input. Nonetheless, being able to solve this detection task suffices to speed up FPT algorithms parameterized by solution size, in a black-box fashion. In particular, if for a constraint set $ℱ$ and a constant $c\in {ℝ}_{\ge 1}$, (1) there is a polynomial-time algorithm for $c$-essential Detection for MinCSP($ℱ$), and (2) there is an algorithm that outputs a solution to MinCSP($ℱ$) of size at most $p$, if one exists, in $g(p)\cdot \mathrm{poly}(n)$ time for some computable function $g$, then there is an algorithm that computes an optimal solution of MinCSP($ℱ$) in $g(p-q)\cdot \mathrm{poly}(n)$ time, where $q$ is the number of $c$-essential constraint applications in the input and $p=\mathrm{opt}(F)$. Bumpus et al. have proven this guarantee in the setting of graph problems, but their proof is easily seen to be valid for MinCSP($ℱ$) as well [6, Theorem 5.1].

Using this framework, several positive results and hardness results have been achieved for graph problems such as Vertex Multicut and Directed Feedback Vertex Set [6, 11]. Here, we extend the framework to achieve new results for CSPs.

We present a dichotomy theorem that characterizes for which constraint sets $ℱ$ there is a constant $c$ such that $c$-essential Detection for MinCSP($ℱ$) is polynomial-time solvable. Specifically, we show that this is true for constraint sets $ℱ$ that are $0$-valid, $1$-valid, IHS-B, or bijunctive (these terms are defined in Section 2). The dichotomy reveals that all other constraint sets $ℱ$ yield a MinCSP($ℱ$) problem for which $c$-essential detection is hard for every $c\in {ℝ}_{\ge 1}$, under established hardness assumptions.

As mentioned, other dichotomies exist that characterize the efficient solvability and approximability of MinCSP($ℱ$). Table 1 shows a comparison between some of these that closely relate to our work. It focuses on the boundary between positive and hardness results. The table includes, in left-to-right order, results on constant-factor approximating the problem in polynomial time [13], exactly solving the problem in FPT time, parameterized by solution size [15], and constant-factor approximating the problem in FPT time [5]. A summary of our results from Theorem 1.1 is included in the final column. In a given row, the table indicates whether the specified tasks for constraint sets from that category – and not from any category from a previous row – are tractable under a suitable hardness assumption.

We point out that $c$-essential detection appears to be a strictly easier task than approximating the problem in polynomial-time or exactly solving the problem in FPT time. It is in particular interesting to see that all cases that admit an exact FPT algorithm also admit a polynomial-time $c$-essential detection algorithm. Based on previous work on $c$-essential objects mentioned earlier, this implies that all these FPT algorithms for MinCSP($ℱ$) can be updated to yield an improved runtime dependence on the complexity parameter. We also note that our results show the same boundary of hardness as the existing dichotomy on constant-factor approximating the problem in FPT time.

Finally, we mention some of the existing work on preprocessing, specifically kernelization and compression, for MinCSP and related problems. Unlike kernelization, compression allows problem instances to be transformed to an instance of a possibly different problem. Jansen and Włodarczyk have characterized the best-possible compression size achievable for MinCSP($ℱ$) in terms of the number of variables [12]. Related CSPs include determining whether a given $ℱ$-formula can be satisfied by an assignment that sets at least, or at most, a given number $k$ of variables to $1$. Kratsch and Wahlström characterized for which constraint sets the minimization problem admits a kernel of size polynomial in $k$ [17]. Later, such a characterization was also given for the maximization problem [16].

We proceed by giving a brief overview of the techniques we use to obtain our results. Our algorithmically most interesting positive result is the polynomial-time $c$-essential detection algorithm on bijunctive constraint sets. To achieve it, we use the insight that bijunctive formulas admit a representation in graph form. Then, for each constraint application in the input formula, we solve a sequence of separation problems on this graph to determine whether to put it in the output set of our $c$-essential detection algorithm or not.

Next, for each of our hardness results, we provide a two-step approach. To show, for a given category of constraint sets, that $c$-essential detection is hard for MinCSP($ℱ$), we start by formulating a canonical constraint set from that category and showing that the problem is hard for that set. Then, we show that the corresponding problem for all other constraint sets in that category is as hard as the problem for the canonical constraint set.

To achieve this second step, we show that an essential implementation of the canonical set ${ℱ}_{\mathrm{can}}$ for a category can be made via any constraint set $ℱ$ in that category. That is, for every constraint application over ${ℱ}_{\mathrm{can}}$, there is a conjunction of constraint applications over $ℱ$ that is equivalent to it, while satisfying an additional property as defined in Definition 4.1. The latter ensures that for every constant $c$, a reduction can be made from MinCSP(${ℱ}_{\mathrm{can}}$) to Weighted MinCSP($ℱ$) that preserves the entire space of $c$-approximate solutions.

We remark that our definition of essential implementations is strictly stronger than the very similar notion of strong and perfect implementations by Khanna et al. [13]. An implementation from their framework also yields a reduction between CSP instances over different constraint sets. They showed that this reduction preserves the constant-factor approximability of the involved problems, but, in contrast to our result, it need not preserve the exact approximation ratio. We were surprised to see that most of the implementations we encountered in related work (also beyond strong and perfect implementations) happen to fit our definition of an essential implementation as well. This reveals even stronger links between problems that have already been shown to be reducible to one another.

The rest of the paper is organized as follows. In Section 2, we define some fundamental concepts and notation. Section 3 contains our positive results, proving Case 2 of Theorem 1.1. Section 4 contains our hardness results, starting with an introduction to essential implementations. Then, in Sections 4.1, 4.2, and 4.3, we prove Cases 3, 4, and 5 of Theorem 1.1 respectively. We conclude with open questions in Section 5. The proofs of statements marked $(\mathrm{★})$ are deferred to the full version.

First note that we may assume w.l.o.g. that input formulas $F$ are already given to us in suitable $2$CNF representation when dealing with MinCSP($ℱ$) instances. Otherwise, we could, for every fixed bijunctive $ℱ$, provide a polynomial-time transformation using a hard-coded bijunctive representation of each constraint in $ℱ$. Thus, let $F$ be an $ℱ$-formula represented in $2$CNF in which every constraint is written as conjunction of at most $d$ clauses. Let $G_F$ be its implication graph, and let $C$ be a constraint application in $F$ that is expressed as $(a_1\vee b_1)\wedge \mathrm{\dots }\wedge (a_{\mathrm{\ell }}\vee b_{\mathrm{\ell }})$, where $a_1,\mathrm{\dots }{a}_{\mathrm{\ell }},b_1,\mathrm{\dots },b_{\mathrm{\ell }}$ are literals for some $\mathrm{\ell }\le d$.

To prove the lemma, we give a polynomial-time algorithm that computes a set $P_C$ from $F$ and $C$, after which we show that this set meets the three preconditions described in Lemma 3.1. To ensure that our algorithm is well-defined, we prove the claim below.

We observe that an assignment $s$ that satisfies $F^{\prime }$ and sets an arbitrary literal $r$ to $1$ must set all other literals reachable from $r$ in $G_{F^{\prime }}$ to $1$ as well. Thus, if literals $\neg a_i$ and $\neg b_i$ are reachable from $a_i$ and $b_i$ respectively, any satisfying assignment to $F^{\prime }$ must set $a_i$ and $b_i$ to $0$. Such an assignment cannot satisfy the clause $C$ in $F^{\prime }$ that requires $(a_i\vee b_i)$. $\mathrm{⊲}$ Now, $P_C$ can be computed as follows.

• $\mathrm{■}$

  Construct the implication graph $G_F$ of $F$.

• $\mathrm{■}$

  For all $i\in [\mathrm{\ell }]$, compute a smallest subset of arcs in $G_{F-f}$ that breaks all $(a_i,\neg a_i)$-paths in $G_F$ and compute a smallest subset of arcs in $G_{F-f}$ that breaks all $(b_i,\neg b_i)$-paths in $G_F$. If only one of these two sets exists, let $T_i$ be this set, or, if both exist, let $T_i$ be a minimum-size set among the two. (Note that at least one of these cuts must exist. If not, the implication graph $G_C$ of the singular constraint application $C$ would have to contain both an $(a_i,\neg a_i)$-path and a $(b_i,\neg b_i)$-path, which, by Claim 3.5, would imply $C$ to be unsatisfiable. This would contradict our assumption that all individual constraints we consider are satisfiable.)

• $\mathrm{■}$

  Let $T$ be ${\bigcup }_{i\in [\mathrm{\ell }]}{T}_i$ and let $P_C$ be the set of constraint applications in $F$ with at least one of their corresponding implication arcs in $T$.

First, we observe that the construction above can be executed in polynomial time. The bottleneck is the second step in which a linear number of cut problems need to be solved. These are variants of the standard min-cut problem on directed graphs, and are easily seen to be solvable efficiently by a simple modification of a polynomial-time mincut algorithm, such as the Ford-Fulkerson algorithm [8].

It remains to prove that $P_C$ satisfies the three properties specified in Lemma 3.1. By construction, $P_C$ does not contain $C$, so it satisfies the first property.

For the other two properties, we start by noting that $T$ is a set of arcs that, for every $i\in [\mathrm{\ell }]$, breaks either all $(a_i,\neg a_i)$-paths or all $(b_i,\neg b_i)$-paths in $G_F$ without including any arcs that correspond to a clause of $C$. We call such a set a $C$-respecting arc set. (Note that such sets may include duplicates of arcs that correspond to a clause of $C$, but not those that specifically correspond to $C$.) Likewise, we call a set of constraint applications from $F$ a $C$-respecting constraint application set if the union of their respective arcs in $G_F$ is a $C$-respecting arc set. As such, $P_C$ is a $C$-respecting constraint application set. We use this notation to show that $P_C$ satisfies the second property specified in Lemma 3.1.

Since $F-X_C$ contains $C$, it follows from Claim 3.5 that $X_C$ is a $C$-respecting constraint application set. By definition, the union $T^{\ast }$ of all arcs in $G_F$ that correspond to a clause in $X_C$ is a $C$-respecting arc set in $G_F$. Since $C$ contains at most $d$ clauses that each introduce $2$ arcs in $G_F$, we find that $|T^{\ast }|\le 2d\cdot |X_C|$. Since every $T_i$ breaks its respective paths optimally, we find that ${\max }_{i\in [\mathrm{\ell }]}|T_i|\le |T^{\ast }|$, so that the union $T$ of all $\mathrm{\ell }\le d$ sets $T_i$ has $|T|\le d\cdot |T^{\ast }|$. With $P_C$ being the set of constraint applications corresponding to the arcs in $T$, we find that $|P_C|\le |T|$. Combining all inequalities we obtain $|P_C|\le 2d^2\cdot |X_C|$. $\mathrm{⊲}$

Now, we show that $P_C$ also satisfies the third property listed in Lemma 3.1.

Given an assignment $s$ that satisfies $F-X$, we explain how to transform it into a satisfying assignment for $F^{\ast }$. Pick an arbitrary clause $(a_i\vee b_i)$ from $C$ that is not yet satisfied by $s$ and determine whether $G_{F^{\ast }}$ contains no $(a_i,\neg a_i)$-path or that it contains no $(b_i,\neg b_i)$-paths. Since $P_C$ is $C$-respecting, at least one of these statements is true and we assume w.l.o.g. that the former is true. Then, we modify $s$ by setting $a_i$ and all literals reachable from $a_i$ in $G_{F^{\ast }}$ to $1$. We repeat this for as long as $C$ contains unsatisfied clauses.

To see that $s$ is a valid assignment after a single iteration, suppose for contradiction that $s$ was modified to set both $x$ and $\neg x$ to $1$. Then, $x$ and $\neg x$ are both reachable from $a_i$. However, the structure of implication graphs ensures that, for every arc $(u,v)$, the arc $(\neg v,\neg u)$ also exists. Thus, $\neg a_i$ is reachable from $x$, which in turn is reachable from $a_i$, contradicting that $G_{F^{\ast }}$ contains no $(a_{,}\neg a_i)$-path.

Thus, every iteration ends with a valid assignment. Moreover, by setting $a_i$ to $1$, $s$ satisfies $C$. Moreover, no previously satisfied clause $(x\vee y)$ becomes unsatisfied, by setting both $\neg x$ and $\neg y$ to $1$: if, e.g., $\neg x$ is reachable from $a_i$, then so is $y$ via the arc $(\neg x,y)$. Thus, setting $\neg x$ to $1$ means that $y$ will also be set to $1$. Therefore, the described procedure strictly increases the number of satisfied clauses in each iteration and it stops when all clauses from $C$ are satisfied, resulting in a satisfying assignment for $G_{F^{\ast }}$. $\mathrm{⊲}$

This proves that the algorithm described above computes a set $P_C$ in polynomial time that satisfies all three preconditions for Lemma 3.1. In particular, our algorithm satisfies these constraints with $c=2d^2$. By Lemma 3.1, there is a polynomial-time $(2d^2+1)$-detection algorithm for MinCSP($ℱ$). $◀$

We recall that FPT algorithms, parameterized by solution size, are known for MinCSP($ℱ$) on bijunctive constraint sets $ℱ$ if and only if the so-called Gaifman graph of $ℱ$ is $2K_2$-free [15]. So, by a result analogous to one from the original work [6, Theorem 5.1] on $c$-essential detection, Lemma 3.4 effectively shows that we can reduce the search-space of these FPT algorithms. In particular, it shows that their exponential runtime dependence on the total size of an optimal solution can be improved to depend only on the number of constraint applications in an optimal solution that are not $c$-essential.

We prove the statement by showing how to reduce an ${ℱ}_2$-formula to a weighted ${ℱ}_1$-formula in such a way that a polynomial-time $c$-essential detection algorithm on the ${ℱ}_1$-formula can be used to detect $c$-essential constraint applications in the ${ℱ}_2$-formula. By Lemma 2.1, this suffices to prove the lemma.

Let $F_2$ be an ${ℱ}_2$-formula with constraint applications $C_1,\mathrm{\dots },C_{\mathrm{\ell }}$ over variables $𝐗=\{x_1,\mathrm{\dots },x_n\}$. To transform $F_2$ into a weighted ${ℱ}_1$-formula $F_1$, we replace every $C_i$ in $F_2$ by an essential implementation ${𝒞}_i$ of constraint applications from ${ℱ}_1$ over variables $𝐗\cup {𝐘}_i$. We denote the head of ${𝒞}_i$ by $C_i^{\ast }$. We give all constraint applications a weight of $\lceil c\cdot \mathrm{\ell }\rceil +1$, except for the heads $C_1^{\ast },\mathrm{\dots },C_{\mathrm{\ell }}^{\ast }$ that each receive a weight of $1$. We define $𝐘:={\bigcup }_{i\in [\mathrm{\ell }]}{𝐘}_i$.

The first step towards proving the correctness of this reduction is to observe that non-head constraint applications in $F_1$ do not appear in any $c$-approximate solution. After all, it follows from Property (I2) that the set of heads $H:=\{C_1^{\ast },\mathrm{\dots },C_{\mathrm{\ell }}^{\ast }\}$, with total weight $\mathrm{\ell }$, makes $F-H$ satisfiable, whereas every other constraint has weight $\lceil c\cdot \mathrm{\ell }\rceil +1$. Now, the following claim effectively shows that the set $H$ spans the exact same space of $c$-approximate solutions to $F_1$ as the set of original constraint applications $C_1,\mathrm{\dots },C_{\mathrm{\ell }}$ does for $F_2$.

For one direction, let $s$ be an assignment on $𝐗$ that satisfies $F_2-S$. For every $i\in [\mathrm{\ell }]$ such that $C_i\in S$, assignment $s$ can be extended to an assignment on $𝐗\cup {𝐘}_i$ that satisfies all constraint applications in $𝒞\setminus \{C_i^{\ast }\}$, due to Property (I2). For every $i\in [\mathrm{\ell }]$ such that $C_i\notin S$, since $s$ satisfies $C_i$, assignment $s$ can be extended to an assignment on $𝐗\cup {𝐘}_i$ that satisfies all constraint applications in ${𝒞}_i$, due to Property (I1). This covers all constraint applications in $F_1-S_H$, showing that an extension of $s$ to $𝐗\cup 𝐘$ exists that satisfies $F_1-S_H$.

For the other direction, observe that any assignment $s^{\prime }$ on $𝐗\cup 𝐘$ that satisfies $F_1-S_H$, satisfies the constraint applications in ${𝒞}_i$ for every $i$ such that $C_i\notin S$. Thus, by Property (I1), the restriction of $s^{\prime }$ to $𝐗$ satisfies $F_2-S$. $\mathrm{⊲}$ Since every head has weight $1$, it follows that $\mathrm{opt}(F_1)=\mathrm{opt}(F_2)$. Now we show how to use a polynomial-time $c$-essential detection algorithm $𝒜$ for Weighted MinCSP(${ℱ}_1$) to construct a polynomial-time $c$-essential detection algorithm for MinCSP(${ℱ}_2$).

Given an ${ℱ}_2$-formula $F_2$ and an integer $k$, we start by transforming it into a weighted ${ℱ}_1$-formula $F_1$ using the reduction above; the weights are polynomial. Then, we apply $𝒜$ to $F_1$ and let $D_1$ denote its output. If $D_1$ contains non-head constraint applications of $F_1$, we return the empty set. Otherwise, we return the set of constraint applications $C_i$ for which the corresponding head $C_i^{\ast }$ is in $D_1$. In either case, let $D_2$ be the output of our algorithm.

It remains to show that the above is a $c$-essential detection algorithm for $F_2$. First, suppose that $\mathrm{opt}(F_1)=\mathrm{opt}(F_2)\le k$. Since $D_1$ satisfies Property (G1) it is a subset of some optimal solution $S_1$ to $F_1$. $S_1$, and by extension $D_1$ must consist entirely of heads. Then, the set $S_2$ of constraint applications in $F_2$ for which the corresponding head is in $S_1$ must be a superset of $D_2$. By Claim 4.3, $S_2$ is an optimal solution to $F_2$, showing that $D_2$ satisfies Property (G1).

Next, suppose that $\mathrm{opt}(F_1)=\mathrm{opt}(F_2)=k$. Since $D_1$ satisfies Property (G2), it contains all $c$-essential constraint applications from $F_1$. Since the set of heads was shown to preserve the entire space of $c$-approximate solutions, a constraint application $C_i$ in $F_2$ is $c$-essential if and only if its corresponding head $C_i^{\ast }$ is $c$-essential in $F_1$. Since $D_2$ contains the set of heads corresponding to $D_1$, it contains all $c$-essential constraint applications in $F_2$. $◀$ Next, we prove that the notion of essential implementations is a transitive relation.

Let $(f_3,𝐗)$ be an arbitrary constraint application from ${ℱ}_3$ over variables $𝐗=\{x_1,\mathrm{\dots },x_p\}$. To prove the lemma, we show that ${ℱ}_1\stackrel{\mathrm{ess}.}{\to }{f}_3$.

Since ${ℱ}_2\stackrel{\mathrm{ess}.}{\to }{ℱ}_3$, there is an essential implementation of $(f_3,𝐗)$ consisting of constraint applications $C_1,\mathrm{\dots },C_m$ from ${ℱ}_2$ over variables $𝐗$ and shared dummy variables $𝐘$. Let $C_1$ be the head of this implementation. Since ${ℱ}_1\stackrel{\mathrm{ess}.}{\to }{ℱ}_2$, there is, for each $i\in [m]$, an essential implementation ${𝒞}_i$ of $C_i$ consisting of constraint applications from ${ℱ}_1$ over variables $𝐗\cup 𝐘$ and dummy variables ${𝐙}_i$. Let $C_i^{\ast }\in {𝒞}_i$ denote the head of ${𝒞}_i$. Note that the constraint applications in one ${𝒞}_i$ share one set of dummy variables ${𝐙}_i$, but that this set differs between different implementations ${𝒞}_i$.

We show that the concatenation of all constraint applications in ${𝒞}_i,\mathrm{\dots },{𝒞}_m$ is an essential implementation of $f_3$ with head $C_1^{\ast }$. It is easily verified that this satisfies Property (I1), so we continue by showing the more interesting fact that it satisfies Property (I2).

Consider an arbitrary assignment $s$ on $𝐗$. By Property (I2) of implementation $C_1,\mathrm{\dots },C_m$, it extends to an assignment $s^{\prime }$ on $𝐗\cup 𝐘$ that satisfies $C_2,\mathrm{\dots },C_m$. By Property (I1) of the implementations ${𝒞}_2,\mathrm{\dots },{𝒞}_m$, $s^{\prime }$ extends to an assignment on $𝐗\cup 𝐘\cup (𝐙\setminus {𝐙}_1)$ that satisfies all constraint applications in ${𝒞}_2,\mathrm{\dots },{𝒞}_m$. By Property (I2) of the implementation ${𝒞}_1$, every assignment on $𝐗\cup 𝐘$ – including $s^{\prime }$ – extends to an assignment on $𝐗\cup 𝐘\cup {𝐙}_1$ that satisfies ${𝒞}_1\setminus \{C_1^{\ast }\}$. Thus, $s$ extends to an assignment $s^{\prime }$ that in turn extends to an assignment on $𝐗\cup 𝐘\cup 𝐙$ that satisfies $𝒞\setminus \{C_1^{\ast }\}$, proving that $𝒞$ satisfies Property (I2). $◀$

Next, in Sections 4.1, 4.2, and 4.3, we prove Cases 3, 4, and 5 from Theorem 1.1. Due to space limitations, the proofs in Sections 4.1 and 4.3 are deferred to the full version. The proofs in Section 4.2 also showcase the general proving strategies used in the other two sections, but we remark that each case of the dichotomy represents a significant effort in tailoring these strategies to their specific setting. Although we consider the introduction and use of essential implementations to be one of our main contributions, this also means that our proofs show only two examples of specific essential implementations.