15.3.2. Maximum Satisfiability

As a second application of the crown reduction technique, consider the maximum satisfiability (MAX-SAT) problem discussed already in Section 13.3. Given a Boolean formula \(F = C_1 \wedge \cdots \wedge C_m\) in CNF, where \(C_j = \lambda_{j,1} \vee \cdots \vee \lambda_{j,s_j}\) for all \(1 \le j \le m\), and each literal \(\lambda_{j,h}\) is a Boolean variable \(x_i\) or its negation \(\bar x_i\). We want to find a truth assignment that satisfies as many clauses in \(F\) as possible. In Section 13.3, the clauses had weights. Here, we only care about the number of satisfied clauses. In this section, we consider the parameterized version of MAX-SAT, which asks whether there exists a truth assignment that satisfies at least \(k\) clauses in \(F\). We show how to find a problem kernel with at most \(k - 1\) variables and at most \(2(k-1)\) clauses for this problem.

The first "reduction rule" does not actually alter \(F\) or \(k\) but still ensures that \(F\) has at most \(2(k-1)\) clauses: If \(F\) has at least \(2k - 1\) clauses, then we simply report that \((F, k)\) is a yes-instance. By the following observation, this rule is sound.

Observation 15.14: If \(F\) has at least \(2k - 1\) clauses, then there exists a truth assignment that satisfies at least \(k\) clauses in \(F\).

Proof: Consider an arbitrary truth assignment \(\tau\) assignment to the variables in \(F\) and let \(\bar\tau\) be the negation of \(\tau\): \(\bar\tau(x) = \neg \tau(x)\) for every variable \(x\). Note that if \(\tau\) does not satisfy a clause \(C_i\) in \(F\), then \(\bar\tau\) does. Thus, if \(\tau\) does not satisfy at least \(k\) clauses in \(F\), then there are at least \(k\) clauses in \(F\) that are not satisfied by \(\tau\) and are therefore satisfied by \(\bar\tau\). This shows that either \(\tau\) or \(\bar\tau\) satisfies at least \(k\) clauses in \(F\). ▨

The second reduction rule, which may be applied more than once, constructs the variable-clause incidence graph \(G_F\) for \(F\). This is a bipartite graph whose vertex set has one variable vertex \(x_i\) for every variable \(x_i\) in \(F\) and one clause vertex \(C_j\) for every clause \(C_j\) in \(F\). There is an edge \((x_i, C_j)\) if \(x_i\) or \(\bar x_i\) is a literal in \(C_j\). This is illustrated in Figure 15.5.

Figure 15.5: Coming soon!

From here on, we do not distinguish between the clauses or variables in \(F\) and the vertices in \(G_F\) that represent them. Next we apply Lemma 15.11 to find either a matching \(M\) that matches every variable in \(G_F\) or a crown \((I, H)\) of \(G_F\) such that all vertices in \(I\) are variables and all vertices in \(H\) are clauses. If the lemma produces a matching \(M\), then we report that \((F, k)\) is a fully reduced instance. If it produces a crown \((I, H)\), with \(|H| \ge k\), then we report that \((F, k)\) is a yes-instance. If \(|H| < k\), then we construct a new formula \(F'\) from \(F\) by removing all clauses in \(H\) from \(F\). Then we recursively apply the reduction to \((F', k - |H|)\) until we obtain a fully reduced instance or decide that the current instance is a yes-instance.

Lemma 15.15: The above crown reduction rule for the maximum satisfiability problem is sound.

Proof: If the reduction rule finds a matching \(M\) that matches every variable, then the reduction rule returns \((F,k)\) and declares it fully reduced. Thus, the rule is clearly sound in this case.

So assume that the reduction rule returns a reduced instance \((F', k - |H|)\) corresponding to a crown \((I,H)\) in \(G_F\). Let \(\bar I\) be the set of variables in \(G_F\) that do not belong to \(I\) and let \(\bar H\) be the set of clauses in \(G_F\) that do not belong to \(H\). Since \((I,H)\) is a crown, there exists a matching \(M\) of \(G[I, H]\) that matches every clause in \(H\). We define a truth assignment \(\tau_I\) to the variables in \(I\) that satisfies all clauses in \(H\): For each variable \(x_i\) matched to a clause \(C_j\) in \(H\), we choose its value so that \(C_j\) is satisfied (\(x_i = \textrm{true}\) if \(x_i \in C_j\), \(x_i = \textrm{false}\) if \(\bar x_i \in C_j\)). For any other variable in \(I\), we choose its value arbitrarily. Such a truth assignment exists because every variable in \(I\) is matched to at most one clause in \(H\). It satisfies all clauses in \(H\) because every clause in \(H\) is matched to some variable in \(I\).

If \(|H| \ge k\), then we can augment \(\tau_I\) to obtain a truth assignment \(\tau\) to all variables in \(F\) by assigning an arbitrary truth value to every variable in \(\bar I\). Since \(\tau_I\) satisfies all clauses in \(H\), so does \(\tau\). Since \(|H| \ge k\), \(\tau\) thus satisfies at least \(k\) clauses in \(F\) and \((F, k)\) is a yes-instance, as claimed by the reduction rule.

If \(|H| < k\), then we need to prove that \((F, k)\) is a yes-instance if and only if \((F', k - |H|)\) is a yes-instance. First assume that \((F', k - |H|)\) is a yes-instance. Observe that \(G_{F'} = G_F\bigl[I' \cup \bar H\bigr]\), for some subset \(I' \subseteq \bar I\), because, by definition, \(F'\) contains exactly the clauses in \(\bar H\) and, since \((I, H)\) is a crown of \(G_F\), no variable in \(I\) occurs in any clause in \(\bar H\).¹ Thus, a truth assignment that satisfies at least \(k - |H|\) clauses in \(F'\) is a truth assignment \(\tau_{I'}\) to the variables in \(I'\) that satisfies at least \(k - |H|\) clauses in \(\bar H\). We can extend \(\tau_{I'}\) to a truth assignment \(\tau_{\bar I}\) to all variables in \(\bar I\) by giving arbitrary values to the variables in \(\bar I \setminus I'\). Since \(\tau_I\) is a truth assignment to the variables in \(I\) that satisfies at least \(|H|\) clauses in \(H\), \(\tau_I\) and \(\tau_{\bar I}\) together define a truth assignment \(\tau\) to all variables in \(F\) that satisfies at least \(k - |H| + |H| = k\) clauses in \(H \cup \bar H\), that is, in \(F\). Thus, \((F, k)\) is a yes-instance.

If \((F, k)\) is a yes-instance, then let \(\tau'\) be an arbitrary truth assignment that satisfies at least \(k\) clauses in \(F\). Let \(\tau'_{\bar I}\) be the restriction of \(\tau'\) to the variables in \(\bar I\) and let \(\tau\) be the truth assignment defined by \(\tau_I\) and \(\tau'_{\bar I}\). Since no variable in \(I\) occurs in any clause in \(\bar H\), \(\tau\) and \(\tau'\) satisfy the same number of clauses in \(\bar H\). Since \(\tau_I\) satisfies all clauses in \(H\), so does \(\tau\). Thus, \(\tau\) satisfies at least as many clauses in \(F\) as \(\tau'\) does, that is, it also satisfies at least \(k\) clauses in \(F\). This implies that \(\tau'_{\bar I}\) satisfies at least \(k - |H|\) clauses in \(\bar H\), that is, \((F', k - |H|)\) is a yes-instance. ▨

It remains to bound the number of variables in any fully reduced instance with respect to the above crown reduction rule. (Our first "reduction rule" already guarantees that we have at most \(2k - 1\) clauses.)

Lemma 15.16: If \((F, k)\) is a fully reduced maximum satisfiability instance with respect to the above crown reduction rule, then \((F, k)\) is a yes-instance or \(F\) has less than \(k\) variables.

Proof: If \((F, k)\) is fully reduced with respect to the crown reduction rule, then \(G_F\) has a matching that matches every variable \(x_i\) to a unique clause \(C_j\). We can choose the truth value of \(x_i\) so that \(C_j\) is satisfied. Since no clause \(C_j\) is matched to two clause vertices, this ensures that the resulting truth assignment satisfies at least as many clauses as there are variables in \(F\). Thus, if there are at least \(k\) variables in \(F\), then \(F\) is a yes-instance. ▨