Kernelization for Feedback Vertex Set based on linear programming
- Speaker
- Tian Bai
- Affiliation
- University of Electronic and Science Technology of China
- Date
- Time
- – Asia/Shanghai
- 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 $(x, k)$ in time polynomial in $n = |x|$ and $k$, returns an equivalent instance $(x', k')$ 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.
Schedule
- 10:00-12:00 (Time in Beijing)
- 14:00-16:00 (Time in Auckland)
- May 21, 2021 (Friday)
Online Meeting
Link: https://meeting.tencent.com/s/QfT7QuGrXPBQ
ID: 582 848 199 Password: 1949