Improved kernels for triangle packing in tournaments

Abstract

Triangle packing problem has been paid lots of attention to in the literature. In this paper, we study the kernelization of the triangle packing problem in tournaments. For the parameterized arc-disjoint triangle packing problem in tournaments, we find a maximal arc-disjoint triangle packing with the number of vertices bounded by 2.5k. Based on the relation between the maximal arc-disjoint triangle packing and the vertices outside of the packing, a kernel of size 3.5k for the problem is obtained, improving the previous best one 6k. For the parameterized vertex-disjoint triangle packing problem in sparse tournaments, several new properties between the triangles in maximal vertex-disjoint triangle packing and the arcs in the feedback arc set are presented, which result in a kernel of size 7k for the problem, improving the previous best one of 15k. We also give a 7k vertex kernel for the parameterized feedback vertex set problem in sparse tournaments. The kernelization process presented in this paper for the parameterized arc-disjoint triangle packing can be applied to solve the parameterized arc-disjoint triangle packing problem on other restricted directed graph classes.