Subset Feedback Vertex Set in Chordal Graph – Algorithms and Logic Group

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)
October 15, 2021 (Friday)

Venue:

Qingshuihe Campus

Abstract:

The Subset Feedback Vertex Set (SFVS) problem takes as input a graph $G$ and a subset of vertices $T$ in $G$ . The task is to find a minimal set $S$ of vertices from $G$ , such that in the remaining graph no cycle contains a vertex of $T$ . SFVS problem splits into two subproblems depending on whether one is allowed to remove terminal vertices. Restricted Subset Feedback Vertex Set (R-SFVS) problem refers to finding a subset feedback vertex set of the vertices in $G$ of size at most $k$ whereas the Unrestricted Subset Feedback Vertex Set (U-SFVS) problem refers to finding a subset feedback vertex set of the non-terminal in $G$ .

SFVS problem is also well-studied on many graph classes like chordal graphs. In this talk, a framework of designing parameterized algorithms for SFVS of these two subproblems when the input graph is chordal will be introduced. The results show that both the parameterized algorithm and exact algorithm for SFVS in Chordal Graph are improved.