NP-Complete

1. Prove that the following problem is NP-Complete.
Input: Set S, Collection A_i,...,A_m of subsets of S, positive integer k.
Output: Is there a sub-collection of size k such that they are pair-wise disjoint? In other words, among the collection of m subsets of S, are there k that are pairwise disjoint?

2. Prove that the following problem is NP-Complete.
Input: Graph G, positive k₁ and k₂
Output: Does G contain both a clique of size k₁ and an independent set of size k₂?

3. The subgraph isomorphism problem takes as input two undirected graphs G₁ and G₂ and asks whether G₁ is a subgraph of G₂. In other words,the problem asks whether there is a one-to-one function f mapping the vertices of G₁ to the vertices of G₂ ,such that edge (u, v) exists in G₁ iff (f(u)f(v)) exists in G₂.
Show that the subgraph isomorphism problem is NP-complete

4. A feedback vertex set in a directed graph G = (V,E) is a subset V' of V , such that V' contains at least one vertex from each directed cycle in G. The feedback vertex set problem (FVS) is: given a directed graph G and an integer k, does G have a feedback vertex set with at most k vertices? Prove FVS is NP-Complete.

<< Back to Tech Archives