Advancing the Algorithmic tool-kit for parameterized cut problems[HBNI Th175]

Abstract

With this thesis we advance the algorithmic tool-kit, and contribute to the existing literature concerning parameterized (di)graph cut problems. The study has been conducted from three broad perspectives. The first is the urge to understand and contribute to the otherwise limited algorithmic tool-kit available to tackle digraph (cut) problems. The second concerns the exploration of the rich structural and algorithmic tool-kit available to tackle undirected graph cut problems, thereby resulting in engineering some of the existing techniques and exhibiting a broader scope of their applicability, together with contributing more advanced tools to the existing machinery. The third concerns building tools that allow “re-usability” of algorithms to solve problems under the presence of certain additional constraints. Towards the above objectives, the concrete questions that are addressed in the thesis are inspired from some major open problems and concerns in the field of parameterized complexity and kernelization. Some of these being the famously active open problem of the existence of a polynomial kernel for Directed Feedback Vertex/Arc Set, sub-exponential parameterized algorithms for digraph problems 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 the results known in literature that take steps to come closer to resolving the actual question. Below we describe the specific results that we obtain. We also remark that the below mentioned results, in several cases, lead to various enticing insights. In particular, through one of our results, we establish connections between kernelization and fault-tolerant subgraphs. Another result is based on a novel application of important separators in the design of polynomial kernels, which is a rare sight in kernelization. Yet other results give an interesting and useful combinatorial insight about the problem at hand.