### Page Content

### to Navigation

## Linear kernel via conflict packing - application to FAST and dense RTI problems

**Prof. Christophe Paul ****(Laboratoire d'Informatique Robotique et Microélectronique de Montpellier)**

We introduce a new technique to design kernelization algorithms for parameterized problems, namely Conflict Packing. We illustrate this technique on two well-studied problems: FAST and RTI.

For the former, one is given a tournament T = (V,A) and seeks a set of at most k arcs whose reversal in T leads to an acyclic tournament. While a linear vertex-kernel is already known for this problem, it requires a constant-factor approximation algorithm as a subroutine. Using the Conflict Packing, we show how to avoid this subroutine to find a so-called safe partition.

In the RTI problem, one is given a set of vertices V and a dense collection R of rooted binary trees over three vertices of V and seeks a rooted tree over V containing all but at most k triplets from R. Using again the Conflict Packing, we prove that the dense RTI problem admits a linear vertex-kernel. This result improves the on the quadratic known kernel.

This is joint work with A. Perez and S. Thomassé.

Date | Speaker | Location | Language |
---|---|---|---|

03.12.2012 17:45 | Christophe Paul | TEL 512 | english |