Skip to content

Edmonds Blossom / General Matching Ladder

This lane is for the first time matching remains the right model, but bipartiteness is gone and odd cycles actually matter.

Who This Is For

Use this lane if:

  • Matching already feels comfortable
  • you trust augmenting-path logic in bipartite graphs
  • you now need maximum cardinality matching in a general undirected graph

This lane is intentionally narrow:

  • one exact starter
  • one flagship note that is the plain template problem
  • one transformation compare point through QBFLOWER
  • one firm boundary against weighted assignment and weighted blossom

Warm-Up

  • explain why an odd cycle breaks the naive bipartite alternating-tree picture
  • explain why blossom is still augmenting-path matching, not a different objective
  • compare one bipartite matching statement against one general matching statement

Target skill:

  • recognize when "the graph is not bipartite" is the decisive signal, not just a side comment

Core

  • general undirected graph
  • maximum number of disjoint edges
  • odd-cycle contraction via blossom shrinking
  • exact flagship rep: General Matching

Target skill:

  • trust the O(n^3) blossom route and recover one valid maximum matching

Stretch

  • transformation route -> QBFLOWER
  • compare one direct general-matching problem against one Task Assignment instance
  • compare one direct general-matching problem against one MINCOST instance

Target skill:

  • separate unweighted general matching from weighted bipartite assignment and from costed flow models

Retrieval Layer

Repo Anchors And Compare Points

The cleanest in-repo loop here is:

  1. reopen Matching just enough to remember alternating paths
  2. learn the blossom route in Edmonds Blossom / General Matching
  3. solve General Matching
  4. revisit QBFLOWER only after the direct template route feels stable

Exit Criteria

You are ready to move on when:

  • you stop trying to 2-color every matching problem by reflex
  • you know that odd cycles are the reason blossom exists
  • you can recover and print one maximum matching, not just its size

External Practice