Algorithms / Two Cliques Complement
Least You Need to Know: TwoCliques, Complement Graphs, and Bipartite Recognition
TwoCliques is a great exam contrast case: it sounds like a hard partition problem, but it becomes easy after the right graph transformation. A graph can be partitioned into two cliques exactly when its complement is bipartite, so the right move is a complement-and-check reduction to a tractable problem.
The least you need to know
- A clique in `G` becomes an independent set in the complement graph `\overline{G}`.
- Partitioning `G` into two cliques is equivalent to partitioning `\overline{G}` into two independent sets.
- A graph is bipartite exactly when its vertices can be partitioned into two independent sets.
- Therefore TwoCliques can be solved by forming the complement graph and testing bipartiteness.
- Not every graph problem listed near NP-complete topics is itself NP-hard.
Key notation
\overline{G}
complement graph of `G`
clique
every pair of vertices in the set is adjacent
bipartite
vertices split into two independent sets
Tiny worked example
- Suppose `G` can be partitioned into cliques `C_1` and `C_2`.
- In the complement graph `\overline{G}`, there are no edges inside `C_1` or inside `C_2`.
- So `C_1` and `C_2` are independent sets of `\overline{G}`.
- That means `\overline{G}` is bipartite, and the converse argument works too.
Common mistakes
- Students often assume TwoCliques must be NP-hard because the statement looks combinatorial and partition-based.
- The complement transformation flips clique reasoning into independent-set reasoning.
- You must check ordinary bipartiteness of the complement, not of the original graph.
How to recognize this kind of problem
- The prompt asks about partitioning vertices into two pairwise-adjacent groups.
- A complement graph naturally converts clique conditions into non-edge conditions.
- The right solution is a graph transformation followed by a standard linear-time bipartite check.