Résumé
This thesis tackles NP-hard problems with combinatorial techniques, focusing on the framework of Fixed-Parameter Tractability. Themain problems considered here are MULTICUT and MAXIMUM LEAF OUT-BRANCHING. MULTICUT is a natural generalisation of the cut problem, and consists in simultaneously separating prescribed pairs of vertices by removing as few edges as possible in a graph. MAXIMUM LEAF OUT-BRANCHING consists in finding a spanning directed tree with as many leaves as possible in a directed graph. The main results of this thesis are the following. We show that MULTICUT is FPT when parameterized by the solution size, i.e. deciding the existence of a multicut of size k in a graph with n vertices can be done in time f(k) ∗ poly(n). We show that MULTICUT IN TREES admits a polynomial kernel, i.e. can be reduced to instances of size polynomial in k. We give anO∗(3.72k) algorithmforMAXIMUM LEAF OUT-BRANCHING and the first non-trivial (better than 2n) exact algorithm. We also provide a quadratic kernel and a constant factor approximation algorithm. These algorithmic results are based on combinatorial results and structural properties, involving tree decompositions,minors, reduction rules and s−t numberings, among others. We present results obtained with combinatorial techniques outside the scope of parameterized complexity: a characterization of Helly circle graphs as the diamond-free circle graphs, and a partial characterisation of 2-well-quasi-ordered classes of graphs.