You have an efficient algorithm for finding the maximum independent set in any graph. A colleague claims this immediately yields an efficient algorithm for maximum clique. Is this correct, and why?
ANo, because clique and independent set require fundamentally different search strategies
BYes, because a maximum clique in G equals a maximum independent set in the complement graph of G, and complement construction is a polynomial-time operation
CYes, but only for sparse graphs where the complement is dense enough to be tractable
DNo, because maximum clique is NP-complete while maximum independent set is solvable in polynomial time
The complement graph Ḡ has an edge wherever G does not and vice versa. A set S forms a clique in G (every pair connected) if and only if S forms an independent set in Ḡ (no pair connected). Since computing the complement takes polynomial time, any algorithm for independent set in Ḡ directly solves clique in G — with no asymptotic overhead. Both problems are NP-complete; the point is that they are computationally equivalent via this graph complement reduction.
Question 2 Multiple Choice
Vertex Cover has a simple 2-approximation algorithm, while Clique has no known constant-factor approximation. What does this tell us about NP-complete problems?
AVertex Cover must not be truly NP-complete if it can be approximated
BNP-completeness characterizes worst-case exact complexity; NP-complete problems can differ dramatically in how well they can be approximately solved
CClique is harder than Vertex Cover because graph density makes clique detection more complex
DBoth problems actually share the same approximation guarantees; the comparison is misleading
NP-completeness is a statement about exact polynomial-time solvability — all NP-complete problems are equivalent in that sense. But approximability is a separate question, and NP-complete problems can behave very differently. Vertex Cover's 2-approximation follows from a simple greedy argument (take both endpoints of any uncovered edge, repeat). Clique's approximation hardness is related to the PCP theorem and shows that even finding an n^(1−ε) approximation is NP-hard. Sharing NP-completeness says nothing about how efficiently a problem can be approximately solved.
Question 3 True / False
If S is a vertex cover in graph G, then V − S (the remaining vertices) is necessarily an independent set in G.
TTrue
FFalse
Answer: True
Proof: suppose V − S contained an edge (u, v). Then neither endpoint is in S. But S is a vertex cover, so every edge must have at least one endpoint in S — contradiction. Therefore V − S has no edges, meaning it is an independent set. This relationship is the key structural link between vertex cover and independent set: every vertex cover corresponds to an independent set (the remaining vertices) and vice versa.
Question 4 True / False
Clique and Vertex Cover are NP-complete because they are essentially the same problem stated in different terms.
TTrue
FFalse
Answer: False
They are related through a chain of polynomial reductions and complement graph transformations, but they are structurally distinct problems asking different questions (dense local structure vs. global edge coverage). More importantly, despite sharing NP-completeness, they behave very differently in practice: Vertex Cover has constant-factor approximation algorithms and fixed-parameter tractable exact algorithms, while Clique is much harder to approximate. Calling them 'the same problem' misses these practically important distinctions.
Question 5 Short Answer
Explain the relationship between the clique problem and the independent set problem using complement graphs, and why this implies the two problems have the same computational complexity.
Think about your answer, then reveal below.
Model answer: The complement graph Ḡ of G has the same vertex set but the opposite edge set: there is an edge in Ḡ between u and v if and only if there is no edge in G. A set S is a clique in G (all vertices mutually connected) if and only if S is an independent set in Ḡ (no two vertices connected). Since complement construction takes O(V²) time — polynomial — any polynomial-time algorithm for one problem directly yields a polynomial-time algorithm for the other, and any proof of hardness for one transfers to the other. They are polynomial-time equivalent.
This complement relationship is why NP-completeness proofs for the two problems can be chained. Clique was shown NP-complete by reduction from 3-SAT; Independent Set's NP-completeness follows immediately via complement. Vertex Cover is then handled by the V − S independent set correspondence. Understanding these structural bridges is how theorists build the 'NP-completeness ecosystem' from a few hard problems.