Reductions

Reductions

What is a Reduction?

A reduction from problem A to problem B shows that if we can solve B, we can solve A.

Polynomial-Time Reduction

Problem A reduces to problem B (A ≤ₚ B) if:

• There exists polynomial-time algorithm to transform A instances to B instances
• Solution to B instance gives solution to A instance

Types of Reductions

Many-One Reduction

Transform one instance of A to one instance of B.

Turing Reduction

Can make multiple calls to B solver.

Example: Vertex Cover ≤ₚ Independent Set

def vertex_cover_to_independent_set(graph, k):
    """
    Reduce Vertex Cover to Independent Set.
    VC: Find k vertices covering all edges
    IS: Find k vertices with no edges between them
    """
    # Complement: IS in G = VC in G'
    # Same graph, k' = |V| - k
    return independent_set(graph, len(graph) - k)

Practice Problems

1. Reduce Vertex Cover to Clique
2. Reduce 3-SAT to Independent Set
3. Reduce Hamiltonian Path to TSP