34-1 Independent set

An independent set of a graph $G = (V, E)$ is a subset $V' \subseteq V$ of vertices such that each edge in $E$ is incident on at most one vertex in $V'$. 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 $\text{NP-complete}$. ($\textit{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 $\text{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. ($\text{Hint:}$ Use the results of Section 26.3.)

(Omit!)