A (3 + ϵ)k-vertex kernel for edge-disjoint triangle packing

Abstract 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 4 k was proved many years ago. Recently, the size of the vertex kernel was improved to 3.5 k . In this paper, we further improve the kernel size. We show that for any fixed ϵ > 0 , there is a polynomial-time algorithm that can reduce the input instance to an equivalent instance of at most ( 3 + ϵ ) k vertices.