Problem 4:34-1 about Independent set 34-1: Independent set. An independent set o
ID: 655382 • Letter: P
Question
Problem 4:34-1 about Independent set
34-1: Independent set. An independent set of a graph G = (V, E) is a subset V
0 ? 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. Formulate a related decision problem for the independent-set problem, and prove that it is NP-complete. (Hint: Reduce from the clique problem.)The decision version of independent set is as follow. Given a graph G = (V, E) and integer 1 ? k ? |V |, decide whether there is an independent set V
Explanation / Answer
Independent set