Parameterized Complexity of Restricted Variants of Some Classical Problems

Abstract

As the title of this thesis suggests, we study how does the complexity of problems change if we add some restrictions to them. In order to achieve this, we use the framework of parameterized complexity. In contrast to classical complexity, where we express the number of steps in terms of input size, in parameterized complexity we express the number of steps in terms of the input size and an extra parameter. In the first part of the thesis, we study how adding structure to the input makes problems easier. We consider the Subgraph Isomorphism problem on unit disk graphs, and the Set Cover problem where the sets form arithmetic progressions. In the second part of the thesis, we add restrictions on the solution. We start from the Flow problem, and we consider two natural restrictions, namely connectivity and the all-or-nothing restriction.