Lune

SODA2025Top-tier venue

Packing Short Cycles

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, William Lochet, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Kirill Simonov

Abstract

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. Deciding whether Min-Sum Cycle Packing is FPT on planar graphs and whether Shortest Cycle Packing is FPT on general graphs remain challenging open questions.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Shortest Disjoint Paths on a Grid cites A Polynomial Time Algorithm for the k-Disjoint Shortest Paths Problem
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on3

  1. A Polynomial Time Algorithm for the k-Disjoint Shortest Paths ProblemWilliam LochetSODA 2021 · 12 citations
  2. Shortest Disjoint Paths on a GridMathieu Mari, Anish Mukherjee, Michal Pilipczuk, Piotr SankowskiSODA 2024 · 4 citations
  3. Packing cycles in planar and bounded-genus graphsNiklas Schlomberg, Hanjo Thiele, Jens VygenSODA 2023 · 1 citation

Related papers

  1. A coarse Erdős-Pósa theoremJungho Ahn, Jochen Pascal Gollin, Tony Huynh, O-joung KwonSODA 2025 · 3 citations
  2. Planar Disjoint Shortest Paths is Fixed-Parameter TractableMichal Pilipczuk, Giannos Stamoulis, Michal WlodarczykSODA 2026
  3. Finding Triangles and Other Small Subgraphs in Geometric Intersection GraphsTimothy M. ChanSODA 2023 · 4 citations
  4. Passing the Limits of Pure Local Search for Weighted k-Set PackingMeike NeuwohnerSODA 2023 · 10 citations
  5. Fixed-Parameter Tractability of Maximum Colored Path and BeyondFedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, Kirill Simonov et al.SODA 2023 · 1 citation
Dusk over the sea between two cliffs drawn in fine vertical lines