# Conﬂict Packing Yield Linear Vertex-Kernels for k- Fast, $k-Dense$ RTI and a Related Problem

1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We develop a technique that we call Conﬂict Packing in the context of kernelization. We illustrate this technique on several well-studied problems: Feedback Arc Set in Tournaments, Dense Rooted Triplet Inconsistency and Betweenness in Tournaments. For the former, one is given a tournament T = (V , A) and seeks a set of at most k arcs whose reversal in T results in an acyclic tournament. While a linear vertex-kernel is already known for this problem [6], using the Conﬂict Packing allows us to ﬁnd a so-called safe partition, the central tool of the kernelization algorithm in [6], with simpler arguments. Regarding the Dense Rooted Triplet Inconsistency 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 Conﬂict Packing, we prove that the Dense Rooted Triplet Inconsistency problem admits a linear vertex-kernel. This result improves the best known bound of O(k^2) vertices for this problem [18]. Finally, we use this technique to obtain a linear vertex-kernel for Betweenness in Tournaments, where one is given a set of vertices V and a dense collection R of betweenness triplets and seeks an ordering containing all but at most k triplets from R. To the best of our knowledge this result constitutes the ﬁrst polynomial kernel for the problem.
Document type :
Conference papers
Domain :

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00642335
Contributor : Christophe Paul Connect in order to contact the contributor
Submitted on : Thursday, November 17, 2011 - 8:46:55 PM
Last modification on : Monday, October 11, 2021 - 1:24:07 PM

### Citation

Christophe Paul, Anthony Perez, Stéphan Thomassé. Conﬂict Packing Yield Linear Vertex-Kernels for k- Fast, $k-Dense$ RTI and a Related Problem. 36th International Symposium on Mathematical Foundations of Computer Science (MFCS 2011), Aug 2011, Warsaw, Poland. pp.497-507, ⟨10.1007/978-3-642-22993-0_45⟩. ⟨lirmm-00642335⟩

Record views