Cliques and Strangers

Picture a party as a graph: each person is a dot, and a line joins two people who know each other. Two natural questions pop out. What's the largest group where everyone knows everyone? — that's a clique. And what's the largest group of complete strangers, no two of whom know each other? — that's an independent set.

They're mirror images. A clique in a graph is exactly an independent set in its complement (flip every connection to a non-connection and vice versa). And both connect to a third problem from this site: the nodes outside a maximum independent set form a minimum vertex cover. Three problems, one underlying structure.

For a small party you can hunt by eye. But the only obvious method — check every possible subset of people — runs into $2^{n}$ subsets. And as we'll see, these problems aren't just hard to solve exactly; they're famously hard to even approximate.

Try it. Click nodes to select a group. The checker tells you live whether your selection is a clique (everyone connected), an independent set (no one connected), or neither.

<p class="hint">{{hint}}</p>
<svg id="g" viewBox="0 0 320 230" class="g"></svg>
<div id="status" class="status"></div>
<div class="btns">
  <button id="mc" type="button">{{btn_max_clique}}</button>
  <button id="mi" type="button">{{btn_max_ind}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.g { width: 100%; max-width: 460px; background: #f4f7f9; border: 1px solid #e2e6eb; border-radius: 10px; display: block; }
.edge { stroke: #c2ccd6; stroke-width: 2.5; }
.node { fill: #8aa0b3; cursor: pointer; transition: fill .1s; }
.node:hover { fill: #6f8699; }
.node.sel { fill: #457b9d; }
.node.clq { fill: #2a9d8f; }
.node.ind { fill: #b5651d; }
.nlbl { font: 700 12px ui-monospace, monospace; fill: #fff; text-anchor: middle; dominant-baseline: central; pointer-events: none; }
.status { font-weight: 800; min-height: 1.4em; margin: .8rem 0 .5rem; font-size: 1rem; }
.status.clq { color: #0a7d33; } .status.ind { color: #b5651d; } .status.no { color: #777; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

// Code not found

Hunt for the biggest clique and the biggest independent set by hand, then press the buttons to reveal the true maxima (found by brute force). Notice they're different sizes — and that finding them got harder the moment the graph grew past a handful of nodes.

These two are heavyweights of hardness:

• Checking a group is easy: confirm every pair is connected (clique) or no pair is (independent set).
• Brute force examines all $2^{n}$ subsets — hopeless beyond tiny graphs.
• They're NP-hard, among the original problems Karp proved NP-complete in 1972.
• Even approximation is hard. Unlike vertex cover (which has a simple 2-approximation), maximum clique and independent set are inapproximable: under standard assumptions, no efficient algorithm can even get within a factor of $n^{1-\varepsilon}$ of the best. That's about as hard as approximation gets.
• The complement trio. Max clique, max independent set, and min vertex cover are three views of the same structure — solve one and you've solved all three.
• In practice branch-and-bound, parameterized algorithms and heuristics handle real graphs surprisingly well, even though the worst case is brutal.

So this is hardness in its purest form: hard to solve, and — unusually — hard to even come close.

Tight groups and conflict-free sets show up across science and engineering:

• Social networks: finding tightly knit communities (cliques) or sets of mutually unrelated users.
• Bioinformatics: clusters in protein-interaction and gene networks often correspond to cliques.
• Scheduling: an independent set in a conflict graph is a set of tasks that can run together without clashing.
• Wireless networks: independent sets choose transmitters that won't interfere.
• Finance and fraud: cliques can reveal coordinated groups or unusual clusters.

Whenever you need either "all mutually compatible" or "all mutually exclusive," one of these problems is hiding underneath.

Cliques and independent sets are two sides of one coin, and together with vertex cover they form a classic trio: solve any one and you've answered all three. They're a tour of how deep hardness can go — not only NP-hard, but resistant even to approximation, a rare and humbling property.

And yet the everyday questions they encode — who forms a tight community? which tasks can safely run together? — get answered constantly, because clever branch-and-bound and heuristics tame the typical case. It's the recurring theme of this site: worst-case impossibility and everyday practicality, living side by side.