Chennai Mathematical Institute

Seminars




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.