Kernelization for Feedback Vertex Set based on linear programming

Speaker:

Tian Bai (University of Electronic and Science Technology of China)

Time:

10:00-12:00 (Time in Beijing)
14:00-16:00 (Time in Auckland)
May 21, 2021 (Friday)

VooVmeeting:

Link: https://meeting.tencent.com/s/QfT7QuGrXPBQ

ID: 582 848 199 Password: 1949

Venue:

Main Building

Abstract:

Feedback Vertex Set (FVS) is a problem to determine whether a given undirected graph has a vertex set of size at most a given parameter $k$ hitting all the cycles in the graph. FVS is one of the Karp’s 21 NP-complete problems and is the most comprehensively studied problems in the field of parameterized complexity. A kernelization algorithm (or kernel) for a parameterized problem is an algorithm that, given an instance katex[/katex] in time polynomial in $n = |x|$ and $k$ , returns an equivalent instance katex[/katex] of the same problem such that $k’, |x’| \leq g(k)$ for some computable function $g(\cdot)$ . In this talk, we will focus on the current best kernel of size $2k^{2} + k$ for FVS based on linear programming. This result was proposed by Iwata in ICALP 2017. In addition, we will discuss the linear programming for FVS obtained by Iwata, Wahlastrom and Yoshida which was published in SIAM Journal on Computing 2016.