Solution Found!
Independent set An independent set of a graph G D .V; E/
Chapter 34, Problem 34-1(choose chapter or problem)
An independent set of a graph \(G=(V, E)\) is a subset \(V^{\prime} \subseteq V\) of vertices such that each edge in E is incident on at most one vertex in \(V^{\prime}\). The independent-set problem is to find a maximum-size independent set in G.
a. Formulate a related decision problem for the independent-set problem, and prove that it is NP-complete. (Hint: Reduce from the clique problem.)
b. Suppose that you are given a “black-box” subroutine to solve the decision problem you defined in part (a). Give an algorithm to find an independent set of maximum size. The running time of your algorithm should be polynomial in \(|V|\) and \(|E|\), counting queries to the black box as a single step.
Although the independent-set decision problem is NP-complete, certain special cases are polynomial-time solvable.
c. Give an efficient algorithm to solve the independent-set problem when each vertex in G has degree 2. Analyze the running time, and prove that your algorithm works correctly.
d. Give an efficient algorithm to solve the independent-set problem when G is bipartite. Analyze the running time, and prove that your algorithm works correctly. (Hint: Use the results of Section 26.3.)
Questions & Answers
QUESTION:
An independent set of a graph \(G=(V, E)\) is a subset \(V^{\prime} \subseteq V\) of vertices such that each edge in E is incident on at most one vertex in \(V^{\prime}\). The independent-set problem is to find a maximum-size independent set in G.
a. Formulate a related decision problem for the independent-set problem, and prove that it is NP-complete. (Hint: Reduce from the clique problem.)
b. Suppose that you are given a “black-box” subroutine to solve the decision problem you defined in part (a). Give an algorithm to find an independent set of maximum size. The running time of your algorithm should be polynomial in \(|V|\) and \(|E|\), counting queries to the black box as a single step.
Although the independent-set decision problem is NP-complete, certain special cases are polynomial-time solvable.
c. Give an efficient algorithm to solve the independent-set problem when each vertex in G has degree 2. Analyze the running time, and prove that your algorithm works correctly.
d. Give an efficient algorithm to solve the independent-set problem when G is bipartite. Analyze the running time, and prove that your algorithm works correctly. (Hint: Use the results of Section 26.3.)
ANSWER:Step 1 of 4
An independent set is , given a graph \(G=(V, E), V^{\prime} \subseteq V\) is an independent set if there are no edges between vertices in \(V^{\prime}\). The decision problem for the independent-set problem is as follows:
Let \((G, k)\) be an arbitrary instance of the clique problem, where \(k\) is the number of vertices in the clique. The problem is “Does there exist an independent set of size at least \(k\)?”
To prove that it is NP-complete,
Let \(G^{*}\) be the complement graph of \(G\). There exist an edge in \(G^{*}\) iff there is no edge in its complement, that is \(G^{*}\) has a clique of size \(k\) if its complement has an independent set of size \(k\). Then \(G\) has clique of size \(k\) if and only if \(G^{*}\) has an independent set of size \(k\). So the independent set problem is NP complete.