An optimal approximation algorithm for Feedback Vertex Set in Tournaments

Add to your list(s) Download to your calendar using vCal

• Pranabendu Misra, Saarbrücken
• Tuesday 09 February 2021, 14:00-15:00
• https://bham-ac-uk.zoom.us/j/87113090115.

If you have a question about this talk, please contact Johannes Carmesin.

In the Feedback Vertex Set problem, given a directed graph G, the task is to remove a minimum number of vertices to make it acyclic. Even when restricted to the class of Tournaments, i.e. complete directed graphs, this problem remains NP-Complete. It is easy to show that the problem admits a 3-approximation algorithm, and under the Unique Games Conjecture it cannot have a better than 2-approximation. Previous results improving upon the 3-approximation were highly non-trivial, and it was a long-standing open problem to obtain a 2-approximation for it. In this work we give a simple randomized algorithm to resolve this question. This result appeared in SODA 2020 .

This talk is part of the Study group in Graph Theory, Topology and Algorithms series.

This talk is included in these lists:

• https://bham-ac-uk.zoom.us/j/87113090115

Note that ex-directory lists are not shown.