Tímea Tamási: FPT-approximation for FPT Problems (Paper by Lokshtanov, Misra, Ramanujan, Saurabh and Zehavi)

Applied Discrete Math seminar

Abstract:

Over the past decade, research has focused on the design of parametrized
approximation algorithms for W[1]-hard problems. In this paper, authors have
studied FPT-approximation for problems that are FPT (i.e. that can be solved
in time f(k) n^(O(1)) for some parameter k). I am going to present a general
scheme to design 2-approximation algorithms for cut problems, with running
time significantly faster than the corresponding FPT-algorithm, and then
exemplify it for the Directed Feedback Vertex Set and Directed Subset Feedback
Vertex Set problems.