Given a graph G = (V, E), an independent set is a set of vertices V, such that V
ID: 3706788 • Letter: G
Question
Given a graph G = (V, E), an independent set is a set of vertices V, such that V,-V and no two vertices in V are connected by an edge in E. The problem of determining the maximum-size independent set in a graph is known to be NP-complete, Here is the decision version of that problem: is an undirected graph with an independent set of size k) In this question, we investigate two related problems. (Be sure to turn the page for the second part!) (a) Suppose that G is a tree. Consider the following special case of the INDSET problem: undirected tree with an independent set of size k) Show that IST E PExplanation / Answer
In the given problem, we have to prove that we can find the solution of IST in polynomial time.
IST is given a graph G and a value k, we have check wether G has an independent set of size k.
The definition of independent set is already explained in the question.
This can be solved by a very important property of a tree:
Every tree is bipartite
The two disjoint set of vertices of a tree can be obtained by level order traversal of the tree in which, nodes at alternate levels are added in different sets. This can be done in polynomial time.
Now, if any of the disjoint set obtained contains vertices more then or equal to k, this means there exist an independent set of size k in G.
Hence we have solve the problem in polynomial time.
So, IST belongs to P
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.