Kernelization for Graph Packing Problems via Rainbow Matching
Stéphane Bessy, Marin Bougeret, Dimitrios M. Thilikos, Sebastian Wiederrecht · Society for Industrial and Applied Mathematics eBooks · 2023
We introduce a new kernelization tool, called rainbow matching technique, that is appropriate for the design of polynomial kernels for packing problems. Our technique capitalizes on the powerful combinatorial results of [Graf, Harris, Haxell, SODA 2021]. We apply the rainbow matching technique on two (di)graph packing problems, namely the TRIANGLE-PACKING IN TOURNAMENT problem (TPT), where we ask for a packing of k directed triangles in a tournament, and the INDUCED 2-PATH-PACKING (I2PP) where we ask for a packing of k induced paths of length two in a graph. The existence of a sub-quadratic kernels for these problems was proven for the first time in [Fomin, Le, Lokshtanov, Saurabh, Thomassé, Zehavi. ACM Trans. Algorithms, 2019], where they gave a kernel of