Skip to interview prep
Apexed

393. What is a polynomial-time reduction? Show the reduction between vertex cover and independent set.

MediumComplexity classes

Technical
Show model answer

A reduction from A to B is a polynomial-time transformation f such that x is a yes-instance of A exactly when f(x) is a yes-instance of B. It shows B is at least as hard as A: a fast algorithm for B gives one for A.

In a graph G with n vertices, a set S is an independent set exactly when its complement V − S is a vertex cover: if no edge has both ends in S, every edge has an end outside S. So G has an independent set of size k if and only if it has a vertex cover of size n − k. The reduction just changes k, and it works in both directions. Similarly, independent sets in G are cliques in the complement graph, linking all three problems.

What is a polynomial-time reduction? Show the reduction between vertex cover and independent set. — Data structures & algorithms interview question — Apexed