TY - GEN
T1 - Kernelization for Graph Packing Problems via Rainbow Matching
AU - Bessy, Stéphane
AU - Bougeret, Marin
AU - Thilikos, Dimitrios M.
AU - Wiederrecht, Sebastian
N1 - Publisher Copyright:
Copyright © 2023 by SIAM.
PY - 2023
Y1 - 2023
N2 - 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 O(k3/2) vertices and O(k5/3) vertices respectively. In the same paper it was questioned whether these bounds can be (optimally) improved to linear ones. Motivated by this question, we apply the rainbow matching technique and prove that TPT admits an (almost linear) kernel of (Equation presented) vertices and that I2PP admits a kernel of O(k) vertices.
AB - 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 O(k3/2) vertices and O(k5/3) vertices respectively. In the same paper it was questioned whether these bounds can be (optimally) improved to linear ones. Motivated by this question, we apply the rainbow matching technique and prove that TPT admits an (almost linear) kernel of (Equation presented) vertices and that I2PP admits a kernel of O(k) vertices.
KW - Kernelization
KW - Packing problems
KW - Parameterized algorithms
KW - Rainbow matching
UR - http://www.scopus.com/inward/record.url?scp=85150333285&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85150333285&partnerID=8YFLogxK
U2 - 10.1137/1.9781611977554.ch139
DO - 10.1137/1.9781611977554.ch139
M3 - Conference contribution
AN - SCOPUS:85150333285
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 3654
EP - 3663
BT - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
PB - Association for Computing Machinery
T2 - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
Y2 - 22 January 2023 through 25 January 2023
ER -