Problem Reduction

1. Introduction

A reduction is a way of transforming one problem into another problem. Suppose you have a problem A which you do not know how to solve. However, you know about an algorithm to solve problem B. If you can "transform" problem A into an instance of problem B (call it instance A_B), you can use the known algorithm for B to solve the "transformed" version A_B, and obtain the solution for A with the solution attained, by "reversing the transformation". We then say that A reduces to B.

1-1. Why Are Reductions Important?

Through reductions, we have another tool to solve problems. Furthermore, with an efficient "transformation", reductions provide the ability to compare the "hardness" of different problems.

1-2. Polynomial-time Reductions

Given two decision problems A and B, a polynomial-time reduction from A to B, denoted A ≤p B, is a transformation from instance a of A to instance b of B such that:

  1. a is a YES-instance for A if and only if b is a YES-instance for B.
    (A YES-instance is an instance of the decision problem whose answer is YES/True).
  2. The transformation takes polynomial time in the size of a.

With a polynomial-time reduction, we will be able to claim that the problem of solving A is only as hard as solving B.

However, if B is "hard", it does not imply that A is "hard". Likewise, if A is "easy", it does not mean that B is "easy".

2. 2

3. 3

4. 4

5. 5

6. 6

7. 7

8. Untitled Slide

9. Visualization

This visualization shows the network of reductions from different NP-complete decision problems to another. In theory, since all these problems are NP-complete, they can all be reduced to one another, but the transformation can become very convoluted for some problems.

9-1. Visualization Components

A vertex contains the name of an NP-complete decision problem. Hover over it to see its full name, or click on it to open the relevant slide that describes the problem.

An edge between vertices opens the slide which contains the proof of reduction from one problem to the other, in the direction of the arrow. [Soon: Green arrow indicates that we have digitize the reduction proof. Black arrow indicates that we have not done so.]

10. C-SAT

The Circuit-Satisfiability problem (C-SAT) is the decision problem of determining whether a given Boolean circuit (using AND, OR, NOT gates) has an assignment of its inputs that makes the output true. In other words, it asks whether the inputs to a given Boolean circuit can be consistently set to 1 or 0 such that the circuit outputs 1. If that is the case, the circuit is called satisfiable. Otherwise, the circuit is called unsatisfiable.

11. 11

12. Untitled Slide

13. Clique

A clique is a set of vertices such that there exists an edge between every pair of distinct vertices in the set. More formally, for a set of vertices C, ∀ v ∈ C, ∃ an edge (u, v) ∀ u ≠ v ∈ C. Then the size of the clique is the number of vertices in the set C.

The CLIQUE decision problem asks the following question on a graph G = (V, E): Does there exist a complete subgraph in G of at least size k?

14. Vertex-Cover

15. Hamiltonian-Cycle

16. Travelling-Salesperson-Problem

17. Subset-Sum

18. Knapsack

19. Independent-Set

20. 3-D-Matching

21. Partition-Into-Triangles

22. Feedback-Edge-Set

23. Set-Cover

24. Partition

25. Dominating-Set

Given a graph G = (V, E), a dominating set D is a subset of vertices such that for all other vertices u that are not in D, there exists some vertex v in D such that (u, v) is an edge in G (i.e., u is adjacent to v).

The Dominating-Set decision problem asks if given an integer k, there exists a dominating set in G of at most size k.