next up previous index CD Book Algorithms
Next: Lecture 23 - approximation Up: No Title Previous: Lecture 21 - vertex

Lecture 22 - techniques for proving hardness

Hamiltonian Cycle

Instance: A graph G  

Question: Does the graph contains a HC, i.e. an ordered of the vertices tex2html_wrap_inline16072 ?

This problem is intimately relates to the Traveling Salesman.

Question: Is there an ordering of the vertices of a weighted graph such that tex2html_wrap_inline16074 ?

Clearly, tex2html_wrap_inline16076 . Assign each edge in G weight 1, any edge not in G weight 2. This new graph has a Traveling Salesman tour of cost n iff the graph is Hamiltonian. Thus TSP is NP-complete if we can show HC is NP-complete.

Theorem: Hamiltonian Circuit is NP-complete

Proof: Clearly HC is in NP-guess a permutation and check it out. To show it is complete, we use vertex cover. A vertex cover instance consists of a graph and a constant k, the minimum size of an acceptable cover. We must construct another graph. Each edge in the initial graph will be represented by the following component:

All further connections to this gadget will be through vertices tex2html_wrap_inline16078 , tex2html_wrap_inline16080 , tex2html_wrap_inline16082 and tex2html_wrap_inline16084 . The key observation about this gadget is that there are only three ways to traverse all the vertices:  

Note that in each case, we exit out the same side we entered. Each side of each edge gadget is associated with a vertex. Assuming some arbitrary order to the edges incident on a particular vertex, we can link successive gadgets by edges forming a chain of gadgets. Doing this for all vertices in the original graph creates n intertwined chains with n entry points and n exits.

Thus we have encoded the information about the initial graph. What about k? We set up k additional vertices and connect each of these to the n start points and n end points of each chain.

Total size of new graph: GE+K vertices and 12E+2kN+2E edges tex2html_wrap_inline16086 construction is polynomial in size and time.

We claim this graph has a HC iff G has a VC of size k.

  1. Suppose tex2html_wrap_inline16088 is a HC.

    Assume it starts at one of the k selector vertices. It must then go through one of the chains of gadgets until it reaches a different selector vertex.

    Since the tour is a HC, all gadgets are traversed. The k chains correspond to the vertices in the cover.

    Note that if both vertices associated with an edge are in the cover, the gadget will be traversal in two pieces - otherwise one chain suffices.

    To avoid visiting a vertex more than once, each chain is associated with a selector vertex.

  2. Now suppose we have a vertex cover of size tex2html_wrap_inline16090 .

    We can always add more vertices to the cover to bring it up to size k.

    For each vertex in the cover, start traversing the chain. At each entry point to a gadget, check if the other vertex is in the cover and traverse the gadget accordingly.

    Select the selector edges to complete the circuit.

Neat, sweet, and NP-complete.

To show that Longest Path or Hamiltonian Path is NP-complete, add start and stop vertices and distinguish the first and last selector vertices.  

This has a Hamiltonian path from start to stop iff the original graph has a vertex cover of size k.

Listen To Part 26-2

Other NP-complete Problems

Open: Graph Isomorphism, Composite Number, Minimum Length Triangulation.

Listen To Part 26-3

Polynomial or Exponential?

Just changing a problem a little can make the difference between it being in P or NP-complete:

P NP-complete
Shortest Path Longest Path
Eulerian Circuit Hamiltonian Circuit
Edge Cover Vertex Cover

The first thing you should do when you suspect a problem might be NP-complete is look in Garey and Johnson, Computers and Intractability. It contains a list of several hundred problems known to be NP-complete. Either what you are looking for will be there or you might find a closely related problem to use in a reduction.  

Listen To Part 26-4

Techniques for Proving NP-completeness

  1. Restriction - Show that a special case of the problem you are interested in is NP-complete. For example, the problem of finding a path of length k is really Hamiltonian Path.  
  2. Local Replacement - Make local changes to the structure. An example is the reduction tex2html_wrap_inline16094 . Another example is showing isomorphism is no easier for bipartite graphs:  

    For any graph, replacing an edge with makes it bipartite.
  3. Component Design - These are the ugly, elaborate constructions  

Listen To Part 26-5

The Art of Proving Hardness

Proving that problems are hard is an skill. Once you get the hang of it, it is surprisingly straightforward and pleasurable to do. Indeed, the dirty little secret of NP-completeness proofs is that they are usually easier to recreate than explain, in the same way that it is usually easier to rewrite old code than the try to understand it.

I offer the following advice to those needing to prove the hardness of a given problem:

Listen To Part 26-8

Now watch me try it!

To demonstrate how one goes about proving a problem hard, I accept the challenge of showing how a proof can be built on the fly.

I need a volunteer to pick a random problem from the 400+ hard problems in the back of Garey and Johnson.

Listen To Part 27-2

Dealing with NP-complete Problems


Option 1: Algorithm fast in the Average case

Examples are Branch-and-bound for the Traveling Salesman Problem, backtracking algorithms, etc.

Option 2: Heuristics

Heuristics are rules of thumb; fast methods to find a solution with no requirement that it be the best one.

Note that the theory of NP-completeness does not stipulate that it is hard to get close to the answer, only that it is hard to get the optimal answer.

Often, we can prove performance bounds on heuristics, that the resulting answer is within C times that of the optimal one.

next up previous index CD Book Algorithms
Next: Lecture 23 - approximation Up: No Title Previous: Lecture 21 - vertex

Mon Jun 2 09:21:39 EDT 1997