Web of Reductions

web-of-reductions circuit-sat circuit-sat cnf-sat cnf-sat circuit-sat->cnf-sat [2] cnf-sat->circuit-sat [1] 3-sat 3-sat cnf-sat->3-sat [5] indset indset cnf-sat->indset [3] ilp ilp cnf-sat->ilp [17] 3-sat->cnf-sat [4] subset-sum subset-sum 3-sat->subset-sum [10] 3-color 3-color 3-sat->3-color [19] d-ham-path d-ham-path 3-sat->d-ham-path [20] d-ham-cycle d-ham-cycle 3-sat->d-ham-cycle [21] vertex-cover vertex-cover indset->vertex-cover [6] clique clique indset->clique [7] max-cut max-cut indset->max-cut [28] set-cover set-cover vertex-cover->set-cover [8] ham-cycle ham-cycle vertex-cover->ham-cycle [18] set-cover->ilp [11] tsp tsp ham-cycle->tsp [9] ham-path ham-path ham-cycle->ham-path [13] ham-cycle->d-ham-cycle [25] partition partition subset-sum->partition [12] knapsack knapsack subset-sum->knapsack [14] partition->subset-sum [15] best-partition best-partition partition->best-partition [27] makespan makespan partition->makespan [22] bin-packing bin-packing partition->bin-packing [23] best-partition->partition [26] knapsack->ilp [16] d-ham-cycle->ham-cycle [24]

Reduction Proofs

  1. CNF-SAT ≤P Circuit-SAT: Every CNF formula has an equivalent depth-2 circuit.
  2. Circuit-SAT ≤P CNF-SAT: CLRS ed3, Theorem 34.9, page 1080.
  3. CNF-SAT ≤P Independent Set: Algorithm Design, Kleinberg-Tardos, Theorem 8.8, page 460. (For every clause k, create i vertices if there are i variables in the clause. Draw an edge between all vertices of a clause and an edge between complementary vertices across clauses.)
  4. 3-CNF-SAT ≤L CNF-SAT: A 3-CNF-SAT instance is also a CNF-SAT instance.
  5. CNF-SAT ≤L 3-CNF-SAT
  6. Independent Set =L Vertex Cover: In a graph (V, E), S is a vertex cover iff V-S is an independent set.
  7. Independent Set =L Clique: S is an independent set in graph G iff S is a clique in the complement of G.
  8. Vertex Cover ≤P Set Cover: For each vertex v, create the set Sv of all edges incident on v. If some of these sets span the set of edges, then the corresponding vertices form a vertex cover.
  9. Hamiltonian Cycle ≤L Travelling Salesman Problem: Given a graph G, construct a weighted graph G' where c(u, v) = 0 if (u, v) in G and c(u, v) = 1 otherwise. Then G' has a 0-weight tour iff G has a hamiltonian cycle.
  10. 3-CNF-SAT ≤P Subset Sum: CLRS ed3, Theorem 34.15, page 1097.
  11. Set Cover ≤P Integer Linear Programming: Represent the set cover instance as a linear program. Each set corresponds to a boolean variable and the requirement of covering each element becomes a linear constraint.
  12. Subset Sum ≤P Set Partitioning: CLRS ed3, Exercise 34.5-5, page 1101. See solutions by Bodnar and Lohr.
  13. Hamiltonian Cycle ≤P Hamiltonian Path: CLRS ed3, Exercise 34.5-6, page 1101. See solutions by Bodnar and Lohr.
  14. Subset Sum ≤P Knapsack: For every number x in the set, create an item of weight x and size x. If the target is t, get a knapsack of size t. A subset sums to t iff we can get profit ≥ t.
  15. Set Partitioning ≤P Subset Sum: Let s be the sum of set X. X can be partitioned into 2 subsets of equal sum iff there is a subset of X of sum s/2.
  16. Knapsack ≤P Integer Linear Programming
  17. CNF-SAT ≤P Integer Linear Programming: Add a constraint for each clause. For example, '(u1 or !u2 or u3)' becomes 'u1 + (1-u2) + u3 ≥ 1'.
  18. Vertex Cover ≤P Hamiltonian Cycle: CLRS ed3, Theorem 34.13, page 1091.
  19. 3-CNF-SAT ≤P Graph 3-coloring: CLRS ed3, Problem 34.3, page 1103. See solutions by Bodnar and Lohr.
  20. 3-CNF-SAT ≤P Directed Hamiltonian Path: Computational Complexity (internet draft), Arora and Barak, Theorem 2.18, page 52.
  21. 3-CNF-SAT ≤P Directed Hamiltonian Cycle: Computational Complexity (internet draft), Arora and Barak, Theorem 2.18 (page 52) shows a polytime reduction from 3-sat to directed hamiltonian path. In the directed graph constructed there, add an edge from the end vertex to the start vertex.
  22. Set Partitioning ≤P Makespan scheduling: Let X be a set of integers with sum s. For each integer x, create a job which requires x units of time. Then X can be partitioned into 2 equal-sum subsets iff all these jobs can be finished in time ≤ s/2 on 2 processors.
  23. Set Partitioning ≤L Bin Packing: Let X be a set of integers with sum s. For each integer x, create an item of size x. Then X can be partitioned into 2 equal-sum subsets iff all these items can be packed in 2 bins.
  24. Directed Hamiltonian Cycle ≤P Hamiltonian Cycle: For every vertex v in directed graph, create vertices v1, v2, v3 in undirected graph. For every edge (u, v) in directed graph, add edge (u3, v1) in undirected graph. Directed graph has ham-cycle iff undirected graph has ham-cycle.
  25. Hamiltonian Cycle ≤P Directed Hamiltonian Cycle: Replace every undirected edge {u, v} by 2 directed edges (u, v) and (v, u). Directed graph has ham-cycle iff undirected graph has ham-cycle
  26. Best Set Partitioning ≤P Set Partitioning: CLRS ed3, Problem 34-2 d, page 1102. See solutions by Bodnar and Lohr.
  27. Set Partitioning ≤P Best Set Partitioning: A partition instance is a best-partition instance with difference 0.
  28. Independent Set ≤P Max cut

Contribute