Linear kernel for Rooted Triplet Inconsistency and other problems based on conflict packing technique.

We develop a technique, that we call conflict packing , to obtain (and improve) polynomial kernels for several well-studied editing problems. We first illustrate our technique on Feedback Arc Set in Tournaments ( k -FAST ) yielding an alternative and simple proof of a linear kernel for this problem. The technique is then applied to obtain the first linear kernel for the Dense Rooted Triplet Inconsistency ( k -dense-RTI ) problem. A linear kernel for Betweenness in Tournaments ( k -BIT ) is also proved. All these problems share common features. First, they can be expressed as modification problems on a dense set of constant-arity constraints. Also the consistency of the set of constraints can be characterized by means of a bounded size obstructions. The conflict packing technique basically consists of computing a maximal set of small obstructions allowing us either to bound the size of the input or to reduce the input. [ABSTRACT FROM AUTHOR]