Complexity Theory: Polynomial-Time Reductions

Posted on | In

Complexity Theory: Polynomial-Time Reductions

Introduction

So far, our goal has been to design efficient algorithms. In Complexity Theory, the goal is the opposite: to identify hard problems for which no efficient algorithm exists.

Key idea: Compare the difficulty of different problems. If we prove that some problem is “harder” than a famous open problem that has remained unsolved for decades, this provides strong evidence that the problem is also hard.

We only consider decision problems with yes/no answers.

Polynomial-Time Reduction

Definition 1. $Y$ is polynomial-time reducible to $X$, written $Y \leq_P X$, if given a black box that solves $X$, any instance of $Y$ can be solved using a polynomial number of basic operations and a polynomial number of black-box calls.

Intuitively, $Y \leq_P X$ means “$X$ is at least as hard as $Y$.”

Theorem 1. If $Y \leq_P X$ and $X$ can be solved in polynomial time, then $Y$ can also be solved in polynomial time.

Proof. Let $A$ be an algorithm for $Y$ and $B$ be a polynomial-time algorithm for $X$. Run $A$ but replace black-box calls with $B$. The $X$ instances written by $A$ have polynomial size, and polynomials are closed under composition, so the total running time is polynomial. ∎

Corollary 1. If $Y \leq_P X$ and $Y$ cannot be solved in polynomial time, then $X$ cannot be solved in polynomial time.

Lemma 2 (Transitivity). If $Z \leq_P Y$ and $Y \leq_P X$, then $Z \leq_P X$.

Independent Set ↔ Vertex Cover

Problem Definitions

Problem 1 (Independent Set). Given $G = (V, E)$ and integer $k$: does an independent set of size $\geq k$ exist?

An independent set $S$: no two nodes in $S$ are adjacent.

Problem 2 (Vertex Cover). Given $G = (V, E)$ and integer $k$: does a vertex cover of size $\leq k$ exist?

A vertex cover $S$: every edge $e \in E$ has at least one endpoint in $S$.

Reduction

Lemma 3. $S \subseteq V$ is an independent set $\iff$ $V \setminus S$ is a vertex cover.

Proof.

  • $(\Rightarrow)$: If $S$ is independent, for every edge $(u,v)$, at least one endpoint is in $V \setminus S$.
  • $(\Leftarrow)$: If $V \setminus S$ is a vertex cover, any two vertices $u, v$ in $S$ have $(u,v) \notin E$. ∎

Theorem 2. Independent Set $\leq_P$ Vertex Cover (and vice versa — they are equally hard).

Proof. Given $G = (V,E)$ and $k$, ask the Vertex Cover oracle “Does $G$ have a vertex cover of size $\leq \lvert V\rvert-k$?” By Lemma 3, this answer is the answer to the original problem. ∎

Vertex Cover → Set Cover

Problem 3 (Set Cover). Given a base set $U$, subsets $S_1, \ldots, S_m \subseteq U$, and integer $k$: do at most $k$ of the $S_i$’s have union equal to $U$?

Vertex Cover is a special case of Set Cover (edges = elements to cover, vertices = covering sets).

Theorem 3. Vertex Cover $\leq_P$ Set Cover.

Proof. Given Vertex Cover instance $G = (V,E)$, $k$, construct:

  • Base set $U = E$
  • For each vertex $i \in V$: $S_i = \lbrace\text{all edges incident to }i\rbrace$
  • $k’ = k$

The Vertex Cover instance is yes $\iff$ the Set Cover instance is yes. ∎

The chain of reductions established so far:

\[\text{Independent Set} \leq_P \text{Vertex Cover} \leq_P \text{Set Cover}\]

Equivalence of Optimization and Decision Versions

Remark. The optimization version of Independent Set (computing the maximum independent set size) and the decision version are equally hard.

  • Optimization → decision: trivial
  • Decision → optimization: run the decision version for $k = 0, 1, \ldots, \lvert V\rvert$ (binary search suffices)

This equivalence justifies focusing only on yes/no decision problems throughout complexity theory.