Introduction

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 2n2^{n} subsets. And as we'll see, these problems aren't just hard to solve exactly; they're famously hard to even approximate.

Find the Group

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">Click people to select a group. A <b>clique</b> = everyone knows everyone (all connected). An <b>independent set</b> = total strangers (none connected). The checker tells you live which one you've got.</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">Max clique</button>
  <button id="mi" type="button">Max independent set</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Clique = all pairs connected; independent set = no pair connected.
// Both are NP-hard (and hard to approximate). Here we brute-force the maxima.
const N = 7;
const POS = [[110, 60], [210, 60], [210, 150], [110, 150], [40, 30], [285, 35], [285, 180]];
const E = [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3], [0, 4], [1, 5], [2, 6], [4, 5]];
const adj = Array.from({ length: N }, () => new Set());
E.forEach(([u, v]) => { adj[u].add(v); adj[v].add(u); });
let sel = new Set(), mode = '';

function classify(arr) {
  let clq = true, ind = true;
  for (let a = 0; a < arr.length; a++) for (let b = a + 1; b < arr.length; b++) {
    if (adj[arr[a]].has(arr[b])) ind = false; else clq = false;
  }
  return { clq: clq && arr.length > 1, ind: ind && arr.length > 1 };
}

function render() {
  const arr = [...sel];
  const c = classify(arr);
  let s = '';
  E.forEach(([u, v]) => { s += '<line class="edge" x1="' + POS[u][0] + '" y1="' + POS[u][1] + '" x2="' + POS[v][0] + '" y2="' + POS[v][1] + '"/>'; });
  for (let i = 0; i < N; i++) {
    let cls = 'node';
    if (sel.has(i)) cls += mode === 'clq' ? ' clq' : (mode === 'ind' ? ' ind' : ' sel');
    s += '<circle class="' + cls + '" cx="' + POS[i][0] + '" cy="' + POS[i][1] + '" r="16" data-i="' + i + '"/>';
    s += '<text class="nlbl" x="' + POS[i][0] + '" y="' + POS[i][1] + '">' + i + '</text>';
  }
  const svg = document.getElementById('g');
  svg.innerHTML = s;
  svg.querySelectorAll('.node').forEach(n => n.addEventListener('click', () => { mode = ''; const i = +n.dataset.i; sel.has(i) ? sel.delete(i) : sel.add(i); render(); }));
  const st = document.getElementById('status');
  if (arr.length < 2) { st.className = 'status no'; st.textContent = 'Select at least two people.'; }
  else if (c.clq) { st.className = 'status clq'; st.textContent = fmt('✓ Clique of %length% — everyone knows everyone.', { length: arr.length }); }
  else if (c.ind) { st.className = 'status ind'; st.textContent = fmt('✓ Independent set of %length% — all strangers.', { length: arr.length }); }
  else { st.className = 'status no'; st.textContent = 'Neither — some pairs connected, some not.'; }
}

function best(want) {
  let bestSet = [];
  for (let m = 0; m < (1 << N); m++) {
    const arr = []; for (let i = 0; i < N; i++) if (m & (1 << i)) arr.push(i);
    const c = classify(arr);
    if ((want === 'clq' ? c.clq : c.ind) && arr.length > bestSet.length) bestSet = arr;
  }
  sel = new Set(bestSet); mode = want; render();
  const st = document.getElementById('status');
  st.className = 'status ' + want;
  st.textContent = fmt('%v% has %length% people: {%bestSet%}.', { v: want === 'clq' ? '★ Maximum clique' : '★ Maximum independent set', length: bestSet.length, bestSet: bestSet.join(', ') });
}

document.getElementById('mc').addEventListener('click', () => best('clq'));
document.getElementById('mi').addEventListener('click', () => best('ind'));
document.getElementById('reset').addEventListener('click', () => { sel = new Set(); mode = ''; render(); });
render();
Result
Console

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.

The Hard Part

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 2n2^{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 n1−ε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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/clique-independent-set/Content licensed under CC BY-NC 4.0.