Maximum And- vs. Even-SAT

First, find any optimal solution $c^{\ast }$ to (1) with $D=[-1,1]$ by LP. To do this, one can use a standard trick. For each clause $C_i=\{s_1^i{x}_1^i,\mathrm{\dots },s_{k_i}^i{x}_{k_i}^i\}$ for $i\in [m]$, introduce a variable $t_i$ and constraints $t_i\le s_j^{i}c(x_j^i)$ for $j\in [k_i]$. Next, replace the objective function by ${\sum }_{i=1}^m\frac{1}{2}+\frac{1}{2}{t}_i$. Observe that in any feasible solution to this LP, we have $t_i\le {\min }_{1\le j\le k_i}{s}_j^{i}c(x_j^i)$. Furthermore, since the objective is an increasing function of $t_1,\mathrm{\dots },t_m$, in any optimal solution to this LP we have $t_i={\min }_{1\le j\le k_i}{s}_j^{i}c(x_j^i)$. Hence the optimal solutions to this LP precisely correspond to the optimal solutions to (1).

We will shift the solution while keeping it optimal until the image of $c^{\ast }$ is contained in $\{-1,0,1\}$. As a pre-processing step, flip signs of literals so that $c^{\ast }(x)\ge 0$ for $x\in V$. Our goal now is to have the image of $c^{\ast }$ contained in $\{0,1\}$. Suppose without loss of generality that $V=\{1,\mathrm{\dots },n\}$ and $c^{\ast }(1)\le \mathrm{\cdots }\le c^{\ast }(n)$. Define

Note that for every $c$ for which $0\le c(1)\le \mathrm{\cdots }\le c(n)$, $\arg {\min }_{1\le j\le k_i}{s}_j^{i}c(x_j^i)$ is known. Indeed, if all $s_j^i$ are positive then the minimum is attained at the smallest $x_j^i$; whereas if there is at least one negative $s_j^i$ then the minimum is attained at the largest $x_j^i$ among those with $s_j^i=-1$. (Here we compare variables by the natural ordering, since we have assumed the variables are natural numbers.) Let $j(i)=\arg {\min }_{1\le j\le k_i}{s}_j^{i}c(x_j^i)$ be this minimum; then, for all $c$ where $0\le c(1)\le \mathrm{\cdots }\le c(n)$,

In other words, $F$ is an affine function in terms of $c$! Define $c^{\ast }(0)=0,c^{\ast }(n+1)=1$. While $c^{\ast }$ has an image that is not 0 or 1, do the following. Take $1\le a\le b\le n$ so that . Such $a,b$ exist, or else $c^{\ast }(x)\in \{0,1\}$ for all $x\in [n]$. If the sum of the coefficients of $c^{\ast }(a),\mathrm{\dots },c^{\ast }(b)$ in $F$ (seen as an affine function) is negative, then we could decrease all of these values together (since this maintains the fact that $0\le c^{\ast }(1)\le \mathrm{\cdots }\le c^{\ast }(n)$) and improve our solution, which is impossible. If the sum of the coefficients is positive, then we could improve our solution by increasing the values of $c^{\ast }(a),\mathrm{\dots },c^{\ast }(b)$, which is impossible. So we can assume the sum of the coefficients is 0, in which case we can set the values $c^{\ast }(a),\mathrm{\dots },c^{\ast }(b)$ to anything we want in the interval $[0,c^{\ast }(b+1)]$ without changing the value of the solution. So set $c^{\ast }(a)=\mathrm{\cdots }=c^{\ast }(b)=0$. Continue this procedure until there are no variables set to anything other than 0 or 1. $◀$

We now prove Theorem 3, restated below for the reader’s convenience.

Without loss of generality, we can assume that each variable appears in each clause at most once. Indeed, if a clause $C$ contains a variable $x$ and its negation $-x$ then $C$ cannot be strongly satisfied but could be weakly satisfied, so running our algorithm on the instance without $C$ causes no issues. Similarly, if a literal appears twice in a clause then both occurrences can be removed, as this does not affect weak satisfiability (but could improve strong satisfiability).

Suppose we are given an instance of Max-And-Even, namely an expression of form

Suppose that the value of this expression is $\rho$. Our goal is to find a function $c^{\ast }$ such that that number of weakly satisfied clauses is at least $\rho$. Recalling that a clause $\{s_1{x}_1,\mathrm{\dots },s_k{x}_k\}$ is weakly satisfied by $c$ if and only if $\frac{1}{2}+\frac{1}{2}{\prod }_i{s}_{i}c(x_i)=1$, and that this expression is 0 otherwise, we note that we must find $c^{\ast }:V\to \{-1,+1\}$ such that

Using Theorem 8, we can efficiently find a function $\tilde{c}:V\to \{-1,0,+1\}$ such that

We claim that the following choice of $c^{\ast }$ makes (2) hold in expectation: if $\tilde{c}(v)=\pm 1$ then set $c^{\ast }(v)=\tilde{c}(v)$. Otherwise set $c^{\ast }(v)$ equal to $+1$ or $-1$ uniformly and independently at random. Indeed, by linearity of expectation it suffices to show that, for any clause $\{s_1{x}_1,\mathrm{\dots },s_k{x}_k\}$, we have

In particular, let us consider the value of the minimum on the left. If it is $-1$ there is nothing left to prove. If it is $+1$, then $\tilde{c}(x_i)\ne 0$ and hence $c^{\ast }(x_i)=\tilde{c}(x_i)$ for all $x_i$, and the bound holds with equality. Finally, if the minimum is 0, then there exists some $x_i$ such that $\tilde{c}(x_i)=0$; hence $c^{\ast }(x_i)$ is set to $+1$ or $-1$ equiprobably. It is easy then to see that the product on the right hand side is either $+1$ or $-1$ equiprobably, whence the conclusion. (This depends, essentially, on the fact that every variable appears in each clause at most once.)

We now derandomise the rounding scheme above; in other words, we will show how to deterministically set the variables so that the resulting value is at least as good as the expectation of the random variables. Equivalently, given a set of parity constraints on subsets of variables, the goal is to find an assignment that satisfies at least as many constraints as the random assignment. This problem can be derandomised easily using the method of conditional expectation – indeed these techniques have appeared before in e.g. [11], but we include them for completeness. Recall that, by assumption, each variable appears in each clause at most once. Thus, conditional on some subset of variables being fixed, we expect half of the remaining parity constraints that have at least one unfixed variable within them to be satisfied. Thus, we can derandomise by going through the variables one by one; when we set a variable $x$, we set it so that as many as possible of the parity constraints where $x$ is the last unfixed variable remaining are satisfied. $◀$

Equivalently, given a digraph $G$ that has a dicut with $\rho$ edges, we will produce an ordering of the vertices of $G$ such that at least $\rho$ edges are oriented according to the ordering – removing all the edges that are not oriented in this way gives us the required subgraph. For some ordering $\sigma$, we say that an edge $(x,y)$ is well ordered by $\sigma$ if $x$ comes before $y$ in $\sigma$.

As a pre-processing step, remove all loops from the input digraph. This will never lower the size of the maximum dicut, nor will it lower the size of the outputted subgraph. Now compute a solution $\tilde{c}$ to (1) for $G=(V,E)$ over $D=\{-1,0,1\}$, using Theorem 8. By this, we mean a solution to the instance including the clause $\{-x,y\}$ once for each occurrence of the edge $(x,y)$ in $G$. In other words, each edge $(x,y)$ contributes $\frac{1}{2}+\frac{1}{2}\min (-c(x),c(y))$ to (1). The values of this expression over $D=\{-1,0,1\}$ are tabulated in Figure 1.

Since the digraph admits a dicut with $\rho$ edges, the value of $\tilde{c}$ is at least $\rho$. Partition the vertices of $G$ into $V_{-1},V_0,V_1$ according to their image through $\tilde{c}$. Let $E_{ij}=E\cap (V_i\times V_j)$, for $i,j\in \{-1,0,1\}$. Let ${\pi }_{-1},{\pi }_0,{\pi }_1$ be arbitrary orderings of $V_{-1},V_0,V_1$, and let ${\pi }_0^{\prime }$ be the reverse of ${\pi }_0$. We claim that one of the orderings $\sigma =({\pi }_{-1},{\pi }_0,{\pi }_1)$ or ${\sigma }^{\prime }=({\pi }_{-1},{\pi }_0^{\prime },{\pi }_1)$ can be returned.

To see why, note that every edge $(x,y)$ with is well ordered by both $\sigma$ and ${\sigma }^{\prime }$. Furthermore, at least half the edges $(x,y)$ with $\tilde{c}(x)=\tilde{c}(y)=0$ are ordered correctly in one of $\sigma$ or ${\sigma }^{\prime }$ (this is why removing loops is essential). But (cf. Figure 1 and the optimality of $\tilde{c}$),

Hence, at least one of $\sigma$ and ${\sigma }^{\prime }$ well orders at least $\rho$ edges. $◀$