TAOCP 7.2.2.2 Exercise 8

Section 7.2.2.2: Satisfiability

Exercise 8. ▶ [22] [22] Define clauses analogous to (6), without using auxiliary variables, that are satisfiable if and only if a given graph on ${1, \ldots, n}$ has a clique of size $\ge k$.

Verified: yes
Solve time: 1m05s

Solution

Let $G$ be a graph on vertex set ${1,\ldots,n}$, and let $k$ be given. Introduce a Boolean variable $x_i$ for each vertex $i$, with the intended interpretation that $x_i=1$ means vertex $i$ is chosen.

We construct a family $F$ of clauses such that $F$ is satisfiable if and only if $G$ contains a clique of size at least $k$.

The construction uses two types of constraints.

For every pair of distinct vertices $i,j$ that is not an edge of $G$, add the binary clause

$\bar{x}_i \vee \bar{x}_j.$

This clause excludes the possibility that both $i$ and $j$ are chosen simultaneously, since any assignment with $x_i=x_j=1$ would falsify it. Hence any satisfying assignment corresponds to a set of chosen vertices that is a clique.

To enforce the lower bound on the size of the chosen set, consider any subset $S \subseteq {1,\ldots,n}$ with $|S|=n-k+1$, and add the clause

$\bigvee_{i \in S} x_i.$

This clause forbids the assignment in which all variables in $S$ are $0$. If some assignment has at most $k-1$ variables equal to $1$, then at least $n-k+1$ variables are equal to $0$, so there exists a set $S$ of size $n-k+1$ consisting entirely of zeros, and the corresponding clause is violated. Conversely, if every such clause is satisfied, then no set of $n-k+1$ variables can all be $0$, so at most $k-1$ variables are $0$, hence at least $k$ variables are $1$.

Let $F$ be the conjunction of all clauses of these two types.

Assume $F$ is satisfiable and let $L={i : x_i=1}$. From the binary clauses, every pair of distinct vertices in $L$ must be adjacent in $G$, so $L$ is a clique. From the second family of clauses, at least $k$ variables are assigned $1$, so $|L| \ge k$. Hence $G$ has a clique of size at least $k$.

Conversely, suppose $G$ has a clique $L$ with $|L|\ge k$. Assign $x_i=1$ if $i \in L$ and $x_i=0$ otherwise. Every non-edge clause $\bar{x}_i \vee \bar{x}j$ is satisfied because no two vertices in $L$ are non-adjacent. For any set $S$ with $|S|=n-k+1$, since $|L|\ge k$, the complement of $L$ has size at most $n-k$, so $S$ cannot be entirely contained in the set of zeros. Hence some $i \in S$ satisfies $x_i=1$, and the clause $\bigvee{i \in S} x_i$ is satisfied. Therefore all clauses are satisfied, so $F$ is satisfiable.

This establishes that $F$ is satisfiable if and only if $G$ contains a clique of size at least $k$. This completes the proof. ∎