Alladi Ramakrishnan Hall

Parameterized Complexity for Graph Partitioning and Geometric Covering (Thesis Defense)

Sudeshna Kolay

IMSc

In this thesis, problems in graph partitioning and geometric covering in the realm of Parameterized complexity are considered. In particular in this thesis the candidate obtains several new results on deleting vertices such that graph can be partitioned into several parts where each part being either a clique or independent sets. Towards that ideas from communication complexity has been used to design faster parameterized algorithms. In the second part of the thesis the authors considers several variants of {\sc Set Cover} problem when geometric restrictions are introduced to the set families. Finally, the candidate designs
the first deterministic subexponential time algorithm for {\sc Rectilinear Steiner Tree}.