Parameterized graph separation problems: new techniques and algorithms[HBNI Th59]

Abstract

Menger's theorem, which states that the minimum number of vertices whose removal disconnects two vertices s and t in a graph is equal to the maximum number of pairwise vertex disjoint paths from s to t in the graph, is an extremely fundamental theorem in combinatorial optimization and it is known that the minimum s-t cut can be computed in polynomial time. Generalizations of the problem of finding the minimum set of vertices disconnecting two vertices in graph, are called graph separation problems. The main problems the author studies in this thesis are such graph separation problems. The fact that very natural generalizations of the s-t cut problem turn out to be NP-complete has motivated the study of these problems in the framework of Parameterized Complexity and the study of these problems has even emerged as an extremely active and independent subfield over the last few years. This thesis results to design new techniques and frameworks to obtain new as well as improved FPT algorithms for certain kinds of parameterized graph separation problems; resent problems which not graph separation problems themselves, but have some variant of graph separation at their core, after which by using new frameworks as well as existing ones, the author gives new as well as improved FPT algorithms.