COMS 482: unofficial class blog

We reviewed for the prelim II today. See previous post: cs482.elliottback.com/archives/2005/04/10/prelim-ii-next-tuesday/

There are two general strategies for dealing with those recalcitrant NP-complete problems. You can either take advantage of special characteristics of the problem, or you can come up with an approximate solution. In this lecture, we will be looking at the former.

Imagine what happens when you run Independent Set on a Tree:

The nodes of the indepent set are labelled in red. How do we get an independent set for a tree? Simply, choosing the leaves first is optimal:

Let T = (V, E) be a tree and v be a leaf vertex. I claim that there is a maximum size independent set that contains v. Consider a max size independent set S. If v is in S, we are done. Assume v is not in S. Let u be a parent of v. If u is not in S, we can put v in S instead to get a larger independent set. If u is in S, we can take out u and put v into S to get S’, an independent set of same size = max size.

Here is an algorithm:

Place all leaves into S
while S is not empty {
    Color the leaves
    Delete leaves and parents
}

You can implement this in linear time using DFS–and even if your graph is not a tree, it still may have some tree-like pieces.

Sample NP-Complete Reductions:

Given n processes and m resources:

a) Each process needs several resources at once. Is there a way for k processes to be active at the same time?

Some ideas include Set Packing, Independent Set. To do it with Set Packing, you would ask if there are k subsets of processes that don’t intersect over resources.

b) Special case of (a) where k = 2.

c) Special case of (a) where there are 2 types of resources and processes require at most one of each type.

d) Each resource is requested by at most 2 processes.

PSPACE = {x | x has a polynomial space algorithm}

Given T = c1 ^ c2 ^ … ^ ck where each clauses c_i is an OR-clause with 3 terms (an instance of 3-SAT) , does there exist and x1 for all x2 does there exist an x3 for all x4 … for all xn-1 such that T is true? This is called quantified 3-SAT (QSAT), an is a kind of alternation thatsshows up in many game AI questions. I.e., is there a move for me such that for all of my opponents’ next move there is another good move for me such that … etc.

One idea for QSAT–try all truth assignments. Define: p^w = polynomial time algorithm given an “oracle” for w. What if you need a solution to an NP-complete problem? Sometimes there are special characteristics of a problem that allows a solution. Sometimes we can define a provably good approximation solution!

Look at vertex cover. Given G, k, is there a vertex cover of size <= k? So, there are n choose k possible vertex covers. We could try them all, but… that’s a lot of options. To check a vertex cover, try each edge e, see if at least one endpoint is in the cover, and repeat. This takes O(n²) time.

Claim: “If G has n nodes, with max-degree d, and if there is a vertex cover of size k, then G has at most k*d edges.”

k*d is better than O(n²). Let s be the vertex cover with |s| = k. There are at most d edges from each vertex in S, there are at most k*d places where S touches some edge either once or twice. |E| <= # touches <= k*d, so trying all the possibilities is no longer O(n choose k * k * (n-1)) but rather O(n^k+1 * k).

Observe that any graph with more than k*(n-1) edges cannot have a vertex cover of size k, and if there is a vertex cover of size k and we completely remove a vertex from the cover, then the remaining graph has a vertex cover of size k-1.

Find(G, k):
    if G has no edges return false
    if G has more than k*(n-1) edges return false
    choose e = (u, v)
        s1 = find(G - {u}, k-1)
        s2 = find(G - {v}, k-1)
        if s1 and s2 fail, then return false
        if(s1) return s1 + {u}
        if(s2) return s2 + {v}

This algorithm is O(k*n*2^k+1). The proof is left as an exercise to the reader.

Recall that we write “x is in P if there exists a polynomial time algorithm a(*) such that s is in x if and only a(s) returns yes.” Define x’ = { s | s not in x}. Is x’ in P? Yes, because we can define a’(*) as follows:

if a(s) returns “yes” then return “no” otherwise return “yes”

Let y be in NP. What about y’? Let y’ = {s | s not in y}. To say “y is in NP” means that there exists a polynomial time certifier b(*,*): s is in y if and only if there exists t such that b(s, t) returns “yes,” in polynomial bounded size. So, let’s look at y’:

s in y’
<=> s not in y
<=> ! there exists t such that b(s,t) returns “yes”
<=> for all t, b(s, t) returns “no”

Co-NP = {y’ | y is in NP}. Does NP = Co-NP? We don’t know. If we assume P=NP, though, it follows that P=Co-NP as well. Generally the consensus is that NP does not equal Co-NP. Here is a diagram that might help explain P, NP, Co-NP, and PSPACE:

P-SPACE is defined as {x | x has an algorithm using at most polynomial space}. P is a subset of PSPACE, because you cannot use more than polynomial space in only polynomial time. To say x is in PSPACE implies that x’ is in PSPACE using the same inversion algorithm as above. You can also create the following chain:

x in Co-NP => x’ in NP => x’ in SPACE => x in PSPACE

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