Abstract
In this thesis, we study the parameterized complexity of several N P -complete problems. More precisely, we study the existence of polynomial kernels for graph and relations modification prob- lems. In particular, we introduce the concept of branches, which provides polynomial kernels for some graph modification problems when the target graph class admits a so-called adjacency de- composition. This technique allows us to obtain the first known polynomial kernels for the CLOSEST 3-LEAF POWER, COGRAPH EDITION and PROPER INTERVAL COMPLETION problems. Regarding relations modification problems, we develop and push further the concept of Conflict Packing, a technique that has already been used in a few parameterized problems and that provides polynomial kernels for several problems. We thus present a linear vertex-kernel for the FEEDBACK ARC SET IN TOURNAMENTS problem, and adapt these techniques to obtain a linear vertex-kernel for the DENSE ROOTED TRIPLET INCONSISTENCY problem as well. In both cases, our results im- prove the best known bound of O(k^2) vertices. Finally, we apply the Conflict Packing technique on the DENSE BETWEENNESS and DENSE CIRCULAR ORDERING problems, obtaining once again linear vertex-kernels. To the best of our knowledge, these results constitute the first known polynomial kernels for these problems.