Sample problems for tutorial #10

1. The independent set problem is defined in the textbook (Section 8.1) as follows. In a graph G=(V,E), a set of nodes S is independent if no two nodes in S are joined by an edge. The decision problem is "Given a graph G and a number k, does G contain an independent set of size at least k?"

   The clique problem is as follows. In a graph G=(V,E), a set of nodes S is called a clique if every pair of nodes in S are joined by an edge. The decision problem is "Given a graph G and a number k, does G contain a clique of size at least k?"

   1. Prove that the clique problem is in NP. More specifically, prove that, given a certificate corresponding to a subset of nodes in G, it is possible to verify, in polynomial time, that this subset is a clique of G with size k.
   2. The independent set problem is known to be NP complete. (This is proven in Section 8.2 and 8.4 of the textbook.) Prove that the clique problem is NP complete. More specifically, prove that you may reduce a known NP complete problem to the clique problem in polynomial time.
2. The Hamiltonian Path Problem is defined as follows. In a graph G=(V,E), a path that contains every vertex exactly once is called a Hamiltonian Path. The decision problem is "Given a graph G, does G contain a Hamiltonian Path?"

   The Bounded-Degree Spanning Tree Problem is defined as follows. In a graph G=(V,E), a spanning tree T has maximum degree at most d if every vertex in V has at most d incident edges that belong to T.

   1. Prove that the Bounded-Degree Spanning Tree Problem is in NP. More specifically, prove that, given a certificate corresponding to a subset of nodes in G, it is possible to verify, in polynomial time, that this subset is a spanning tree of G with degree at most d.
   2. The Hamiltonian Path problem is known to be NP complete. (The closely related Hamiltonian Cycle problem is proven to be NP complete in Section 8.5 of the textbook.) Prove that the Bounded-Degree Spanning Tree Problem is NP complete. More specifically, prove that you may reduce a known NP complete problem to the Bounded-Degree Spanning Tree problem in polynomial time.