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