|
10:30--11:45, Seminar Hall A 2-Approximation Algorithm for Weighted Feedback Vertex Set in Tournaments Geevarghese Philip Chennai Mathematical Institute. 18-01-19 Abstract A tournament is a directed graph T such that every pair of vertices in T is connected by an arc. A feedback vertex set is a set S of vertices in T such that deleting S from T gives a directed graph with no directed cycles. We consider the Weighted Feedback Vertex Set problem in tournaments. Here the input consists of a tournament T and a weight function w which assigns non-negative integer weights to vertices of T. The task is to find a feedback vertex set S in T with the minimum total weight. This problem is NP-hard, even in the unweighted case where the goal is to find a feedback vertex set of the minimum cardinality. We give the first (randomized) polynomial-time factor-2 approximation algorithm for the weighted version; this improves on the previous best 7/3-factor approximation due Mnich et al. (presented at ESA 2016). Assuming the Unique Games Conjecture, ours is the best possible approximation ratio achievable in polynomial time. The algorithm combines three simple algorithmic ideas to get the desired approximation factor in randomized polynomial time. The talk will be self-contained, and my goal is to make it accessible to anyone with an interest in algorithms. Having done a first course in undergraduate Algorithms will help, but is not a strict requirement to understand most of the talk. This is joint work with Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan, and Saket Saurabh. The manuscript is online at https://arxiv.org/abs/1809.08437 .
|
