TAOCP 5 Exercise 23

We are given an undirected graph \(G = (V, E)\) with \(|V| = 4096\) vertices (people) and \(|E| \approx 200\,000\) edges (acquaintance pairs).

taocpmathematicsalgorithmsvolume-3hard

Section 5: Introduction to Sorting

Exercise 23. [30] In a certain group of 4096 people, everyone has about 100 acquaintances. (A file has been prepared listing all pairs of people who are acquaintances. (The relation is symmetric: If $x$ is acquainted with $y$, then $y$ is acquainted with $x$. Therefore the file contains roughly 200,000 entries.) How would you design an algorithm to list all the $k$-person cliques in this group of people, given $k$? (A clique is an instance of mutual acquaintances: Everyone in the clique is acquainted with everyone else.) Assume that there are no cliques of size 25, so the total number of cliques cannot be enormous.

Verified: yes
Solve time: 12m11s

Setup

We are given an undirected graph (G = (V, E)) with (|V| = 4096) vertices (people) and (|E| \approx 200,000) edges (acquaintance pairs). The input is a file listing each edge once as a pair ((u, v)) with (u < v). The graph is simple and symmetric. For a given integer (k) (with (1 \le k \le 24)), we must list all (k)-cliques , sets of (k) vertices that are pairwise adjacent. It is assumed that no clique of size (25) exists, so the total number of cliques is not enormous.hence the output size) is manageable.

Solution

The algorithm uses sorting to build efficient adjacency lists and then performs a backtracking search that enumerates every (k)-clique exactly once.

1. Read and sort the edges

Read all edges from the file. Each edge is a pair ((u, v)) with (1 \le u < v \le 4096). Sort the list of edges lexicographically: first by (u), then by (v). Any (O(M \log M)) sorting algorithm (merge sort, quicksort, or radix sort, since vertex numbers are bounded by (4096)) is suitable. After sorting, edges with the same (u) appear consecutively with increasing (v).

2. Build sorted adjacency lists

Allocate an array (\text{Adj}[1..4096]) of dynamic arrays (or vectors). Scan the sorted edge list once: for each edge ((u, v)), append (v) to (\text{Adj}[u]) and (u) to (\text{Adj}[v]). Because the edge list is sorted by (u), the neighbors appended to (\text{Adj}[u]) are already in increasing order. The neighbors appended to (\text{Adj}[v]) are not necessarily sorted; sort each (\text{Adj}[i]) individually (e.g., with quicksort). Since the average degree is (\approx 100), this step is fast. After sorting, every (\text{Adj}[x]) is a strictly increasing list of all neighbors of (x).

3. Recursive backtracking to enumerate (k)-cliques

We generate each (k)-clique exactly once by insisting that vertices are chosen in strictly increasing order. For each vertex (v = 1, 2, \dots, 4096):

  • If (\deg(v) < k-1), skip (v) (it cannot belong to a (k)-clique).
  • Initialize the current clique (C = [v]).
  • Initialize the candidate set (P = { u \in \text{Adj}[v] \mid u > v }). Because (\text{Adj}[v]) is sorted, (P) is the suffix of (\text{Adj}[v]) consisting of elements greater than (v).
  • Call (\text{Extend}(C, P)).

Procedure (\text{Extend}(C, P)):

  • If (|C| = k): output (C) as a (k)-clique; return.
  • If (|C| + |P| < k): return (not enough candidates to reach size (k)).
  • For each (u \in P) in increasing order:
    • Let (C' = C \cup {u}).
    • Let (P_{\text{tail}} = { w \in P \mid w > u }) (the part of (P) after (u)).
    • Compute (P' = \text{Intersect}(P_{\text{tail}}, \text{Adj}[u])). Since both lists are sorted, the intersection is obtained by a linear‑time merge scan.
    • Call (\text{Extend}(C', P')).
  • End for.

The procedure (\text{Intersect}(A, B)) for sorted lists (A, B) returns a new sorted list of their common elements. Because all lists have length at most (\approx 100), this operation is very fast.

4. Output

Every time (|C|) reaches (k), the clique (C) is printed or stored.

Complexity

  • Sorting edges: (O(M \log M) \approx 200,000 \times 18 \approx 3.6) million comparisons.
  • Building and sorting adjacency lists: (O(M \log d)) with (d \approx 100).
  • Backtracking: Each recursive call processes one vertex and intersects two lists of length (\le 100). The total number of calls is proportional to the number of cliques of size (\le k). By assumption this number is not enormous, so the running time is output‑sensitive and practical.
  • Memory: (O(M)) for adjacency lists plus (O(k)) recursion depth.

Verification

We prove that the algorithm outputs every (k)-clique exactly once.

Lemma 1. Every (k)-clique (S) has a unique smallest vertex (v = \min(S)). The search started from (v) has (C = [v]) and (P = { u \in \text{Adj}[v] \mid u > v }). Since all other vertices of (S) are adjacent to (v) and greater than (v), they belong to (P). Hence the search from (v) can potentially generate (S).

Lemma 2. During the recursive search, (\text{Extend}(C, P)) maintains the invariant:

  • (C) is a clique with vertices in strictly increasing order.
  • (P) is exactly the set of vertices that are adjacent to every vertex in (C) and are greater than (\max(C)).
  • Every (k)-clique that contains (C) and whose remaining vertices are all (> \max(C)) and subsets of (P) will be generated by this call.

Proof by induction on recursion depth.
Base: The initial call from (v) has (C = [v]) and (P = \text{Adj}[v] \cap {u : u > v}), which satisfies the invariant.
Inductive step: Assume the invariant holds for a call with clique (C) and candidates (P).
If (|C| = k), (C) is a (k)-clique and is correctly output.
If (|C| + |P| < k), no (k)-clique extending (C) exists, so returning is correct.
Otherwise, for each (u \in P) in increasing order, we form (C' = C \cup {u}) and (P' = P_{\text{tail}} \cap \text{Adj}[u]), where (P_{\text{tail}} = {w \in P : w > u}). By the invariant, every vertex in (P) is adjacent to all vertices in (C). Since (u \in P), (C') is a clique. A vertex (w \in P') is (> u), belongs to (P) (hence adjacent to all of (C)), and belongs to (\text{Adj}[u]) (hence adjacent to (u)). Thus (w) is adjacent to all of (C'). Conversely, any vertex (w > u) adjacent to all of (C') must be in (P_{\text{tail}}) and in (\text{Adj}[u]), hence in (P'). Therefore (P') is exactly the set of common neighbors of (C') greater than (u), and the invariant holds for the recursive call. Because we iterate (u) in increasing order, every increasing sequence of vertices from (P) that extends (C) to a clique is explored exactly once. ∎

Lemma 3. Each (k)-clique is output exactly once.
Let (S) be a (k)-clique and (v = \min(S)). By Lemma 2, the search from (v) will follow the increasing sequence (S \setminus {v}) and output (S). No other starting vertex (v') can produce (S): if (v' < v) then (v' \notin S) (contradicting (v = \min(S))); if (v' > v) then (v \notin P) initially (since (P) contains only vertices (> v')), so (S) cannot be formed. Hence (S) appears exactly once.

Independent check on a small case.
Consider (V = {1,2,3,4}) with all six edges, (k = 3). Sorted edges: ((1,2), (1,3), (1,4), (2,3), (2,4), (3,4)). Adjacency lists: (\text{Adj}[1]=[2,3,4]), (\text{Adj}[2]=[1,3,4]), (\text{Adj}[3]=[1,2,4]), (\text{Adj}[4]=[1,2,3]).

  • (v=1): (P=[2,3,4]). Recursion yields ({1,2,3}, {1,2,4}, {1,3,4}).
  • (v=2): (P=[3,4]). Recursion yields ({2,3,4}).
  • (v=3): (P=[4]), (|C|+|P|=2 < 3) → prune.
  • (v=4): (P=\emptyset) → prune.
    Output: all four 3‑cliques, each exactly once. Correct.

The assumption that no clique of size (25) exists bounds the recursion depth by (24) and, together with the statement that the total number of cliques is not enormous, justifies the output‑sensitive approach. Sorting the edge file and maintaining sorted adjacency lists are standard correct techniques. The intersection of two sorted lists is a well‑known linear‑time algorithm.

This completes the proof. ∎

Notes

The algorithm uses sorting in two essential ways: sorting the edge file to construct adjacency lists efficiently, and keeping adjacency lists sorted to enable fast intersection during backtracking. The search is a variant of the Bron-Kerbosch algorithm without pivoting, restricted to cliques of size exactly (k) and using a vertex ordering to avoid duplicates. The pruning condition (|C|+|P| < k) is crucial when (k) is close to the maximum clique size.