G12FCO -- Formal Computation

Problem Class 4 -- NP-completeness

Both of these may take you some time to construct a `proper' proof, but the `Aha!' should come pretty quickly if you're looking at things the right way.

1. Show that Longest Path is NP-complete. LP is the decision problem of determining whether a given network contains a simple path [that is, a path which encounters no vertex more than once] from A to B which is longer than some given length. [Hint: HC.] [`Shortest Path' is in P.]

2. A clique in a graph is a set of vertices such that every pair of them is [directly] connected by an edge belonging to the graph. Clique is the decision problem of determining whether or not a given graph has a clique with a given number of vertices. Show that Clique is NP-complete. [Hint: Draw a complete graph with some number of vertices (that is, join every pair of vertices). Paint some of the edges red and the rest blue. What is the relationship between a vertex cover of the red edges and a clique among the blue edges?]

top of page

G12FCO home page

Previous problem class

Next problem class

Lecture 13