G12FCO -- Formal Computation

Problem Class 4 -- NP-completeness -- solutions

1. Longest Path: Start with an arbitrary instance of HC. Convert this [evidently in polynomial time] to an instance of LP by giving every edge of the network the length 1, by choosing the endpoint A in LP to be an arbitrary node [e.g. the first] of the graph, setting B to be the same node, and asking whether there is a path of length greater than N-1, where N is the number of nodes. Clearly, there is such a path if and only if there is a Hamiltonian circuit.

   So HC transf LP. Since HC is NP-complete, and LP is clearly in NP, LP must also be NP-complete.

   [If you're unhappy about A and B being the same point, choose B to be a neighbour of A, ask for paths of length greater than N-2, repeat for all neighbours of A.]

2. Clique: Any pair of nodes not in a vertex cover cannot be joined by an edge in the given graph, and therefore must be joined by an edge in the complementary graph [the graph in which all edges originally present are deleted and all nodes not originally joined become joined]. In terms of the hint, any vertex cover of the red edges corresponds to a clique among the unfortified villages in the blue edges. So an arbitrary instance of VC can be transformed [evidently in polynomial time] into an instance of Clique by taking the complementary graph and asking for a clique that includes N-V vertices, where N is the number of `villages' and V is the number allowed for the vertex cover.

   Final details left as an exercise.

top of page

G12FCO home page

Previous discussion

Next discussion

Problem class