Skip to content

Matching Hot Sheet

Use this page when the statement is really about pairing two sides of a compatibility graph and you want the smallest reliable route back to bipartite matching.

Do Not Use When

  • the graph is not actually bipartite
  • capacities or costs make a flow model cleaner than a plain matching model
  • the problem is really edge cover, blossom, or weighted assignment and you still need to identify that boundary first

Choose By Signal

  • maximum number of compatible pairs in a bipartite graph -> hopcroft-karp.cpp
  • small bipartite modeling but retrieval is fuzzy -> reopen the Matching page for Kuhn/Hopcroft-Karp chooser first
  • equal-size two-sided preferences with a stability objective -> Stable Marriage hot sheet
  • one-to-one weighted assignment on a dense square matrix -> Hungarian hot sheet
  • capacities, source groups, or transport story dominate -> check Flow hot sheet
  • undirected graph is not guaranteed bipartite -> General Matching hot sheet
  • general graph / edge-cover transformation boundary -> treat QBFLOWER as a compare point, not as the in-lane baseline

Core Invariants

  • one augmenting path increases the matching size by exactly 1
  • if no augmenting path remains, the current matching is maximum
  • the repo starter assumes the left and right parts are fixed in advance

Main Traps

  • feeding a non-bipartite graph to Hopcroft-Karp
  • mixing statement indexing with the starter's 0-based interface
  • forgetting that some tasks ask for vertex cover / edge cover / weighted assignment after the matching, not just the matching size

Exact Starters In This Repo

Reopen Paths