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 listsSchool of Mathematics events Astrophysics Talks Series Condensed Matter Physics Seminars## Other talksIntegral equation methods for acoustic scattering by fractals Harness light-matter interaction in low-dimensional materials and nanostructures: from advanced light manipulation to smart photonic devices TBA Gravity wave detection and new findings Kneser Graphs are Hamiltonian Kolmogorov-Smirnov type testing for structural breaks: A new adjusted-range based self-normalization approach |