Title: Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms

Description: Speaker: Dr. Fahad Panolan

Time: Monday, 14 January 2019, 10:30am
Venue: Department of Computer Science and Engineering, Room No. 109, 01st Floor, New CSE/CC Building

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.

This is joint work with Daniel Lokshtanov, Saket Saurabh, Roohani Sharma, and Meirav Zehavi.

Speaker Profile:
Dr. Fahad Panolan is a post-doctoral fellow at University of Bergen. He did his Phd at Institute of Mathematical Sciences, Chennai under the guidance of Prof. Saket Saurabh. He has also worked as a software engineer at Yahoo! Inc, Bangalore. His research interests are mainly Parameterized Algorithms and Complexity, Algorithms using matroids and matrix factorization, Graph Theory and Graph Algorithms, and Approximation Algorithms.

University of Bergen

Prof. Rohit Gurjar

Date: Monday, 14 January, 2019
Time: 10:30am IST
Access: Public
Category: Talk*
Created by: Department Calendar
Updated: Tuesday, 12 May, 2020 8:11am IST
Send Reminder: Yes  -  166 hours 9 minutes before start
Participants: Department Calendar
<office@cse.iitb.ac.in> (External User)
_NUC_department <all@cse.iitb.ac.in> (External User)