Assignment 5
no late homework would be accepted
1 (Exercise XXXXXXXXXXShow that the class P , viewed as a class of languages, is closed under union,
intersection, concatenation, complement, and Kleene closure. That is, if A,B ∈ P , then
A ∪B ∈ P , A ∩B ∈ P , AB ∈ P , Ā ∈ P and A∗ ∈ P .
2 (Exercise XXXXXXXXXXShow that the class NP is closed under union, intersection, concatenation, and
Kleene closure. Discuss the closure of NP under complement.
3 (Exercise XXXXXXXXXXShow that the problem of determining the satisfiability of Boolean formula in
disjunctive normal form is polynomial-time solvable.
4 (Exercise XXXXXXXXXXThe subgraph-isomorphism problem takes two graphs G1 and G2 and asks
whether G1 is isomorphic to a subgraph of G2. Show that the subgraph-isomorphism problem
is NP-complete.
5 (Exercise XXXXXXXXXXThe longest-simple-cycle problem is the problem of determining a simple cycle
(no repeated vertices) of maximum length in a graph. Show that this problem is NP-hard.
6 Show that the following problem is NP-complete: Given a graph G, determine whether G contains
a Hamiltonian path where a path is Hamiltonian if it passes every vertex exactly once.
7 Show that the following problem is NP-hard: Given a graph, find a spanning tree to minimize
the number of leaves.
8 Given a graph, find the maximum independent set. (An independent set is a subset of vertices
which are not adjacent each other.)
1