Packing Short Cycles

Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of vertices that either minimize the total length of the paths Björklund, Husfeldt, ICALP 2014; Mari, Mukherjee, Pilipczuk, and Sankowski, SODA 2024 or request the paths to be shortest Lochet, SODA 2021, we consider the following cycle packing problems: Min-Sum Cycle Packing and Shortest Cycle Packing . In Min-Sum Cycle Packing , we try to find, in a weighted undirected graph, \(k\) vertex-disjoint cycles of minimum total weight. Our first main result is an algorithm that, for any fixed \(k\) , solves the problem in polynomial time. We complement this result by establishing the W1-hardness of Min-Sum Cycle Packing parameterized by \(k\) . The same results hold for the version of the problem where the task is to find \(k\) edge disjoint cycles. Our second main result concerns Shortest Cycle Packing , which is a special case of Min-Sum Cycle Packing that asks to find a packing of \(k\) shortest cycles in a graph. We prove this problem to be fixed-parameter tractable (FPT) when parameterized by \(k\) on weighted planar graphs. We also obtain a polynomial kernel for the edge-disjoint variant of the problem on planar graphs. Whether Min-Sum Cycle Packing is FPT on planar graphs, or Shortest Cycle Packing on general graphs, remains open.