COMS 482: unofficial class blog

The Travelling Salesman Problem (TSP):

Given distances between n cities and a bound D, is there a tour (visit all cities and return home) of cost at most D? Note that using TSP to prove NP-completeness of other problems is quite hard.

Claim: “TSP is NP-complete”

Proof: TSP is in the set NP. Given a valid tour, we can check that it is valid and has a cost &lt= D in polynomial time. Then, we want to show that Hamiltonian Cycle reduces to TSP in polynomial time. Given an HC problem as a graph G, we can show how to build the travelling salesman problem. Using the same vertices, place an edge between each pair with cost 1 if the edge exists in G, otherwise place the edge with cost 2.

Claim: “G has a Hamiltonian Cycle if and only if G’ has a TSP tour of cost &lt= n (vertices)”

Proof (=>): Assume G has a HC. Then the cycle in G’ is a tour and its cost is <= n.

Proof (<=): Assume G’ has a TSP tour of cost <= n. Every node is visited, and each edge has cost 1. The corresponding cycle is a valid HC.

3D Matching:

Given disjoint sets X, Y, and Z each of size n and given a set of triples T is a subset of (X, Y, Z) is there a subset of T of size n that covers all X + Y + Z? We can show that 3-SAT reduces to 3D Matching in polynomial time, so 3D matching is NP-complete.

Graph Coloring:

A graph g is said to have a k-coloring if there is a way to assign colors to vertices such that all adjacent verticex do not share the same color. Given a graph g and a bound k, is G k-colorable? Graph coloring is NP-complete, but on planar graphs 2-coloring has a simple DFS algorithm, and >=4-coloring simply returns “yes.”

Subset Sum:

Given w₁, … , w_n in {Naturals} and a target w_i is there a subset of w₁, … , w_n whose sum is exactly w_i?

NP-Complete “Types”:

All the NP Complete problems we have covered so far can be grouped by similarity into the following categories:

• Packing problems: Set Packing, Independent Set
• Covering problems: Vertex & Set Cover
• Partitioning problems: 3D Matching, Graph coloring
• Sequencing problems: Hamiltonian Cycle, Hamiltonian Path, Travelling Salesman Problem
• Numerical problems: Subset sum
• Constraint problems: SAT, 3-SAT, and Circuit-SAT