University of Birmingham > Talks@bham > Study group in Graph Theory, Topology and Algorithms > An optimal approximation algorithm for Feedback Vertex Set in Tournaments

## An optimal approximation algorithm for Feedback Vertex Set in TournamentsAdd 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:Note that ex-directory lists are not shown. |
## Other listsMedical Imaging Research Seminars Midlands Logic Seminar Featured lists## Other talksMoving heat: from fusion reactors to batteries Roots of random functions Outerspacial 2-complexes Variational Bayesian inference for point processes - a latent variable approach Prediction of Toric Code Topological Order from Rydberg Blockade |