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

摘要

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. (C) 2018 Elsevier B.V. All rights reserved.