direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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é.

03.12.2012 17:45
Christophe Paul
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras