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