Q2. Suppose G = (V, E) is an undirected graph. A STRONGLY INDEPENDENT SET is a s

Question

Q2. Suppose G = (V, E) is an undirected graph. A STRONGLY INDEPENDENT SET is a subset S of vertices such that for any two vertices u, v ? S there is no path of length ? 2 between u and v. Consider the following Strongly Independent Set (SIS) problem: Given an undirected graph G = (V, E) and an integer k, does G have a strongly independent set of size ? k? Prove SIS is NP-complete.

Note: For the following problem, you can assume that INDEPENDENT SET, VERTEX COVER, 3-SAT, HAMILTONIAN PATH, and GRAPH COLORING are NP-complete.

Explanation / Answer

First, note that this problem is in NP, because we can guess an independent set of size k and check it in polynomial time.
To show that it is NP-hard, we will reduce from VERTEX-COVER. An instance of VERTEX-COVER is a graph G and a positive integer k. We accept if there is a set of k vertices such
that every edge is incident to at least one of the vertices in our set.An independent set is a set of k vertices that have no edges between them.Note that, if S is a vertex cover of G, then V ? S is an independent set, because at least one
vertex of every edge is contained in S. Similarly, if S' is an independent set, then V ? S' is a vertex cover.
So our reduction will take G and k and produce the same graph G, and the integer n ? k.
(This obviously takes polynomial time.) There is a vertex cover of size k if and only if thereis an independent set of size n ? k. Therefore, INDEPENDENT-SET is NP-complete.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.