Date: 9th Dec, 5:00 p.m. Venue: Zoom: https://us02web.zoom.us/j/84324728072?pwd=ZENXaVNDVmVNSTJBeHlHRzgrc2VWUT09 An optimal approximation algorithm for Feedback Vertex Set in Tournaments Pranabendu Misra Max-Planck Institute for Informatics, Saarbrucken, Germany. 09-12-20 Abstract 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.
|