In a conflict graph, how do maximum independent set, maximum clique and minimum vertex cover relate?
answer
- three names, one underlying decision
- who is in versus who is left out
- the two sizes sum to n
- clique lives in the complement graph
- translation costs only quadratic time
basics
~20 sThey are one problem in three costumes. A conflict-free set of sessions is an independent set; the vertices left out of it form a vertex cover; and the same set is a clique in the complemented graph. Solve one exactly, solve all three.
solid answer
~50 sTake a graph on `n` vertices. A set `S` has no edge inside it — an independent set — exactly when the vertices outside `S` touch every edge, which is the definition of a vertex cover; so the largest independent set and the smallest vertex cover always add up to `n`. And `S` is independent in the graph exactly when `S` is a clique in the **complement**, where every non-edge becomes an edge. Both translations are mechanical and cost `O(n^2)`, so a polynomial algorithm for any one of the three would give polynomial algorithms for the other two, and all three are NP-hard together. The identity is about exact optima only: it does not carry solution quality across when you settle for an approximate answer, and it does not mean every input is hard — on a graph with no odd cycle all three are solvable in polynomial time.
go deeper
Hold the one-line identity: the sessions you schedule together form an independent set, the ones you leave out form a vertex cover, and the two sizes add up to the total number of sessions.
Explain both translations and why they are cheap — complementing a graph is quadratic work and the cover identity is plain set complement. That cheapness is what makes the three problems stand or fall together.
Use the identity to pick the formulation that suits the data. A sparse conflict graph is comfortable stated as independent set and uncomfortable stated as clique, even though the classification is identical.
Decide where hardness is allowed to live. If your instances genuinely come from a family where these problems are tractable, that structural fact is worth protecting in the data model rather than rediscovering feature by feature.
## Three names for one decision Fix a graph whose vertices are sessions and whose edges join pairs that conflict. - An **independent set** is a set of vertices with no edge between any two of them — a group of sessions that can all run together. - A **clique** is a set of vertices with an edge between *every* two of them — a group that conflicts pairwise. - A **vertex cover** is a set of vertices touching every edge — a group whose removal leaves no conflict at all. They sound like three different questions. They are one question asked from three sides, and the translations between them are trivial. ## The two identities **Cover is the complement of independence.** A set `S` is independent exactly when every edge has at least one endpoint outside `S` — which is exactly the statement that the vertices outside `S` form a vertex cover. Therefore, on a graph with `n` vertices, the largest independent set and the smallest vertex cover satisfy a fixed relation: their sizes sum to `n`. **Clique lives in the complement graph.** Build the complement by keeping the vertices and flipping every pair: pairs that were joined become unjoined and vice versa. A set with no internal edges in the original has *all* internal edges in the complement. So maximum independent set in a graph is literally maximum clique in its complement. A worked instance, small enough to check by hand. Take four vertices in a path, `1-2-3-4`, with edges `{1,2}`, `{2,3}`, `{3,4}`: 1. Largest independent set: `{1,3}`, `{1,4}` and `{2,4}` all work, so the size is **2**, and no three vertices avoid all three edges. 2. Smallest vertex cover: `{2,3}` touches all three edges, so the size is **2**, and no single vertex touches all three. 3. The sum is `2 + 2 = 4`, which is the vertex count. ✔ 4. The complement has edges `{1,3}`, `{1,4}`, `{2,4}`. Its largest clique is a pair such as `{1,3}` — no triangle exists there, since `{3,4}` is missing. Size **2**, matching the independent set. ✔ ## What the equivalence does and does not buy | Problem | Question asked | Translation to the others | |---|---|---| | Maximum independent set | Largest conflict-free group | Complement of a minimum vertex cover | | Minimum vertex cover | Smallest group whose removal kills all conflicts | Complement of a maximum independent set | | Maximum clique | Largest all-conflicting group | Maximum independent set of the complement graph | What it buys: - **Classification.** All three are NP-hard, and they stand or fall together. An exact polynomial algorithm for one is an exact polynomial algorithm for all. - **Freedom of formulation.** You may state a requirement in whichever of the three reads most naturally to the people writing it down. What it does not buy: - **Approximate quality does not travel.** Settling for a near-optimal answer to one of these is a genuinely different proposition for each; the identity relates exact optima, and quality guarantees are a separate subject with its own results. - **It does not make every input hard.** NP-hardness is a worst-case statement over all graphs. On a graph with no odd cycle, the minimum vertex cover coincides with the largest set of pairwise-disjoint edges, and both are computable in polynomial time; on a tree a simple bottom-up rule suffices. Recognising that your instances live in such a family is often the entire win. - **It is not free of practical consequence.** Complementing a graph inverts density: a sparse conflict graph becomes a dense complement. The classification is unchanged, but the two formulations suit different data structures and behave very differently under a solver. ## Using it in an interview The expected move is to say the identity out loud rather than analyse each problem separately: *"picking who to schedule and picking who to drop are the same decision, so these are one problem"*. Then add the two caveats that separate a memorised fact from understanding — that the translation preserves exact optima rather than approximation quality, and that it says nothing about restricted families of graphs where the problem is genuinely easy.
- Does the complement translation change how an instance behaves in practice, even though it is polynomial?Yes, on density. A sparse conflict graph has a dense complement, so the clique formulation of the same instance carries far more edges and suits different data structures. Polynomial-time equivalence is a statement about classification; it never promises the translated instance is equally comfortable to attack.
- Is minimum vertex cover hard on every input, given that it is NP-hard in general?No. NP-hardness is worst-case over all inputs. On a graph with no odd cycle the minimum vertex cover equals the largest set of pairwise-disjoint edges, and both are computable in polynomial time; on a tree a bottom-up rule settles it. Knowing your instances fall in such a family is often the whole win.
Choosing guests so that no two feuding people are both invited is the same act as choosing whom to leave out so that every feud is broken. One list fixes the other; there is only ever one decision being made.
saying these in an interview costs you the question
- Looks for the clique in the original graph rather than in its complement.
- Says complementing the graph makes an NP-hard problem cheaper to solve.
- Claims the identity also carries approximate solution quality between the problems.
- Believes vertex cover is hard on every input because it is NP-hard in general.
- Adds maximum clique to minimum vertex cover to get the vertex count.