pith. sign in

arxiv: 2604.20351 · v1 · submitted 2026-04-22 · 💻 cs.DS

Blossom VI: A Practical Minimum Weight Perfect Matching Algorithm

Pavel Arkhipov , Vladimir Kolmogorov This is my paper

Pith reviewed 2026-05-09 23:45 UTC · model grok-4.3

classification 💻 cs.DS
keywords minimum weight perfect matchingblossom algorithmcherry blossomsgraph matchingprimal-dual methodspractical algorithmsmaximum cardinality matching
0
0 comments X

The pith

A new Blossom VI algorithm for minimum weight perfect matching achieves almost-linear runtime on tested instance families by shrinking cherry blossoms into shallower supernodes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces an implementation for minimum weight perfect matching that focuses on solving maximum-cardinality unweighted matching subproblems in its primal phase. It substitutes cherry trees for alternating trees and cherry blossoms for traditional blossoms, then shrinks the cherry blossoms into supernodes. This produces much shallower structures than prior approaches. The result is an algorithm that runs almost linearly across every tested family and outperforms Blossom V precisely where that earlier method slows to superlinear time. Faster practical matching solvers matter because the problem appears in scheduling, computer vision, and network optimization, where instance size often limits what can be solved.

Core claim

Blossom VI solves the minimum weight perfect matching problem by repeatedly solving maximum-cardinality unweighted matching subproblems during the primal phase. It employs cherry trees and cherry blossoms in place of alternating trees and blossoms, shrinking the cherry blossoms into supernodes. This strategy keeps supernode hierarchies much shallower than in previous implementations, yielding almost-linear runtime on every family of instances tested and significantly better performance than Blossom V on those families where the prior method exhibits superlinear behavior.

What carries the argument

Cherry blossoms shrunk into supernodes, which replace traditional blossoms to produce shallower hierarchies while the algorithm solves a sequence of unweighted matching subproblems.

If this is right

  • Minimum weight perfect matching instances that previously triggered superlinear slowdowns can now be solved more quickly.
  • Larger graphs become feasible to process because the runtime stays close to linear on the tested families.
  • The primal phase can rely on calls to an unweighted maximum-cardinality matcher without incurring extra asymptotic cost.
  • Shallower supernodes reduce the depth of the search structures used during augmentation and dual updates.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The cherry-blossom shrinking technique could be adapted to other matching variants that currently use traditional blossoms.
  • If the almost-linear behavior persists on new families, it may encourage replacing older blossom codes in production solvers.
  • Hybrid implementations that combine this primal approach with existing dual heuristics become easier to test.

Load-bearing premise

The families of graphs tested so far are representative of the instances that arise in practical use.

What would settle it

A graph family on which the implementation either exhibits superlinear runtime or is slower than Blossom V across the board would show the practical claims do not hold.

Figures

Figures reproduced from arXiv: 2604.20351 by Pavel Arkhipov, Vladimir Kolmogorov.

Figure 1
Figure 1. Figure 1: Primal update operations. White circles denote roots of cherry trees and contracted [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of runtimes of Blossom VI vs Blossom V. Red crosses denote 500 seconds [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
read the original abstract

We implement an algorithm for solving the minimum weight perfect matching problem. Our code significantly outperforms the current state-of-the-art Blossom V algorithm on those families of instances where Blossom V takes superlinear time. In practice, our implementation shows almost-linear runtime on every family of instances on which we have tested it. Our algorithm relies on solving the maximum-cardinality unweighted matching problems during its primal phase. Following the state-of-the-art cherry blossom algorithm, we use cherry trees instead of traditional alternating trees and cherry blossoms instead of traditional blossoms. We shrink cherry blossoms rather than traditional blossoms into supernodes. This strategy allows us to deal with much shallower supernodes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript presents Blossom VI, a practical algorithm and implementation for the minimum weight perfect matching problem. It refines the Blossom framework by using cherry trees in place of alternating trees and cherry blossoms in place of traditional blossoms, shrinking the latter into shallower supernodes. This enables solving a sequence of maximum-cardinality unweighted matching problems in the primal phase. The central empirical claim is that the implementation significantly outperforms Blossom V on families where the latter exhibits superlinear runtime and achieves almost-linear runtime on every tested family of instances.

Significance. If the empirical performance claims hold under broader testing, the work offers a meaningful practical improvement for solving minimum-weight perfect matching instances that arise in optimization and combinatorial applications. The engineering refinement of cherry structures is a direct, scoped extension of prior Blossom variants and does not rely on new theoretical runtime bounds or untested assumptions beyond the reported instance families.

minor comments (2)
  1. Abstract: the performance claims (outperformance on superlinear families and almost-linear runtime on all tested families) are stated without any reference to specific instance families, benchmark tables, or statistical measures; adding a short clause pointing to the experimental section would improve immediate readability.
  2. The manuscript would benefit from an explicit statement in the introduction or experimental section confirming that all reported runtimes were measured on the same hardware and with identical termination criteria as the Blossom V baseline.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading and positive assessment of the manuscript. The recommendation for minor revision is appreciated, and we are glad that the practical improvements and engineering refinements are viewed as a meaningful contribution. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; empirical runtime claims are scoped to tested instances

full rationale

The paper describes a forward engineering refinement of the Blossom framework (cherry trees, shallower supernodes, reduction to unweighted cardinality matching in the primal phase) and reports measured runtimes on specific families. These observations are presented as experimental results rather than derived predictions or theorems. No equation or claim reduces by construction to a fitted parameter, self-definition, or self-citation chain; prior-work references are external and non-load-bearing for the scoped empirical statement. The central claim remains falsifiable on new instances and does not import uniqueness or ansatz via self-citation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard graph-theoretic assumptions and prior matching algorithms without introducing new free parameters, axioms beyond domain basics, or invented entities.

axioms (1)
  • domain assumption Input graphs admit perfect matchings or the algorithm correctly handles cases without them.
    The minimum weight perfect matching problem is only well-defined when a perfect matching exists; the paper assumes standard handling of this prerequisite.

pith-pipeline@v0.9.0 · 5396 in / 1126 out tokens · 50300 ms · 2026-05-09T23:45:44.784090+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    Solving large-scale matching problems

    David L Applegate and William J Cook. Solving large-scale matching problems. InNetwork flows and matching, pages 557–576, 1991

    work page 1991

  2. [2]

    M. L. Balinski. Labelling to obtain a maximum matching. In R. C. Bose and T. A. Dowling, editors,Combinatorial Mathematics and Its Applications, pages 585–602. University of North Carolina Press, Chapel Hill, NC, 1969

    work page 1969

  3. [3]

    Maximum matching in general graphs without explicit consideration of blos- soms revisited.CoRR, abs/1509.04927, 2015

    Norbert Blum. Maximum matching in general graphs without explicit consideration of blos- soms revisited.CoRR, abs/1509.04927, 2015

    work page arXiv 2015

  4. [4]

    Computing minimum-weight perfect matchings.INFORMS journal on computing, 11(2):138–148, 1999

    William Cook and Andre Rohe. Computing minimum-weight perfect matchings.INFORMS journal on computing, 11(2):138–148, 1999

    work page 1999

  5. [5]

    A primal algorithm for optimum matching

    William H Cunningham and Alfred B Marsh. A primal algorithm for optimum matching. In Polyhedral Combinatorics: Dedicated to the memory of DR Fulkerson, pages 50–72. Springer, 2009

    work page 2009

  6. [6]

    On the use of optimal fractional matchings for solving the (integer) matching problem.Computing, 36(3):263–270, 1986

    Ulrich Derigs and Achim Metz. On the use of optimal fractional matchings for solving the (integer) matching problem.Computing, 36(3):263–270, 1986

    work page 1986

  7. [7]

    LEMON — an open source C++ graph template library.Electronic notes in theoretical computer science, 264(5):23–45, 2011

    Bal´ azs Dezs˝ o, Alp´ ar J¨ uttner, and P´ eter Kov´ acs. LEMON — an open source C++ graph template library.Electronic notes in theoretical computer science, 264(5):23–45, 2011

    work page 2011

  8. [8]

    Dillencourt

    Michael B. Dillencourt. Toughness and Delaunay triangulations.Discrete Comput. Geom., 5(6):575–601, December 1990

    work page 1990

  9. [9]

    Shrinking trees not blossoms: A recursive maximum matching approach

    Andre Droschinsky, Petra Mutzel, and Erik Thordsen. Shrinking trees not blossoms: A recursive maximum matching approach. In2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX), pages 146–160. SIAM, 2020

    work page 2020

  10. [10]

    Maximum matching and a polyhedron with 0, 1-vertices.Journal of research of the National Bureau of Standards B, 69(125-130):55–56, 1965

    Jack Edmonds. Maximum matching and a polyhedron with 0, 1-vertices.Journal of research of the National Bureau of Standards B, 69(125-130):55–56, 1965

    work page 1965

  11. [11]

    Paths, trees, and flowers.Canadian Journal of mathematics, 17:449–467, 1965

    Jack Edmonds. Paths, trees, and flowers.Canadian Journal of mathematics, 17:449–467, 1965. 17

    work page 1965

  12. [12]

    Blossom I: a computer code for the matching problem.IBM TJ Watson Research Center, Yorktown Heights, New York, 294, 1969

    Jack Edmonds, Ellis L Johnson, and Scott C Lockhart. Blossom I: a computer code for the matching problem.IBM TJ Watson Research Center, Yorktown Heights, New York, 294, 1969

    work page 1969

  13. [13]

    X-blossom: Massive parallelization of graph maximum matching.Proceedings of the VLDB Endowment, 18(10):3339–3353, 2025

    Dayi Fan, Rubao Lee, and Xiaodong Zhang. X-blossom: Massive parallelization of graph maximum matching.Proceedings of the VLDB Endowment, 18(10):3339–3353, 2025

    work page 2025

  14. [14]

    An efficient implementation of Edmonds’ algorithm for maximum matching on graphs.Journal of the ACM (JACM), 23(2):221–234, 1976

    Harold N Gabow. An efficient implementation of Edmonds’ algorithm for maximum matching on graphs.Journal of the ACM (JACM), 23(2):221–234, 1976

    work page 1976

  15. [15]

    A scaling algorithm for weighted matching on general graphs

    Harold N Gabow. A scaling algorithm for weighted matching on general graphs. In26th Annual Symposium on Foundations of Computer Science (sfcs 1985), pages 90–100. IEEE, 1985

    work page 1985

  16. [16]

    Efficient implementation of graph algorithms using contraction

    Harold N Gabow, Zvi Galil, and Thomas H Spencer. Efficient implementation of graph algorithms using contraction. In25th Annual Symposium onFoundations of Computer Science, 1984., pages 347–357. IEEE, 1984

    work page 1984

  17. [17]

    Faster scaling algorithms for general graph matching problems.Journal of the ACM (JACM), 38(4):815–853, 1991

    Harold N Gabow and Robert E Tarjan. Faster scaling algorithms for general graph matching problems.Journal of the ACM (JACM), 38(4):815–853, 1991

    work page 1991

  18. [18]

    Harold Neil Gabow.Implementation of algorithms for maximum matching on nonbipartite graphs.Stanford University, 1974

    work page 1974

  19. [19]

    AnO(EVlogV) algorithm for finding a maximal weighted matching in general graphs.SIAM Journal on Computing, 15(1):120–130, 1986

    Zvi Galil, Silvio Micali, and Harold Gabow. AnO(EVlogV) algorithm for finding a maximal weighted matching in general graphs.SIAM Journal on Computing, 15(1):120–130, 1986

    work page 1986

  20. [20]

    Finding a maximum cut of a planar graph in polynomial time.SIAM Journal on Computing, 4(3):221–225, 1975

    Frank Hadlock. Finding a maximum cut of a planar graph in polynomial time.SIAM Journal on Computing, 4(3):221–225, 1975

    work page 1975

  21. [21]

    New algorithms for maximum weight matching and a decomposition theorem.Mathematics of Operations Research, 42(2):411–426, 2017

    Chien-Chung Huang and Telikepalli Kavitha. New algorithms for maximum weight matching and a decomposition theorem.Mathematics of Operations Research, 42(2):411–426, 2017

    work page 2017

  22. [22]

    Blossom V: a new implementation of a minimum cost perfect matching algorithm.Mathematical Programming Computation, 1(1):43–67, 2009

    Vladimir Kolmogorov. Blossom V: a new implementation of a minimum cost perfect matching algorithm.Mathematical Programming Computation, 1(1):43–67, 2009

    work page 2009

  23. [23]

    Implementation ofO(nmlogn) weighted matchings in general graphs: the power of data structures.Journal of Experimental Algorithmics (JEA), 7:4, 2002

    Kurt Mehlhorn and Guido Sch¨ afer. Implementation ofO(nmlogn) weighted matchings in general graphs: the power of data structures.Journal of Experimental Algorithmics (JEA), 7:4, 2002

    work page 2002

  24. [24]

    AnO( p |V||E|) algoithm for finding maximum matching in general graphs

    Silvio Micali and Vijay V Vazirani. AnO( p |V||E|) algoithm for finding maximum matching in general graphs. In21st Annual symposium on foundations of computer science (Sfcs 1980), pages 17–27. IEEE, 1980

    work page 1980

  25. [25]

    Maximum matchings via Gaussian elimination

    Marcin Mucha and Piotr Sankowski. Maximum matchings via Gaussian elimination. In45th Annual IEEE Symposium on Foundations of Computer Science, pages 248–255. IEEE, 2004

    work page 2004

  26. [26]

    Andre Rohe.https://www.math.uwaterloo.ca/tsp/vlsi/index.html

    work page

  27. [27]

    Springer, 2003

    Alexander Schrijver et al.Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003

    work page 2003

  28. [28]

    Pearson Education, 2001

    Jeremy G Siek, Lie-Quan Lee, and Andrew Lumsdaine.The Boost Graph Library: User Guide and Reference Manual, The. Pearson Education, 2001. 18

    work page 2001

  29. [29]

    A theory of alternating paths and blossoms for proving correctness of the general graph maximum matching algorithm.Combinatorica, 14(1):71–109, 1994

    Vijay V Vazirani. A theory of alternating paths and blossoms for proving correctness of the general graph maximum matching algorithm.Combinatorica, 14(1):71–109, 1994

    work page 1994

  30. [30]

    A proof of the MV matching algorithm.arXiv preprint arXiv:2012.03582, 2020

    Vijay V Vazirani. A proof of the MV matching algorithm.arXiv preprint arXiv:2012.03582, 2020

    work page arXiv 2012

  31. [31]

    Witzgall and C

    C. Witzgall and C. T. Zahn, Jr. Modification of Edmonds’ maximum matching algorithm. Journal of Research of the National Bureau of Standards–B. Mathematics and Mathematical Physics, 69B(1–2):91–98, 1965. 19

    work page 1965