Random Sampling of Important Separators: New Bounds and New Applications

Speaker:

Huairui Chu (University of Electronic and Science Technology of China)

Time:

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

VooVmeeting:

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

ID: 447 185 012 Password: 1949

Venue:

Main Building

Abstract:

Important separator is a well-known concept for solving problems about graphs in parameterized algorithm sense. Marx and Razgon combined random sampling and important separators to provide a technique called random sampling of important separators (RSIS). They used this technique to solve Undirected Multicut problem. Chu’s work improves the probability bound from katex[/katex] to katex[/katex] by a simple lemma. This technique is also effective in some directed graph problems such as Directed Multiway Cut and Directed Subset Feedback Vertex Set. In this talk the algorithm of these two problems will be introduced and a new form of application of RSIS on Directed Subset Feedback Vertex Set will be discussed. Chu gives three algorithms: One for Directed Multiway Cut runs in $O^*(2^{O(k \log {k})})$ and two for Directed Subset Feedback Vertex Set run in $O^*(2^{O(k^2 \log {k})})$ and $O^*(2^{O(k \log {k}+k \log{|D|})})$ respectively.