Improved kernels for triangle packing in tournaments  

作　　者：Hanchun YUAN Qilong FENG Jianxin WANG 

机构地区：[1]School of Computer Science and Engineering,Central South University,Changsha 410083,China [2]Hunan Provincial Key Lab on Bioinformatics,Central South University,Changsha 410083,China

出　　处：《Science China(Information Sciences)》2023年第5期96-109,共14页中国科学（信息科学）（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant Nos.62172446,61872450)。

摘　　要：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.

关 键 词：TOURNAMENTS triangle packing KERNELIZATION fixed-parameter tractable graph algorithms 

分 类 号：O157.5[理学—数学]