# 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) numbersInteger 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