Polynomial-Time Reductions for NP-Complete Problems

1. Independent Set to Vertex Cover Reduction

Input

A graph G and an integer k.

Reduction Steps

1. Call the black-box for Vertex Cover with the input graph G.
2. Provide n-k as the target size, where n is the number of nodes in G.
3. Return the result ('yes' or 'no') from the black-box call.

2. SAT to Independent Set Reduction

Input

A CNF formula F.

Reduction Steps

1. Construct a graph G where the nodes of G are the literals occurring in F (with possible repetitions).
2. Add the following edges to G:
   • An edge joining every pair of complementary literals.
   • An edge joining any two literals that occur in the same clause.
3. Call the black-box for Independent Set with input graph G and an integer k, where k is the number of clauses in F.
4. Return the result ('yes' or 'no') from the black-box call.

3. Hamiltonian Path to Hamiltonian Cycle Reduction

Input

A graph G and two nodes, x and y.

Reduction Steps

1. Construct a new graph H from G. Initially, place all nodes and edges from G into H.
2. Add two new nodes to H, called x' and y'.
3. Add the following new edges: (x', x) and (y', y).
4. Call the black-box for the Hamiltonian Problem with input H.
5. Return the result ('yes' or 'no') from the previous call.

4. Independent Set to Diverse Subset Reduction

Input

A graph G and a non-negative integer k.

Reduction Steps

1. Construct a matrix A with one row for each node in G and one column for each edge in G. The rows can be seen as customers and the columns as products.
2. Assign every entry of matrix A to a 0 or 1. For a node v and an edge e in G, the entry A(v,e) is 1 if node v is incident to edge e, and 0 otherwise.
3. Call the black box for the Diverse Subset Problem with input (A, k).
4. Return the result ('yes' or 'no') from the previous call.

5. Independent Set to Clique Reduction

Input

A graph G and a non-negative integer k.

Reduction Steps

1. Construct the complementary graph, G', of G. The graph G' has the same nodes as G and contains precisely all those edges that are not in G.
2. Call the oracle for Clique with input (G', k).
3. Return the result ('yes' or 'no') from the previous call.

6. Vertex Cover to Set Cover Reduction

Input

A graph G and an integer k ≥ 0.

Reduction Steps

1. Construct a universe set U where each element is an edge of graph G (i.e., U is the set of edges E).
2. Construct a collection of subsets of U. For each node i in G, create a subset S_i that contains all edges incident to node i.
3. Call the oracle for Set Cover with the universe U, the collection of subsets {S_i for each node i in V}, and the integer k.
4. Return the result ('yes' or 'no') from the previous call.