Alice is solving an assignment on Graph Theory, and, she observed that cycles in

Question

Alice is solving an assignment on Graph Theory, and, she observed that cycles in a graph is what makes the questions difficult. She is determined to make all the graphs acyclic with the minimum loss of vertices. She thinks solving this question is easy, but is it? VERTEX DELETION: Given a directed graph G = (V, E), and an integer k is there a set V' subsetoforequalto V with |V'| lessthanorequalto k such that V' contains at least one vertex from every directed cycle in G? (a) Show that VERTEX DELETION is in NP. (b) Prove that VERTEX DELETION is NP-Complete by showing VERTEX COVER lessthanorequalto_P VERTEX DELETION.

Explanation / Answer

a. Vertex Deletion problem is solved by Non Deterministic Turing Machine in polynomial time. That means, by guessing. And therefore, it is a Class NP problem.

b. To Prove Vertex Deletion is NP complete:

We have, a problem is NP Complete if it satisfies below 2 conditions:

1. A problem is a NP( a problem can be solved by non deterministic turing machine in polynomial time)

2. For all other problems in NP, all these problems can be polynomially reducable to given problem.

Now We have Vertex Deletion is NP, already proved. If you extends the scale of vertex deletion problem, then it's impossible to find the solution in polynomial time.i.e. NP Complete problem

Thank you.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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