Ch.11
NP-Hard and NP-Complete Problems

First, let us look at some history

As we have discussed in class, we have focused thus far on finding classes of problems that fit an algorithm type (greedy, divide and conquer, dynamic programming, etc). In this chapter we look instead at a new classification. Basically, we have problems that can be solved in a "short time" (polynomial) and ones that require vast amounts of time because of the numerous possibilities inherent in the problems (nonpolynomial). Reasons why from Garey and Johnson

We have an interesting aspect of Computer Science here since in studying the Theory of NP-Completeness, we do not provide a method of obtaining polynomial time algorithms, nor do we say that algorithms of this complexity do not exist.

Specifically, the focus of the study is to show that problems for which we have no known polynomial time algorithms are computationally related.

Within this group, we further differentiate the classification into smaller divisions: NP-Hard and NP-Complete.

NP stands for Nondeterministic Polynomial

Nondeterministic Algorithms

Algorithms such that the result of every operation is uniquely defined are called deterministic algorithms.

Up to now, we have focused on problems that were deterministic. (Even with our AI - we still used functions to determine a path given the information known)

Discussing nondeterministic algorithms requires three new functions:

  1. Choice(S): arbitrarily chooses one of the elements of set S

  2. Failure() signals an unsuccessful completion

  3. Success() signals a successful completion
A nondeterministc algorithm terminates unsuccessfully if and only if there exists no set of choices leading to a successful signal.

Algorithm 11.1 Nondeterministic search

  1. j:= Choice(1,n);

  2. if A[j] = x then {write (j); Success();}

  3. write(0); Failure();
The computing times for Choice, Success, and Failure are taken to be O(1).

Consider time for Search for (1) deterministic (2) nondeterministic. Consider sort time for (1) deterministic (2) nondeterministic. See text, algorithm 11.2 for nondeterministic Sort.

A machine capable of executing a nondeterminsistic algorithm in this way is called a nondeterministic machine.

Let us go one step further: It would be nice if we even knew if there was such an choice! (Consider - is there a proof for x?)

Decision problems

Definition 11.1: Any problem for which the answer is either zero or one is called a decision problem. An algorithm for a decision problem is termed a decision algorithm. Any problem that involves the identification of an optimal solution (either maximum or minimum) value of a given cost function is known as an optimization problem. An optimization algorithm is used to solve an optimization problem.

Decision problems: yes/no answer. Hence we are now limited to just Success and Failure answers (output).

Although this may sound very restrictive, note that many optimization problems can be recast into decision problems with the property that the decision problem can be solved in polynomial time iff the optimization problem can. Similarly, we can say that if the decision problem cannot be solved in polynomial time, then the optimization problem cannot either.

Most of this chapter demonstrates the theory of NP through examples. The most commonly seen are Hamiltonian Cycles, Cliques, Traveling Salesperson, Node Cover, Scheduling and Satisfiability. We will look at each of these in varied respects.

Here is the first:

Hamiltonian cycle

Let G= (V, E) be a connected graph. A Hamiltonian cycle is a round-trip path along n edges of G that visits every vertex once and returns to its starting position (book, page 365 see figure 7.15 as well).

    No H.C.

Directed vs. undirected

L1 : does G-> have a directed Hamiltonian cycle?

L2 : does G have an undirected Hamiltonian cycle?

L1, L2 are both decision problems.

Given the above two questions, one might also be led to consider

Does L1 L2?

Does L2 L1?

Why?           Hint: Humans are lazy ... if we have one, we potentially have the other

Consider:

Clearly a straightforward transformation does not work, HC on G does not imply a HC on G->

Ahhh, but be careful - this G-> is not what we would get if we had this G as a start.

Let's consider one at a time. How to solve for a Hamiltonian cycle - clearly the undirected appears easiest. Why? Let's try to ultimately "remodel" the directed so that it is easy too.

Two possibilities for solving the problem (more specifically, what is the problem?):

  1. UHC gives only yes/no answer (decision problem).       if only yes/no, we do not know when we do transformation back where it is, and hence not sure if the directed has the same cycle

  2. UHC gives the cycle if one exists.       Again, we need to be able to transform back to potential directed solution to make sure that the same cycle is present in the directed
OK, Consider possibilities: 4 nodes in the graph implies that we need 4 nodes and 4 edges for the HC, and also that each node will have a degree of 2. We see multiple choices for the undirected graph, but all do not transform to the directed.

Obviously it is easy to see if such exist in undirected - any trick to make directed easier?
Consider a transformation to make the directed "look" undirected.

In a directed graph, each edge has two parts, a tail and a head. Hence each node can be considered as two parts - the tail and/or head of some edge.
The bottom represents when a node starts at a tail (things I point to)
The top when a node ends at a head (things pointing to me). Can we formalize this?

Nodes become what looks like edges (3 nodes for each initial 1) and edges become what looks like ordered pairs of nodes. (Remember tails are at the bottom (or 3's))

G-> = (V->,E->)

V = {<u,1>, <u,2>, <u,3> | u V-> }

E = {(<u,3>, <v,1>) | <u,v>-> E->} U { (<u,1>, <u,2>), (<u,2>, <u,3>) | u V->}

Here is one that has a Hamiltonian cycle

Here are some that do not


Could you write an algorithm given this nifty technique?

THM: G-> has a DHC iff G has an UHC

Proof:

==> { G-> has a DHC => G has an UHC }

<== { G has a UHC => G-> has an DHC }

DONE

(Perhaps a bit more)

UHC DHC       trivial       discuss

Therefore UHC and DHC are polynomially equivalent since each can be reduced to the other in polynomial time.

Back to Decidability and NP Algorithms

The Question: Does a graph G contain a Hamiltonian Cycle? Can you give an NP algorithm to determine this?

Look how easy decidability algorithms are :-)

You may be thinking, "this all seems silly and trivial". Why do we consider decidability? It helps us determine if a problem is NP:

  1. choice to get rid of permutation aspect
  2. verify in polynomial time

Again, these classifications are going to be quite useful. But make sure you know the difference between
      * reductions (which require valid transformations),
      * NP algorithms,
      * and decision problems.

For example, consider this interesting relationship:

L1 L2 imples L1 is a special case of L2

L1 : DHC

L2 : Traveling Salesperson Problem (tour of minimum cost)

Given a directed graph G-> = (V, E->) and c: E-> --> R, find a DHC in G-> of minimum cost

If we know how to get a cycle with minimum cost, then we should be able to get the answer for just the cycle! (i.e., a DHC)

  1. take directed and convert to complete (all edges)
  2. assign costs

Discuss this problem, its definition, and what "answer" it provides.

To show that this algorithm does, indeed, transform the DHC to a TSP problem you would need also to show that a result in the transformation is equivalent to a result in the original problem. Specifically

Prove: G-> has a DHC iff Minimum Cost Tour = |V|.

Can you?

To be continued