Parameterized Complexity of Graph Partitioning and Geometric Covering[HBNI Th115]

Abstract

In this thesis, we consider problems in graph partitioning and geometric covering in the realm of Parameterized complexity. Several algorithmic paradigms have been developed in order to cope with the hard problems of classical complexity. However, any algorithmic paradigm meant to cope with the hard problems and to run in polynomial time, such as approximation algorithms or randomized algorithms, must give in to inaccuracy. Parameterized complexity is a fairly new branch of theoretical computer science, with yet another measure of efficiency in terms of running time but where there in no compromise on accuracy. A parameterized problem associates with each input instance, of a classical problem, a parameter, which is usually a positive integer. The aim is to contain the exponential explosion in the running time of algorithms such that the dependence of the exponential function in the running time is only on the parameter associated with the input instance. When carefully chosen, the parameter tends to be much smaller than the input instance. Therefore, we expect parameterized problems to have more efficient algorithms, in terms of running time, than their counterparts in the classical complexity setting.