IMSc Webinar

Advancing the Algorithmic Tool-kit for Parameterized Cut Problems

Roohani Sharma

IMSc

In this thesis we consider several (di)graph cut problems and study them from the perspective of parameterized complexity and kernelization. The goal of the study is three-fold: first to extend the otherwise limited understanding of parameterized cut problems on directed graphs, second to present novel applications of the rich toolkit available for undirected cut problems and third to develop tools that allow to reuse the algorithms to solve the respective problems in the presence of an additional constraint.

The concrete questions addressed in the thesis are inspired from some major open problems and concerns in the area. Some of these being the famously active open problem of the existence of a polynomial kernel for Directed Feedback Vertex/Arc Set, sub-exponentiality in FPT beyond tournaments, parameterized algorithms for partitioning problems beyond the classical partitioning problems, the existence of single exponential FPT algorithms for stable versions of classical cut problems and the parameterized complexity of Stable Multicut. We address the above questions either in full or extend all possible results known in literature that take steps to come closer to resolving the actual question.

***********************************************************************8

Meeting Details:

Meeting URL

bluejeans.com/544145125/3911?src=join_info

Meeting ID 544 145 125

Participant Passcode 3911

Want to dial in from a phone?

Dial one of the following numbers:
+1.408.419.1715 (United States(San Jose))
+1.408.915.6290 (United States(San Jose))
(see all numbers - www.bluejeans.com/numbers)

Enter the meeting ID and passcode followed by #

Connecting from a room system?
Dial: airtel.bjn.vc or 199.48.152.152 and enter your meeting ID & passcode