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' SubsetEqual V with |V'| lessthanorequalto k such that V' contains at least one vertex from every directed cycle in G? Show that VERTEX DELETION is in NP. Prove that VERTEX DELETION is NP-Complete by showing VERTEX COVER lessthanorequalto P VERTEX DELETION.

Explanation / Answer

a) Vertex deletion is a NP problem.

We can remove k vertices and then run depth first search from each of te vertices(to test for cycles).

Next, we reduce the graph to Vertex Cover(VC).

We make VC of our G with a newly constructed G' with each edge of G {u,v} connected oppositely as {v,u}. G' contains the same vertices.

Now, we show that there is a vertex cover of size k in G if and only if there is a subset of k vertices in G' whose removal breaks all cycles. First, assume that there is a vertex cover of size k in G. Now, remove these k vertices from G' along with the edges incident upon them. Notice that for any directed edge (u; v)2 G' , at least one of u or v must have been removed, because one of u or v must have been in our vertex cover. Thus, after removing these k vertices and their incident edges from G', no two vertices have an edge between them, and consequently there can be no cycles.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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