Inhalt des Dokuments
Es gibt keine deutsche Übersetzung dieser Webseite.
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é.
Back to the research colloquium site.