Random Sampling of Important Separators: New Bounds and New Applications

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 $2^{-O(k^2)}$ to $2^{-O(k \log {k})}$ 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.

Schedule

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

Online Meeting

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

ID: 447 185 012 Password: 1949