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

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.

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.

Organization:
University of Bergen



Host:
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)