Résumé
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 W[1]-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.