NPC Examples

Bart Massey

Reductions and Approximations

• Reduction of 3-SAT to Integer Programming

• Reduction of 3-SAT to Vertex Cover

• Reduction of Independent Set to Generalized Movie Jobs

• Reduction of Hamiltonian Cycle to TSP

• 2-Approximation of Vertex Cover

• 2-Approximation of Euclidean TSP

Integer Programming

• RESTRICTED INTEGER PROGRAMMING

  • Given: A set of linear inequalities over variables

  • Question: Is there an assignment of integers to the variables that makes all the inequalities true?

• Example

  x + y + z ≤ 3

  y + z ≥ x

  x ≥ 2

  Nope. x + y + z must be at least 4

• Special case of Restricted Linear Programming: allow the values to be rational (real) numbers

• Integer programming is kind of a big deal

• Standard heuristic is to "relax" to LP instance, solve LP instance efficiently, then (if there's a solution to the LP instance) try the integer values for each variable that are closest to the LP value

3-SAT → Integer Programming

• Let x[i] be the variables in a 3-SAT instance, and C be the set of clauses.

• For each x[i], add a new variable y[i] which is equal to not x[i]. Replace all the not x[i] instances in clauses with y[i]

• Generate an IP instance via

  For each i:

  x[i] ≥ 0

  x[i] ≤ 1

  y[i] ≥ 0

  y[i] ≤ 1

  x[i] + y[i] = 1

  For each clause in C: Sum of variables in C ≥ 1

• If the 3-SAT instance is SAT, that assignment gives a solution to the IP

• If the IP instance is solvable, that gives us a solution to the SAT instance

• The general case of IP contains an optimization component we don't need. The reduction of this to Restricted IP is trivial

Hamiltonian Cycle

• HAMILTONIAN CYCLE

  • Given: Graph G = (V,E)

  • Question: Does there exist a circle subgraph of G including all of V?

• Known to be NPC

Hamiltonian Cycle → k-TSP

• Construct the complete graph for the k-TSP

• Give each edge a weight of 2 if it is not part of the HC graph, and 1 otherwise

• Choose k = |V|

• If there is a Hamiltonian cycle, it gives a k-TSP solution

• If there is a k-TSP solution, it gives a Hamiltonian cycle

Vertex Cover

• VERTEX k-COVER

  • Given: a graph G = (V, E), a bound k

  • Question: Does there exists a subset C of V with |C| <= k such that every edge in E hits at least one vertex in C?

• Note that we have already changed this to a decision problem

• We flip between decision and optimization problems pretty casually around here

3-SAT → Vertex Cover

• For each x[i] and y[i], build a "variable gadget" consisting of that pair of vertices connected by an edge. We will consider x[i] to be true if y[i] is included in C and otherwise y[i] must be included in C and we will consider x[i] false

• For each clause, build a "clause gadget" consisting of a triangle connecting all the variables in the clause.

• Connect the variable gadgets to the clause gadgets by putting an edge between each corresponding variable

• Set k = |x| + 2|C|

• Note that this requires at least one end of each connecting edge be covered. It will require |x| vertices to cover the variable gadgets, plus 2|C| vertices to cover the clause gadgets

• If the 3-SAT problem is SAT, it is easy to see that a satisfying assignment induces a k-Vertex Cover of our graph

• If there is a k-Vertex Cover of our graph, a SAT assignment can be read off the variable gadgets

2-Approximation of Vertex Cover

• Repeat until done: Pick an edge e from the graph, add both ends v[i], v[j] to C, add e to E, delete all edges touching v[i] or v[j]

• The result is guaranteed to be a Vertex Cover, since every edge will impinge on either 1 or 2 vertices in C

• The result is guaranteed to be at most twice the minimum cover, since at best you could delete one of the two vertices covering each edge in E

Generalized Movie Jobs

Euclidean Path

• EUCLIDEAN PATH

  • Given: Set V of points on the Euclidean plane

  • Find: Permutation p of S minimizing the sum of the distances between successive points in p

• Note that we removed the requirement to return to the origin. Is the problem still NPC?

2-Approximation of Euclidean Path

• Construct a minimum-weight spanning tree on the complete graph of vertices in the TSP

• A "shortcut" path that traces the MWST skipping all visited vertices will never be longer than twice the MWST weight

• The MWST weight is a lower bound on the Euclidean path length, because you have to visit each vertex at least once

• Similar (but more complicated) argument applies to Euclidean TSP

What To Do With Your Hard Problem?

• If it is not obviously in NP, give up. These are really hard problems

• Try to prove it NP-hard. Failure to do so may imply a polytime algorithm

• Given NPC proof:

  • See if a polytime approximation is good enough

  • See if a state-space search can solve your instances, or at least get close

  • See if you really really need everything that makes the problem hard