Polynomial-Time Reductions

What is a Reduction?

A reduction from problem A to problem B shows that if we can solve B, we can solve A. This is the central tool for proving problems are "hard" in computational complexity theory.

Formally, problem A polynomial-time reduces to problem B (written A ≤ₚ B) if:

There exists a polynomial-time algorithm to transform any instance of A into an instance of B
The transformed instance has the same answer as the original
If we had a poly-time solver for B, we'd get a poly-time solver for A

Key insight: If A ≤ₚ B and B ∈ P, then A ∈ P. Equivalently, if A ≤ₚ B and A ∉ P, then B ∉ P.

Types of Reductions

Many-One (Karp) Reduction

Transform one instance of A to exactly one instance of B. This is the most restrictive and most commonly used type for NP-completeness proofs.

Turing (Cook) Reduction

Algorithm for A can make multiple oracle calls to B. More powerful, but harder to work with.

Parsimonious Reduction

Preserves the number of solutions — useful for counting problems (#P-completeness).

Example 1: Vertex Cover ≤ₚ Independent Set

Vertex Cover (VC): Find a set S of k vertices such that every edge has at least one endpoint in S.

Independent Set (IS): Find a set S of k vertices such that no two vertices in S share an edge.

Key observation: S is a vertex cover of G if and only if V − S is an independent set of G.

python

def vertex_cover_to_independent_set(graph, n_vertices, k):
    """
    Reduction: VC(G, k) → IS(G, n-k)
    
    G has a vertex cover of size k
    ⟺ G has an independent set of size (n - k)
    
    Proof:
    - Let C be a vertex cover of size k
    - Then V - C has size n - k
    - For any edge (u,v): at least one of u,v is in C
    - Therefore NEITHER u nor v are both in V-C
    - So V-C has no edges within it → V-C is an independent set
    """
    # Same graph, complementary parameter
    return independent_set(graph, n_vertices - k)

def vertex_cover_to_clique(graph, n_vertices, k):
    """
    Reduction: VC(G, k) → Clique(complement(G), n-k)
    
    G has a vertex cover of size k
    ⟺ complement(G) has a clique of size (n - k)
    """
    complement = build_complement(graph, n_vertices)
    return clique(complement, n_vertices - k)

Example 2: 3-SAT ≤ₚ Independent Set

This reduction proves Independent Set is NP-complete. Given a 3-SAT instance with clauses C₁, ..., Cₘ:

For each clause Cᵢ = (l₁ ∨ l₂ ∨ l₃), create a triangle of 3 nodes
Add a "conflict edge" between literal lᵢ in clause r and literal ¬lᵢ in clause s
Set k = m (number of clauses)

Claim: 3-SAT is satisfiable ↔ graph has an independent set of size k.

python

def sat_to_independent_set(clauses):
    """
    Build graph for 3-SAT → Independent Set reduction.
    Returns: (graph, k) where k = len(clauses)
    """
    nodes = []  # (clause_idx, literal)
    edges = []
    node_idx = {}
    
    # Create triangle for each clause
    for i, clause in enumerate(clauses):
        for j, literal in enumerate(clause):
            idx = len(nodes)
            node_idx[(i, j)] = idx
            nodes.append((i, literal))
    
    # Intra-clause edges (triangle)
    for i, clause in enumerate(clauses):
        for j in range(len(clause)):
            for l in range(j + 1, len(clause)):
                edges.append((node_idx[(i, j)], node_idx[(i, l)]))
    
    # Inter-clause conflict edges
    for i, clause_i in enumerate(clauses):
        for j_i, lit_i in enumerate(clause_i):
            for i2, clause_i2 in enumerate(clauses):
                if i >= i2:
                    continue
                for j_i2, lit_i2 in enumerate(clause_i2):
                    # Conflict: lit_i and lit_i2 are negations of each other
                    if lit_i == -lit_i2:
                        edges.append((node_idx[(i, j_i)], node_idx[(i2, j_i2)]))
    
    return nodes, edges, len(clauses)

Example 3: Hamiltonian Path ≤ₚ Travelling Salesman

Given an undirected graph G = (V, E), build a TSP instance:

Assign weight 1 to each edge in E
Assign weight 2 to each edge NOT in E
Budget B = |V| − 1

G has a Hamiltonian path ↔ TSP has a tour of cost ≤ B + 2 (the +2 accounts for returning to start).

The Reduction Recipe

To prove problem X is NP-complete:

Show X ∈ NP: Give a polynomial-time verifier (certificate check)
Choose a known NP-complete problem Y
Show Y ≤ₚ X: Give a poly-time transformation f such that

YES instance of Y → YES instance of X
NO instance of Y → NO instance of X

Practice Problems

Prove that Clique ≤ₚ Independent Set
Show that Hamiltonian Cycle ≤ₚ Hamiltonian Path
Reduce Subset Sum to Partition
Show that 3-Coloring ≤ₚ SAT

ADVANCED ALGORITHMS - NP-COMPLETENESS:Polynomial-Time Reductions