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

Hamiltonian Cycle Problem:

Given a graph G, is there “a path that visits each vertex once and return to the start,” i.e. a Hamiltonian Cycle?

Claim: “Hamiltonian Cycle is NP-complete.”

Proof: Hamiltonian Cycle is in NP because a given list of vertices can be checked for a tour in polynomial time. Now, we want to show that 3-SAT reduces to Hamiltonian Cycle in polynomial time. Thus, we need some way of mapping the variables and clauses to a hamiltonian cycle problem graph:

While this graph is complex at first, look at how it is built. For each variable, there is a row of at most 2n nodes, where n is the number of clauses. Two of these nodes are connected to each clause if the variable appears in that clause. The ends of each row of nodes are connected to the ends of the next. Walking left to right down a row means “true,” while right to left means “false.” In this way, a Hamiltonian cycle through the graph represents an assignment of truth values to the variables in a list of 3-SAT clauses.

Claim: “The 3-SAT boolean formula is satisfiable if and only if the graph has a hamiltonian cycle.”

Proof (=>): Assume the formula is satisfiable by some truth assignment. Choose one true term in each clause, traverse the graph moving across each variable’s path in the appropriate direction, and take a diversion to a clause node for each term chosen above. This path is a Hamiltonian cycle.

Proof (<=): Suppose there exists a Hamiltonian cycle c that traverses a variable’s row either left to right or right to left. Call one way true, and the other false. Ecah clause node is visited by a side-trip from a variable row. This variable corresponds to a true term in the clause.

External Links:

• Hamiltonian cycle
• Traveling salesman problem

Did you know you can read the CS482 Blog on Bloglines? Just click the button:

I was away in Florida–if you have notes, please email me!

Introductory Definitions:

A boolean variable is a variable that can either be assigned one of true or false. A term is either a boolean variable or its negation. A clause is built using terms and V (or operator).

SAT (Satisfiability):

Given a set of clauses c₁ … c_k over the variables x₁ … x_n, is there way to assign True and False to variables so that all clauses evaluate to true? SAT <=_p 3-SAT <=_p Independent Set.

3-SAT:

Given clauses c₁ … c_k each of length 3 over the variables x₁ … x_n, is there way to assign True and False to variables so that all clauses evaluate to true?

Claim: “3-SAT is NP-Complete”

Proof: Given a certificate (a set of assignments to variables) we can check in polynomial time that this satisfies all of the clauses. Next we want to show that 3-SAT reduces to independent set. Let’s map 3-SAT to a graph structure, obeying the following rules:

• Make sure there is at least one true term in each clause so that all clauses are thus true.
• Make sure x and !x are not both true

We can use these rules to construct a graph of k triangular clauses, connecting all x and !x between clauses. The independent set of this graph is the solution to 3-SAT:

Proof that 3-SAT reduces to Independent Set:

Claim: The original clauses can all be satisfied iff the graph has an independent set of size k.

Proof (=>): Suppose there exists a satisfying assignment. Then each clause has 1 or more true terms: Choose one of them. Put these into set S: we have k of them. For any 2 vertices in S there is no edge between them because 1) edges in the cause are not chosen and 2) edges between clauses are not chosen because a variable cannot be both true and false. So, S is an independent set.

Proof (<=): Assume we have an independent set S of size k. No 2 vertices can be in the same clause, so each clause has 1 vertex in S. For each vertex in S, we set the corresponding term to be true. X and !x are not both in S, so they cannot both be true. Make leftover variables either true or false. Each clause is satisfied by this assignment.