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: 1m23s

---

Solution

Let the vertices of the given graph be ${1,\ldots,n}$. Introduce one Boolean variable $x_i$ for each vertex $i$, where $x_i=1$ means that vertex $i$ is chosen for the clique. The clauses must force the chosen vertices to form a set of size at least $k$ and must forbid choosing any pair of vertices that is not connected by an edge.

For every non-edge ${i,j}$ of the graph, introduce the binary clause

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

In Knuth's literal notation this clause is written $\bar{i}\bar{j}$. These clauses ensure that two nonadjacent vertices cannot both receive the value $1$.

To require at least $k$ vertices to be chosen, introduce one clause for every subset $S\subseteq{1,\ldots,n}$ with $|S|=n-k+1$:

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

In literal notation this is

$$ {i:i\in S}. $$

The required formula $F$ is the set of all these clauses:

$$ F= {\bar{i}\bar{j}: {i,j}\text{ is not an edge of the graph}} \cup {{i:i\in S}:S\subseteq{1,\ldots,n},\ |S|=n-k+1}. $$

No auxiliary variables are used, because every variable of $F$ corresponds directly to a vertex of the graph.

Suppose first that the graph contains a clique $K$ with $|K|\geq k$. Define a satisfying assignment by

$$ x_i= \begin{cases} 1,&i\in K,\ 0,&i\notin K. \end{cases} $$

Consider a clause $\bar{i}\bar{j}$ arising from a non-edge ${i,j}$. Since $K$ is a clique, it cannot contain both $i$ and $j$. Hence at least one of $x_i,x_j$ is $0$, so the clause $\bar{i}\vee\bar{x}_j$ is satisfied.

Now consider a clause corresponding to a set $S$ of size $n-k+1$. Its variables are the vertices in $S$. If every vertex in $S$ had value $0$, then all vertices of $K$ would lie outside $S$. The complement of $S$ has size

$$ n-(n-k+1)=k-1, $$

so it cannot contain the $k$ vertices of $K$. Therefore some vertex of $K$ lies in $S$, and the clause $\bigvee_{i\in S}x_i$ is satisfied. Hence the assignment satisfies all clauses of $F$.

Conversely, suppose that $F$ has a satisfying assignment. Let

$$ K={i:x_i=1}. $$

For every non-edge ${i,j}$, the clause $\bar{i}\bar{j}$ belongs to $F$. Since this clause is satisfied, it is impossible that both $x_i=1$ and $x_j=1$. Therefore every two vertices of $K$ are adjacent, so $K$ is a clique.

It remains to show that $|K|\geq k$. Assume instead that $|K|\leq k-1$. Then the complement of $K$ contains at least

$$ n-(k-1)=n-k+1 $$

vertices. Choose a subset $S$ of the complement of $K$ with

$$ |S|=n-k+1. $$

The clause

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

belongs to $F$. Every vertex in $S$ has value $0$, so every literal in this clause is false, contradicting the assumption that the assignment satisfies $F$. Therefore

$$ |K|\geq k. $$

Thus every satisfying assignment gives a clique of size at least $k$, and every clique of size at least $k$ gives a satisfying assignment. The constructed clauses therefore are satisfiable exactly for graphs containing a clique of size $\geq k$.

This completes the proof.

∎