A (3+is an element of)k-vertex kernel for edge-disjoint triangle packing

作者：Lin, Weibo; Xiao, Mingyu^*

来源：Information Processing Letters, 2019, 142: 20-26.

DOI：10.1016/j.ipl.2018.10.006

• Kernelization
• Triangle packing
• Fixed-parameter tractable
• Graph algorithms

In the EDGE-DISJOINT TRIANGLE PACKING problem (ETP), we are given a graph G and an integer k, and asked to check whether G contains at least k edge-disjoint triangles. This problem is NP-hard and has been well studied in the parameterized complexity. A vertex kernel of size 4k was proved many years ago. Recently, the size of the vertex kernel was improved to 3.5k. In this paper, we further improve the kernel size. We show that for any fixed E > 0, there is a polynomial-time algorithm that can reduce the input instance to an equivalent instance of at most (3 + is an element of)k vertices.

• 出版日期2019-2
• 单位电子科技大学