Chapter III Clique

Friends of friends of friends

In a clique, everyone knows everyone. Finding the biggest one is exhausting.

Take an undirected graph and look for a fully-connected subset:

G = (V, E), S \subseteq V with {u, v} \in E for all u, v \in S . (1)

A set satisfying (1) is a clique. The decision version of the problem asks whether the graph contains a clique of size at least k. Karp reduced 3-SAT to it: build a vertex per literal occurrence, connect compatible literals across clauses, and a satisfying assignment becomes a clique of size equal to the clause count.

Maximum clique resists even constant-factor approximation under standard assumptions (Håstad), and the best exact algorithms run in time

O (1. 2^{n}), (2)

polynomial only on the log of the input.

Figures, in plain terms

(1)

G = (V, E) names the graph: V is the set of vertices (the dots), E is the set of edges (the lines between them).

S ⊆ V says S is a subset of the vertices — pick any group of dots, including possibly all of them or none of them. The horseshoe-with-a-line symbol ⊆ reads "is a subset of."

The condition after "with" demands an edge between every pair drawn from S. The braces {u, v} are an unordered pair, ∈ E means "is an edge in the graph," and for all u, v ∈ S quantifies over every choice of two vertices in S.

Put it all together: S is a clique when every two of its members are directly connected.

(2)

O(...) is big-O notation — an upper bound on how the runtime grows as the input gets bigger. O(n²) means the work is at most some constant times n², for large enough n.

1.2ⁿ is exponential growth: the runtime multiplies by 1.2 every time n grows by one. With n = 50, that's already over 9,000× the work of n = 1.

The bound (2) is "polynomial only on log n" because if you wrote 1.2ⁿ as 2^(0.26 n), the exponent is linear in n — and n is exponential in log n. So the runtime is exponential in the size of the input but only polynomial in log of the input.