TAOCP 7.1.3 Exercise 132
Let $G$ be a graph on $V=\{0,1,\dots,n-1\}$.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 132. ▶ [M27] [M27] A clique in a graph is a set of mutually adjacent vertices; a clique is maximal if it’s not contained in any other. The purpose of this exercise is to discuss an algorithm due to J. K. M. Moody and J. Hollis, which provides a convenient way to find every maximal clique of a not-too-large graph, using bitwise operations. Suppose G is a graph with n vertices V = {0, 1, . . . , n −1}. Let ρv = {2u | u −−−v or u = v} be row v of G’s reflexive adjacency matrix, and let δv = {2u | u ̸= v} = 2n −1 −2v. Every subset U ⊆V is representable as an n-bit integer σ(U) = u∈U 2u; for example, δv = σ(V \ v). We also define the bitwise intersection τ(U) = & 0≤u<n(u ∈U? ρu: δu). For example, if n = 5 we have τ({0, 2}) = ρ0 & δ1 & ρ2 & δ3 & δ4.
7.1.3 BITWISE TRICKS AND TECHNIQUES 195 a) Prove that U is a clique if and only if τ(U) = σ(U). b) Show that if τ(U) = σ(T) then T is a clique. c) For 1 ≤k ≤n, consider the 2k bitwise intersections Ck = & 0≤u<k(u ∈U? ρu: δu) U ⊆{0, 1, . . . , k −1} , and let C+ k be the maximal elements of Ck. Prove that U is a maximal clique if and only if σ(U) ∈C+ n . d) Explain how to compute C+ k from C+ k−1, starting with C+ 0 = {2n −1}.
Verified: yes
Solve time: 4m50s
Corrected Solution
Let $G$ be a graph on $V={0,1,\dots,n-1}$. For each vertex $v$, define
$$ \rho_v=\sum{2^u \mid u=v \text{ or } u \text{ is adjacent to } v},\qquad \delta_v=2^n-1-2^v. $$
For $U\subseteq V$,
$$ \sigma(U)=\sum_{u\in U}2^u, \qquad \tau(U)=\bigwedge_{0\le u<n}(u\in U ? \rho_u : \delta_u). $$
A key observation used throughout is the bitwise interpretation: for a fixed vertex $x$,
$$ \tau(U)_x=1 ;\Longleftrightarrow; \text{for every } u\in U,\ (u=x \Rightarrow \rho_u(x)=1)\ \text{and}\ (u\neq x \Rightarrow \rho_u(x)=1). $$
Equivalently, if $x\notin U$ then $\tau(U)_x=0$, while if $x\in U$ then $\tau(U)_x=1$ exactly when $x$ is adjacent to every vertex of $U$ (including itself via reflexivity).
It follows immediately that
$$ \tau(U)={x\in U \mid x \text{ is adjacent to every vertex of } U}. $$
(a)
We prove that $U$ is a clique if and only if $\tau(U)=\sigma(U)$.
If $U$ is a clique, then every $x\in U$ is adjacent to every $u\in U$, so each such $x$ survives all constraints in the definition of $\tau(U)$. Hence $\tau(U)_x=1$ for all $x\in U$, and as noted above no vertex outside $U$ can appear in $\tau(U)$. Therefore $\tau(U)=\sigma(U)$.
Conversely, suppose $\tau(U)=\sigma(U)$. Then every $x\in U$ satisfies $\tau(U)_x=1$, which implies that $x$ is adjacent to every vertex of $U$. In particular, for any distinct $x,y\in U$, vertex $x$ is adjacent to $y$. Thus $U$ is a clique.
(b)
Assume $\tau(U)=\sigma(T)$. Since $\tau(U)\subseteq U$, we obtain $T\subseteq U$.
To show $T$ is a clique, take distinct $v,w\in T$. Since $w\in T$, we have $\tau(U)_w=1$, which implies that $w$ is adjacent to every vertex in $U$, in particular to $v$. Hence every pair of vertices in $T$ is adjacent, so $T$ is a clique.
(c)
First we establish structural properties of $\tau(U)$.
From the definition, $\tau(U)\subseteq U$. Moreover, if $x,y\in \tau(U)$, then both are in $U$ and each is adjacent to every vertex of $U$, hence in particular $x$ is adjacent to $y$. Therefore $\tau(U)$ is always a clique.
Thus every element of $C_n$ is a clique (possibly empty) contained in the generating set $U$ that produced it.
Now we prove the characterization.
Claim
$U$ is a maximal clique if and only if $\sigma(U)\in C_n^+$.
($\Rightarrow$)
Assume $U$ is a maximal clique. By part (a), $\tau(U)=\sigma(U)$, so $\sigma(U)\in C_n$.
Suppose $\sigma(U)$ is not maximal in $C_n$. Then there exists $V\subseteq V$ such that
$$ \tau(V)\supsetneq \tau(U)=U. $$
Since $\tau(V)$ is a clique (as shown above), this contradicts the maximality of $U$. Hence $\sigma(U)\in C_n^+$.
($\Leftarrow$)
Assume $\sigma(U)\in C_n^+$. We first show that $U$ is a clique.
Since $\sigma(U)\in C_n$, there exists some set $W$ such that $\tau(W)=\sigma(U)$. By part (b), $\sigma(U)$ is a clique, so $U$ is a clique.
Now suppose $U$ is not maximal. Then there exists a vertex $v\notin U$ adjacent to every vertex of $U$. Let $V=U\cup{v}$. Then $V$ is a clique, hence by part (a),
$$ \tau(V)=\sigma(V)=\sigma(U),+,2^v, $$
which strictly contains $\sigma(U)$. This contradicts maximality of $\sigma(U)$ in $C_n$. Therefore $U$ is a maximal clique.
(d)
We derive a recurrence for $C_k$.
Every subset $U\subseteq {0,\dots,k-1}$ either contains $k-1$ or it does not. We split accordingly.
Case 1: $k-1\notin U$
Then the contribution of $k-1$ in the definition of $\tau(U)$ is $\delta_{k-1}$, so
$$ \tau(U)=\left(\bigwedge_{0\le u<k-1}(u\in U ? \rho_u : \delta_u)\right)\wedge \delta_{k-1}. $$
Case 2: $k-1\in U$
Write $U=U'\cup{k-1}$. Then
$$ \tau(U)=\left(\bigwedge_{0\le u<k-1}(u\in U' ? \rho_u : \delta_u)\right)\wedge \rho_{k-1}. $$
Thus every element of $C_k$ is obtained from some element $X\in C_{k-1}$ in exactly one of the two ways:
$$ X\wedge \delta_{k-1} \quad\text{or}\quad X\wedge \rho_{k-1}. $$
Hence
$$ C_k={X\wedge \delta_{k-1}\mid X\in C_{k-1}}\ \cup\ {X\wedge \rho_{k-1}\mid X\in C_{k-1}}. $$
Finally, $C_k^+$ is obtained by removing all elements that are strictly contained (bitwise) in others in $C_k$, and the construction starts from
$$ C_0={2^n-1}. $$
This iterative process yields $C_n^+$, whose elements are exactly the maximal cliques of $G$.