NP-Complete Assignment

  1. A graph G= (V, E) is said to be isomorphic to another graph G' = (V', E') if there exists a function f: V --> V' such that for all (u,v) E,     (f(u), f(v)) E'.     (f is one to one, i.e., for all u, v E, f(u) = f(v) ==> u = v.)
    (See also Chapter 10, Exercise 10 on page 377)

    Subgraph Isomorphism Problem

    Given two graphs G and H, is G isomorphic to a subgraph of H?     Show that the subgraph isomorphism problem is NP-Complete.

    First, an illustration:

  2. Longest Path

    Given a graph G and a positive integer K, is there a simple path in G of length (number of edges on path) at least K?
    (Note: You may not assume that the end points of the path are provided as part of the problem instance.) Show that the longest path is NP-Complete.

  3. [Feedback Node Set] Horowitz, Sahni and Rajasekaran: Ch. 11, Ex. 5 page 530
    Let G = (V, E) be a directed graph. Let S V be a subset of vertices such that deletion of S and all edges incident to vertices in S results in a graph G' with no directed cycles. Such an S is a feedback node set. The size of S is the number of vertices in S. The feedback node set decision problem (FNS) is to determine for a given input k if G has a feedback node set of size at most k.
    (a) Show that node cover decision problem FNS
    (b) Write a polynomial time nondeterministic algorithm for NFS.