Towards optimal kernel for edge-disjoint triangle packing

• We derive new reduction rules for the edge-disjoint triangle packing problem.
• We derive an improved 3.5k vertex kernel for the edge-disjoint triangle packing problem.
• Our kernel improves the FPT-algorithm to solve the problem.

We study the kernelization of the Edge-Disjoint Triangle Packing (Etp) problem, in which we are asked to find k edge-disjoint triangles in an undirected graph. Etp is known to be fixed-parameter tractable with a 4k vertex kernel. The kernelization first finds a maximal triangle packing which contains at most 3k vertices, then the reduction rules are used to bound the size of the remaining graph. The constant in the kernel size is so small that a natural question arises: Could 4k be already the optimal vertex kernel size for this problem? In this paper, we answer the question negatively by deriving an improved 3.5k vertex kernel for the problem.