| Title | : | Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms |
| Speaker | : | Fahad Panolan (University of Bergen, Norway) |
| Details | : | Mon, 10 Dec, 2018 4:00 PM @ A M Turing Hall |
| Abstract: | : | We present two new combinatorial tools for the design of parameterized algorithms. The first is a simple linear time randomized algorithm that given as input a d-degenerate graph G and an integer k, outputs an independent set Y, such that for every independent set X in G of size at most k, X is a subset of Y with "large probability". The second is a new (deterministic) polynomial time graph sparsification procedure that given a graph G, a set T = {{s_1, t_1}, {s_2, t_2},...,{s_{ell},t_{ell}}} of terminal pairs and an integer k, returns an induced subgraph G' of G that maintains {em all} the inclusion minimal multicuts of G of size at most k, and does not contain any (k+2)-vertex connected set of size $2^{O(k)}$. In particular, G' is a $2^{O(k)}$-degenerate graph. Put together, our new tools yield new randomized fixed parameter tractable (FPT) algorithms for Stable s-t Separator, Stable Odd Cycle Transversal and Stable Multicut on general graphs. All of our algorithms can be derandomized at the cost of a small overhead in the running time. |
