Invited Talk by Dr. R Krithika on The Parameterized Complexity of Cycle Packing: Indifference is Not an Issue

Title: The Parameterized Complexity of Cycle Packing: Indifference is Not an Issue
Speaker: Dr. R Krithika, Institute of Mathematical Sciences, Chennai
Host Faculty:  Dr. Subrahmanyam Kalyanasundaram
Room No: A-220, academic block A.


 In the Cycle Packing problem, we are given an undirected graph G, a positive integer r, and the task is to determine whether there exist r vertex-disjoint cycles. Cycle Packing is one of the first problems studied in the Parameterized Complexity framework and it is well known to be fixed-parameter tractable (FPT) with respect to the solution size r. In this talk, we will discuss the parameterized complexity of Cycle Packing with respect to a structural parameter, namely, distance to proper interval graphs (indifference graphs). We will show that this problem is FPT using the color coding technique, a greedy strategy and a dynamic programming routine based on structural properties of proper interval graphs. Several structural parameterizations for Cycle Packing have been studied in the literature and our FPT algorithm fills a gap in the ecology of such parameterizations. This is joint work with Abhishek Sahu (Institute of Mathematical Sciences), Saket Saurabh (Institute of Mathematical Sciences) and Meirav Zehavi (Ben-Gurion University) and is accepted for publication at LATIN 2018 (to be held in April 2018). The talk will be self-contained.

Speaker bio:

Krithika Ramaswamy is a postdoctoral researcher at the Institute of Mathematical Sciences, Chennai. Her research interests lie in the area of Parameterized Algorithms and Complexity. She obtained her PhD at the Indian Institute of Technology Madras and her thesis focussed on designing parameterized and approximation algorithms for finding various hitting sets in graphs. 

Tuesday, January 2, 2018 - 12:00