Lesson · Intractability and Approximation · Hardness that travels

One Structure, Three Problems

Independent set, vertex cover and clique are the same question in three notations, and the translation is not an approximation or a correspondence between optima — it is an identity holding on every subset of the vertices. The lab checks it on all 32 subsets of a five-cycle rather than on the largest one, because an identity tested only at the optimum is tested at its easiest case.

Open the interactive lesson Practice

S is independent in G ⟺ V − S is a vertex cover of G S is independent in G ⟺ S is a clique in the complement of G on the five-cycle: 11 independent sets = 11 covers = 11 cliques, over 32 subsets α = 2, τ = 3, α + τ = 5 = n three problems, one structure — so a hardness result about one is about all three

Two equivalences, checked on every subset rather than on the optimum

Core ideas

What this lesson establishes

The first idea is the identity itself, which is one line and is the tightest relationship on this course. The second is why checking it at the optimum would be checking almost nothing. The third is what the identity does and does not transfer.

Complementing the set, and complementing the graph

Two different complements are at work and confusing them is the usual error. Taking V - S complements the SET and turns an independent set into a vertex cover of the same graph. Taking the complement GRAPH, where u and v are joined exactly when they were not, turns an independent set into a clique on the same vertices. Each equivalence is an immediate consequence of the definitions, and together they say that three problem names describe one piece of structure.

An identity checked at the optimum is barely checked

The relation α + τ = n between the largest independent set and the smallest cover is a corollary, and it is the form most often quoted. It is also the weakest test of the underlying claim: it compares two numbers on one pair of sets. The panel instead walks all 32 subsets and asks, for each, whether the three verdicts agree — 32 tests of the equivalence rather than one test of its consequence.

What transfers, and in which direction

Because the map is a bijection on instances and on solutions, a hardness result about any one of the three transfers to the other two, and so does a polynomial algorithm. That symmetry is unusual: most reductions on this course run one way only. It also means that a special case where one of them is easy is a special case where all three are, which is the shape the vertex cover lesson later depends on.

The material

Two equivalences, the identity they imply, and the enumeration that tests them

The three problems, the two one-line proofs, the corollary about the optima, and what the lab checks on every subset.

Definition · Three problems on one graph

An independent set is a set of vertices no two of which are joined. A vertex cover is a set of vertices touching every edge. A clique is a set of vertices every two of which are joined. Write α for the size of the largest independent set and τ for the size of the smallest vertex cover.

Theorem · The two equivalences

For every subset S of the vertices of a graph G: S is independent in G if and only if V - S is a vertex cover of G; and S is independent in G if and only if S is a clique in the complement of G.

Take an edge uv. If S is independent it does not contain both ends, so at least one end is in V - S, so V - S touches every edge and is a cover. Conversely if V - S is a cover then no edge has both ends outside it, that is, no edge has both ends in S, so S is independent.

For the second: S is independent in G exactly when no pair inside S is joined in G, which is exactly when every pair inside S is joined in the complement, which is exactly when S is a clique there. Both arguments are the definition read twice, and that is why the equivalence holds subset by subset rather than only at the extremes.

□

Theorem · Gallai's identity

α + τ = n for every graph on n vertices.

≤

≥

□

What the lab measured on the five-cycle

The loaded graph is the cycle on five vertices. The panel reports 32 subsets checked, 11 independent sets, 11 vertex covers and 11 cliques in the complement; α = 2, τ = 3, and α + τ = 5, which is n. The two equivalences are reported as holding on every one of the 32, not as holding at the optimum — the panel says how many subsets it checked precisely so that the difference is visible.

That the three counts are equal is a consequence of the equivalences and a useful check on them, since a mismatch anywhere would separate them. It is worth noticing that 11 is not a round number and is not 2^5 divided by anything obvious: it is whatever the graph gives, and both sides give it.

Example · The complement of a five-cycle is a five-cycle

Joining the pairs the cycle leaves out gives the edges 1-3, 1-4, 2-4, 2-5 and 3-5, which form the cycle 1, 3, 5, 2, 4. So this graph is isomorphic to its own complement, and the clique problem on the complement is the independent set problem on another five-cycle. The largest clique there has 2 vertices, matching α.

Why this matters for the rest of the course

Everything proved hard for one of these three is hard for the other two, with no new gadget. That is why the approximation lessons later on can talk about vertex cover while the reduction lessons talked about independent set, and why the two are not two subjects. It also sets up a warning: the approximability of the three is not shared, because an approximation ratio is a statement about sizes and the map S ↦ V - S does not preserve ratios. A cover within a factor 2 of the smallest says nothing useful about the largest independent set.

So the identity transfers exact answers perfectly and approximate answers not at all. Both halves of that sentence are worth holding, because the first makes the three problems interchangeable in the hardness chapters and the second makes them completely different problems in the approximation ones.

Interactive

Independent set, vertex cover and clique are one problem

S is independent exactly when V − S is a cover, and exactly when S is a clique in the complement — checked on every subset, not only the largest

Step through the subsets and watch the three columns move together

The map here is an involution: apply it twice and you are back where you started, so it is a bijection in the strongest sense the kit contains. The three optima are found by three separate exhaustive searches, and α + τ = n falls out of them rather than being asserted.

Worked example

Edges, as u-v

Which subset to show0

Show in the table

Vertices and edges—

Subsets checked—

Independent sets—

Vertex covers—

Cliques in the complement—

α and τ, and α + τ—

S independent equals V−S covers—

S independent equals S a clique—

These are the same question asked three ways. If no edge has both ends in S then every edge has an end outside it, so V−S is a cover; and if no edge of G joins two members of S then every pair of them is joined in the complement, so S is a clique there. Both directions are checked here on every subset, not on the largest one — an identity tested only at the optimum is tested at its easiest case.

Method

Translating between the three, without losing what does not translate

The translation is mechanical; the discipline is in knowing which quantities survive it.

Name which complement you are taking

Complementing the set gives a cover of the same graph. Complementing the graph gives a clique on the same vertices. Writing “the complement” without saying which is the fastest way to produce a sentence that is half right.

Check the equivalence on a subset that is not optimal

Take any set at all — a single vertex, the empty set, everything — and run the three tests. The claim is subset by subset, so a non-optimal subset is a legitimate test and a much more informative one than the extreme case.

Use the identity to convert exact answers only

α + τ = n converts an exact largest independent set into an exact smallest cover and back. Do not push an approximation through it: a cover that is twice the smallest gives an independent set with no ratio guarantee whatever, and the arithmetic that looks like it should work does not.

Carry hardness in the direction you need it

A reduction into independent set plus this equivalence is a reduction into vertex cover and into clique, at no cost. When you need a problem to be hard, reduce to whichever of the three is most convenient and translate.

Three names, one structure

Score 0 / 0

Choose the answer you can justify.

All 32 subsets of the five-cycle, and the three columns that agree

The graph is the cycle 1-2, 2-3, 3-4, 4-5, 5-1. Its complement has the edges 1-3, 1-4, 2-4, 2-5, 3-5. A few subsets of each size, with the three verdicts.

S independent in G V − S covers G S a clique in the complement {} yes yes yes {1} yes yes yes {1, 3} yes yes yes {1, 2} no no no {1, 3, 5} no no no {2, 4, 5} no no no {1, 2, 3, 4} no no no over all 32 subsets: 11 independent 11 covers 11 cliques no subset on which the three verdicts disagree α = 2 attained by {1, 3} τ = 3 attained by {1, 2, 4} α + τ = 5 = n

The subset {1, 3, 5} is the one to look at hardest. It is three vertices of a five-cycle and it is not independent, because 5 and 1 are adjacent. Its complement {2, 4} misses the edge 5-1, so it is not a cover. And in the complement graph 1 and 3 are joined but 3 and 5 are joined while 5 and 1 are not, so it is not a clique. Three different-looking checks, one answer, and none of them involved an optimum.

The empty set and the full set are the degenerate rows and they are included on purpose. The empty set is independent, its complement is everything and covers, and it is vacuously a clique. A routine that special-cased the extremes would pass a check that skipped them.

For a faded rehearsal, switch to the two disjoint triangles and predict the three counts before running it. The supplied first move: an independent set can take at most one vertex from each triangle, so count the sets of size 0, 1 and 2 by hand. Then say what the complement graph looks like, and check α + τ against 6.

Common mistakes

Confusing the two complements“Take the complement” means the set in one equivalence and the graph in the other. Taking the complement graph and then looking for a cover in it, or taking V - S and then looking for a clique, produces statements that are false and look like the theorem.

Pushing an approximation through the identityThe identity is exact and the arithmetic with it is subtraction, which does not preserve ratios. This is not a technicality: vertex cover has a 2-approximation and the maximum independent set has no constant-factor approximation at all unless P = NP, and these two facts sit on either side of a subtraction.

Reading 11 = 11 = 11 as the theoremEqual counts are a consequence and a good check. The theorem is that the three verdicts agree subset by subset, and three equal totals could in principle arise from disagreements that cancel. The panel reports both the counts and the subset-by-subset verdict for that reason.

Check your understanding

✓

Finish when you can move a problem between the three forms and say which quantities survive the move.

You should be able to prove both equivalences in a line each, derive α + τ = n from them, check the equivalence on a non-optimal subset of a graph you drew yourself, and explain why an approximation ratio does not transfer across the identity.

Note: Every reduction so far has been graph to graph or formula to graph. “Numbers as Gadgets” changes the material: the transformed instance is a list of integers, and the reason the construction works is that no column of a base-ten addition can carry.