GRAPH SEPARATION IN PARAMETERIZED ALGORITHMS
M. S. Ramanujan · 2011
Parameterized Complexity is an exact algorithmic approach to deal with intractable computational problems having some small parameters. For decision problems with input size n, and a parameter k, the goal here is to design an algorithm with runtime f(k)nO(1) where f is an arbitrary function of k, as opposed to (in most cases,) a trivial n algorithm. Such algorithms are called fixed parameter tractable (FPT) and problems with FPT algorithms are said to be fixed parameter tractable (FPT). Such algorithms are practical when small values of the parameters cover practical ranges. Numerous computational problems have been solved by modelling these problems as problems on graphs and then applying known results in graph theory to extract some structure and use this in designing algorithms. In recent years, a more refined approach has been to model the problems of interest as separation problems on graphs and then solve them. This approach has been used to give FPT algorithms for a number of problems including MULTIWAY CUT, DIRECTED FEEDBACK VERTEX SET (DFVS) and ALMOST 2-SAT, with the last two being long standing open questions in the field of parameterized complexity. It is not only the case that a lot of problems have been modelled as separation problems on graphs, but these separation problems themselves appear to have a common underlying combinatorial structure. The aim of this thesis is to study a combinatorial object called important separators, and formally describe it as a tool with which a number of graph separation problems with certain properties can be solved. To this end, we first extend the existing notion of important separators, which has already been defined on undirected graphs, to directed graphs as well. Finally, we describe the FPT algorithms for the above three problems using the notion of important separators as an explicit tool.