Techniques in parameterized algorithm design

Abstract

In this thesis we give a novel classification of techniques for designing parameterized algorithms, together with research publications applying these techniques, in particular Crown Decompositions, to various problems. In Part I we argue that the currently known techniques can be organized into just four general themes: Bounded Search Trees, Reduction Rules, Induction and Win/Win. The four main themes and their variations are presented through an algorithmic skeleton and illustrated by examples. Part II contains four research papers that apply the techniques described in Part I on the following problems: MAX INTERNAL SPANNING TREE, K3-PACKING, H-PACKING, K1;s-PACKING, P2-PACKING, SET SPLITTING, and MAX CUT. The techniques used include Win/Win, Bounded Search Trees, Greedy Localization, Crown Decomposition, Modelled Crown Decomposition, Extremal Method, and Reduction Rules.