betaFeedback

WorksMathematics

Almost-Linear-Time Maximum-Cardinality Matching in General Graphs

Abstract

We prove that maximum-cardinality matching in a simple undirected graph with n vertices and m edges can be found by one uniform randomized algorithm in (n+m)1+o(1)(n+m)^{1+o(1)} time. The bound holds on every computation path in a logarithmic-word model, and the algorithm returns an explicit maximum matching with probability at least 2/3. An explicit reduction gives the same time and probability guarantees for deciding whether a simple host graph has a spanning subgraph with prescribed valid vertex degrees, and for finding one when it exists.

Introduction

A matching in a graph is a set of edges with pairwise disjoint endpoints. The maximum-cardinality matching problem asks for such a set with the largest possible number of edges. We prove an almost-linear bound in the adjacency-list input size for general graphs, with explicit output and a single uniform algorithm. The running-time guarantee includes every unsuccessful random computation, all finite-precision work, and all input and output costs.

Statement and computational model

The input is a simple undirected unweighted graph G=([n],E)G = ([n], E), where n≥1n \ge1 and m=∣E∣m = |E|. It is given by an array of adjacency-list boundaries and two neighbor occurrences per edge. Labels and indices use O(log⁡(n+2))O(\log(n + 2)) bits. The lists may have any valid order. Isolated vertices count toward nn, and the graph need not be connected. Write p=n+mp = n + m, which is within a constant factor of the number of input word records, and write ν(G)\nu(G) for the maximum matching size.

We use a classical randomized word-RAM whose word length is

w=⌈c0log⁡2(n+2)⌉,w = \lceil c_0 \log_2(n + 2) \rceil,

for a fixed constant c0≥2c_0 \ge2 chosen with the algorithm. Unit-cost instructions are word reads and writes, comparison, addition, subtraction, multiplication modulo 2w2^w, integer quotient and remainder with nonzero divisor, Boolean operations, and shifts by fewer than ww positions. Each independent fair random bit costs one instruction. Longer arithmetic uses charged multiword implementations. Allocation, initialization, data movement, preprocessing, and output writing are included. There is no oracle or nonuniform advice. Since n≤p≤n2n \le p \le n^2 for a simple graph, the word length is also Θ(log⁡(p+2))\Theta(\log(p + 2)).

Theorem 1.1 (Exact matching in almost-linear input-size time). There are a single uniform randomized word-RAM algorithm, fixed constants c0≥2c_0 \ge2 and C≥1C \ge1, and a nonincreasing function η:N≥1→R≥0\eta: \mathbb{N}_{\ge1} \to\mathbb{R}_{\ge0} with η(q)→0\eta(q) \to0 as q→∞q \to\infty such that the following holds. For every input graph G=([n],E)G = ([n], E) with m=∣E∣m = |E| and p=n+mp = n + m, the algorithm halts on every computation path in at most

Cp1+η(p)Cp^{1+\eta(p)}

instructions. With probability at least 2/32/3 it outputs an explicit list of edges of a matching of size ν(G)\nu(G).

For every fixed integer κ≥1\kappa\ge1, this gives Cκn1+η(n)C_\kappa n^{1+\eta(n)} instructions on graphs with m≤κnm \le\kappa n, for some constant CκC_\kappa. The same algorithm and exponent envelope work for all κ\kappa, which need not be supplied as an input. At the dense extreme m=Θ(n2)m = \Theta(n^2), the bound is n2+o(1)n^{2+o(1)}.

A perfect matching is not promised. In particular, the perfect-matching procedure for graphs of maximum degree three will be used only after reductions that preserve explicit witnesses. A separate algorithm for each fixed exponent slack would also be insufficient; Section 9 constructs the single finite program and the common envelope in Theorem 1.1.

A reduction also gives an almost-linear bound for prescribed vertex degrees. Given an integer f(v)f(v) with 0≤f(v)≤deg⁡G(v)0 \le f(v) \le\deg_G(v) for every vertex vv, an ff-factor is a spanning subgraph ([n],F)([n], F) with deg⁡F(v)=f(v)\deg_F(v) = f(v) for every vv. Corollary 10.1 gives one uniform randomized algorithm that decides whether an ff-factor exists and returns its edge list when it does, with success probability at least 2/32/3 and (n+m)1+o(1)(n + m)^{1+o(1)} instructions on every computation path. The degree prescription is an array of one-word integers. Section 10 gives the witness-preserving reduction with only logarithmic expansion in the number of edge incidences.

Context and significance

The structure of matchings has long connected combinatorial existence criteria with efficient construction. Hall’s theorem characterizes when a family of sets has distinct representatives [16], and Tutte’s perfect-matching theorem identifies the obstruction caused by odd components [34]. Berge’s augmenting-path criterion turns maximum cardinality into a question about alternating paths [2]. Edmonds made this approach algorithmic in general graphs through blossom contraction and expansion [7]. His matching-polytope theorem gives a complementary explanation of the odd-set constraints [8]: vertex-degree inequalities alone allow, for example, value 1/21/2 on each edge of a triangle.

Tutte’s short proof of the factor theorem reduces prescribed-degree ff-factors to perfect matchings [35]. The reduction in Section 10 follows this incidence-port approach, replacing the local complete connections to auxiliary vertices by the rearrangeable networks used in Section 9. This controls the size of the perfect-matching instance even when a host vertex has high degree. There are also direct algorithms: Gabow finds a maximum-cardinality edge set subject to deg⁡F(v)≤f(v)\deg_F(v) \le f(v) in O(n2/3m)O(n^{2/3}m) time on simple graphs [11], Theorem 4.1. After linear-time input processing, including removal of zero-demand vertices, this gives an O(n+n2/3m)O(n+n^{2/3}m) factor test: an ff-factor exists exactly when the returned set has 2∣F∣=∑vf(v)2|F|=\sum_v f(v).

Batching shortest augmenting paths led to the bipartite algorithms of Hopcroft and Karp [18] and, independently, Karzanov [19], and to the Micali–Vazirani algorithm for general graphs [26, 39]. The latter has running time O(mn)O(m\sqrt{n}) on a RAM; reading the explicit input and removing isolates gives the convenient universal bound O(n+mn)O(n+m\sqrt{n}). This is Oκ(n3/2)O_\kappa(n^{3/2}) when m≤κnm \le\kappa n. Gabow and Tarjan developed a different route through weighted scaling [12], and Gabow later gave a direct weighted-search formulation at the same cardinality bound [10]. On very dense graphs, Goldberg and Karzanov improve the combinatorial bound to O(n+mnlog⁡(n2/m)/log⁡n)O(n+m\sqrt{n}\log(n^2/m)/\log n) by combining skew-symmetric flow with graph compression [15], Theorem 10.3. The weighted problem has its own sequence of improvements: the scaling algorithm of Duan, Pettie, and Su finds an exact maximum-weight matching in O(mnlog⁡(nW))O(m\sqrt{n}\log(nW)) time for integer weights of magnitude at most WW [6], with logarithms bounded below by a constant.

Algebraic methods offer another important approach. Random evaluation of the Tutte matrix connects matching to linear algebra [24]. Mucha and Sankowski, and subsequently Harvey, obtained randomized algorithms that construct maximum matchings at the matrix-multiplication time scale, conventionally written O(nω)O(n^\omega) field operations [17, 28]. These algorithms already recover explicit witnesses and can work over finite fields of polynomial size. Their matrix-multiplication bound is most competitive on dense graphs. Theorem 1.1 instead gives an almost-linear bound in the explicit input size throughout the range of densities, including n2+o(1)n^{2+o(1)} at the dense extreme.

For bipartite matching, the unit-capacity flow formulation permits continuous optimization to accelerate exact search. Mądry’s electrical-flow interior-point method [25] and the moderately dense algorithm of van den Brand et al. [36] were intermediate advances. The almost-linear exact integral-flow algorithms of Chen et al. [3] and van den Brand et al. [37] then yield almost-linear exact bipartite matching. General graphs require additional control of odd blocks. Here that control is provided by the matching state and its local projections. The deterministic flow theorem is used through the explicit static interface in Lemma 2.1.

The proof combines several established ideas with interfaces tailored to that state. Its constructive factor-critical blocks belong to the contraction-and-expansion tradition, while Hall’s theorem underlies the reassignment of their exposed vertices. The multiscale allocation and debt bounds are proved directly. The routing helper uses the cut-matching structure of Khandekar, Rao, and Vazirani [20], together with concentration and conductance estimates [30, 33]. Its recursive virtual graphs follow the hierarchical random-walk embeddings of Ghaffari, Kuhn, and Su [14]. Here the sampled support and the substituted routes must also preserve supplied resource loads, with their full construction costs charged.

The use of approximate minimum-ratio circulations as optimization directions has its modern antecedent in the almost-linear flow framework [3, 37]. Chen et al. prove a deterministic fully dynamic approximate minimum-ratio-cycle theorem with flat forest representations [4]. Our routing hierarchy is related to the origin-aware construction of Rozhoň et al. [29]; the finite forest family and associated cycle extraction adapt the construction in [4]. The preallocated forest copies used to lift recursive paths follow Kyng, Meierhans, and Probst Gutenberg [21]. Sections 5 and 8 specify how retained mapped edges preserve accumulated coordinate changes and absolute motion through these representation updates. The recent distance-oracle approach of Kyng et al. [22] provides another development of this method. Sections 7 and 8 supply the complete backend used here, including its adaptive guarantees, explicit changes of representation, stable edge-copy lifetimes, and bounds on traversal length before cancellation. Those guarantees are the inputs to our priced-step analysis.

Main ideas and organization

The central subproblem is to find a perfect matching in a graph of maximum degree three. Section 9 reduces exact cardinality queries to this subproblem while retaining the original edge identifiers, so that every successful answer can be decoded into a matching of the input graph.

The perfect-matching procedure maintains a current matching through a partition of the vertices. Its odd blocks, called bins, come with internal matchings after any prescribed vertex is left exposed. Some outside singleton vertices, called rows, are assigned along original edges to distinct bins. Each assigned bin matches its exposed vertex to its row; an unassigned bin contributes one unmatched vertex. The remaining vertices are stored as matched pairs, apart from unmatched vertices set aside during repairs. This representation permits a change of exposure without immediately expanding a nested block.

The difficulty is to repair this representation after structural changes without repeatedly scanning all its odd blocks. A ledger allocates a fixed amount from each row among its neighboring bins. The difference between a bin’s capacity and its allocated load is its residual. Several ledgers impose residual margins proportional to bin size; a nonnegative debt allows a margin to fail temporarily. At each settled state, the lowest ledger has no debt and certifies a strict Hall surplus for every nonempty set of bins. The highest ledger carries a logarithmic objective that must admit progress when a perfect matching exists and no structural operation is available.

The intermediate ledgers turn that progress into affordable repairs. A repair is an exact flow problem on row–bin incidences, initially explored only at bins whose debt is substantial relative to their size. An unexplored boundary bin temporarily accepts an optimistic amount of flow. If enough arrives, the algorithm explores that bin and permanently locks in an absorbed amount proportional to its size. The total available flow is bounded by the starting debt, so these locks bound the number of physical vertices examined. If the requested residual margin is infeasible, the repair instead removes a set of bins. The gap between adjacent margins makes this removal decrease debt in every preserved coarser ledger by an amount proportional to the removed size. Thus debt pays both for local exploration and for removing blocks from the state. The logarithmic optimization uses exact conservation throughout; integral cut inequalities turn a point whose total bound violation is below one into a certificate of exact feasibility. A final local cut also recovers the entire residual source-reachable set needed by the matching repair.

Both the matching objective and these local flow tests use the same priced-step interface. It searches for a circulation direction with sufficient objective increase relative to its weighted length. When it accepts such a direction, it takes a small exact dyadic step. The direction is represented by individual edges and paths in a changing forest, so a long path need not be expanded for every step. The implementation separately records signed coordinate changes and absolute motion. The latter counts repeated traversals before cancellation and controls when a coordinate must be read and repriced.

The cycle data structure supplying this interface is constructed in full. A static routing sparsifier first provides short routes whose total use of specified resources is bounded. During an interval of updates, a frozen collection of forests then decomposes every current circulation into local correction cycles and a circulation in one smaller graph. A hierarchy of routing snapshots limits the number of new representative edges added to that graph. Finally, prebuilt copies of the paths represented by its edges lift its forest back to the current graph. When recursive occurrences change at otherwise unaffected child labels, these copies retain their identities. This preserves the exact accumulated values used by the priced-step implementation; replacing an affected copy first transfers its saved history.

Let SS be a power-of-two upper bound on the number of vertices in the reduced graph. For each sufficiently large fixed parameter aa, these ingredients yield time S1+O(1/a)+oa(1)S^{1+O(1/a)+o_a(1)} for a subcubic perfect-matching test. The coefficient hidden in O(1/a)O(1/a) is absolute. Logarithmic powers may depend on the fixed parameter. Deterministic prerequisite failures suspend a parameter branch; exhausted random retries terminate its test with a possibly erroneous negative answer. This distinction permits an every-path asymptotic bound. Finally, instruction-level dovetailing with summable error budgets turns all fixed-parameter guarantees into Theorem 1.1, without a convergence rate or an input-dependent table of thresholds.

Sections 3 and 4 develop the matching algorithm assuming the priced-step interface. Section 5 proves that interface from the flat-cycle backend. Section 6 gives the static helper, and Sections 7 and 8 prove the backend’s quality and implementation guarantees. Section 9 completes the reductions and the uniform finite-word implementation. Section 10 applies the resulting matching algorithm to prescribed-degree factors through a linearithmic-size reduction.

The principal interfaces and their proof dependencies are summarized below.

ResultRole in the proof
Theorem 4.7Fixed-parameter subcubic perfect-matching search; Sections 3–4 use Lemma 5.1.
Lemma 5.1Priced logarithmic steps; Section 5 proves the interface from Lemma 5.2.
Lemma 5.2Flat-cycle backend; Sections 7–8 construct it using the static routing helper, Lemma 6.1.
Theorem 1.1Explicit minimum matching with one input-size exponent envelope; Section 9 applies the witness reductions and instruction-level schedule to Theorem 4.7.

Table 1.

Conventions and static primitives

Representations and fixed-parameter bounds

Auxiliary graphs may have parallel edges or arcs, always distinguished by identifiers. Fix a reference orientation on every variable edge. Traversing an edge backward negates its coefficient. A signed circulation has zero divergence at every vertex; its length norm for positive lengths ℓ\ell is

∥ℓf∥1=∑eℓe∣fe∣.\lVert\ell f\rVert_1 = \sum_e \ell_e |f_e|.

This norm differs from the raw length of a supplied traversal list: the latter counts every traversal with its multiplicity, before cancellation. Later a forest edge may map either to an actual graph edge, with its endpoint correspondence specified, or to a null edge whose two endpoints have the same image. A null traversal has zero actual projected length, although a reduction may assign it an additional positive bookkeeping length.

All representation sizes include vertices or slots, individual edges, terminal incidences, and explicitly stored lists. Ordinary adjacency lists, heaps, balanced dictionaries, and path-copy persistent maps incur logarithmic overhead per record operation. No argument permits a free scan of all coordinates after an implicit path update. Arithmetic and key-length costs are included separately when they exceed one word.

The matching procedure uses a master bound S=2sS = 2^s, an integer parameter a≥1000a \ge1000, and a reliability parameter σ\sigma. In the final schedule σ≤a+1\sigma\le a + 1. A bound of the form

SO(1/a)+oa(1)S^{O(1/a)+o_a(1)}

has an absolute coefficient in O(1/a)O(1/a); for each fixed a,σa,\sigma, the second exponent tends to zero as S→∞S \to\infty. Constants and powers of logarithms may depend on these fixed parameters. All smaller local routines measure their permitted logarithmic factors against the indicated master bound. The parameters are not fixed uniformly while taking a→∞a \to\infty.

An implementation may check a deterministic size or precision prerequisite. If that check is inadequate, it suspends the entire parameter branch without an answer. In contrast, exhaustion of a capped randomized routine is a detected failure; the calling perfect-matching test returns a negative answer promptly. The fixed-parameter analysis proves that deterministic suspensions cannot occur on any path once the input is sufficiently large for that fixed parameter. It does not require random attempts always to succeed. These conventions are used in Theorem 4.7 and the schedule in Section 9.

Exact integral flow

Lemma 2.1 (Static integral flow). For an explicitly represented directed network of total size at most PP, with integral capacities, demands and costs bounded in magnitude by a fixed power of PP, exact integral minimum-cost flow can be computed uniformly and deterministically in P1+o(1)P^{1+o(1)} time. Its finite-precision operations can be simulated with polynomially logarithmic overhead on logarithmic-bit words. In particular, integral source-sink maximum flow with nonnegative upper capacities and zero lower capacities returns an explicit integral arc vector and a residual-reachability minimum-cut certificate within that bound.

Proof. Use the deterministic minimum-cost-flow theorem of van den Brand et al. [37], Theorem 1.1, with its finite fixed-point model and deterministic integral rounding [37], Section 2 and Lemma 4.1. The stated logarithmic dependence on integral magnitudes and polynomial logarithmic word lengths is absorbed in Po(1)P^{o(1)}. A fixed-point word is stored as a charged array of logarithmic-bit words. Longer virtual addresses can be keys in a dictionary of touched cells; no unused address space is initialized.

Maximum flow is obtained by adding a bounded sink-to-source return arc and minimizing its negative flow. Its capacity can be the sum of the original capacities. Feasibility and absence of a residual source-sink path certify maximality. Residual reachability supplies the cut. ∎

Only the nonnegative-upper-capacity maximum-flow specialization is called algorithmically below. Integral lower bounds are used in feasibility arguments through the classical cut criteria for circulation feasibility [9, 13]. The following consequence records the precision margin we use.

Lemma 2.2 (Integral cuts from a small total violation). Let every lower and upper arc bound be integral, with lower bound no larger than upper bound. If an exactly conserved real arc vector has total bound violation less than one, the bounds admit an exactly feasible integral circulation.

Proof. For a vertex set XX, feasibility requires the sum of lower bounds on arcs leaving XX to be at most the sum of upper bounds on arcs entering XX. Conservation of the real vector implies that any failure of this inequality is at most its total bound violation. The two bound sums are integers, so a positive discrepancy would be at least one, a contradiction. The circulation cut criterion therefore holds. To obtain that criterion, subtract the lower bounds, introduce a super-source and super-sink for the resulting vertex imbalances, and apply the integral maximum-flow/minimum-cut theorem. Saturating the imbalance arcs gives the asserted integral circulation.

Large capacities relative to a small local graph do not require a different finite program for each magnitude exponent.

Lemma 2.3 (One polynomial-capacity implementation). For maximum flow with nonnegative integral upper capacities of at most bb bits, a single fixed polynomial-capacity version of Lemma 2.1 suffices, using bb calls on linear-size residual graphs, together with the charged capacity arithmetic and identifier translations.

Proof. Begin with zero capacities. In each binary digit round write the new capacity vector as c′=2c+ξc' = 2c + \xi, where every ξe\xi_e is zero or one. If ff was a maximum flow of value vv for cc, then 2f2f is feasible for c′c'. Let AA be the number of original arcs. An old minimum cut has new capacity at most 2v+A2v + A, so the largest residual augmentation has integral value Δ≤A\Delta\le A.

Decompose an optimal integral residual augmentation into source–sink paths and cycles and discard the cycles. Its remaining total path value is Δ\Delta, so every forward and reverse residual arc carries at most Δ≤A\Delta\le A. Truncating every residual capacity at AA therefore preserves the optimum augmentation. Compute it with the fixed polynomial-capacity routine. Adding forward usage and subtracting reverse usage updates 2f2f to a maximum flow for c′c'. This proves the induction over digits.

Local vertices and arcs can be renumbered, using dictionaries to translate their caller identifiers on input and output. Integer arrays, comparisons, and translations are charged at their actual bit or multiword cost. In the fixed-parameter applications below, bb and all key lengths contribute only the permitted logarithmic powers in the master size.

When paths from an integral flow are needed, pair incoming and outgoing flow units and trace source paths, dropping cycles. We charge the total represented throughput, not merely the number of graph arcs. The routing helper supplies the explicit throughput bounds at each such use.

A clocked fallback

The final schedule needs one fixed polynomial fallback, solely to guarantee halting and polynomial physical addressability at every finite input size. Edmonds’ deterministic algorithm supplies the following interface.

Lemma 2.4 (Polynomial perfect-matching fallback). There is one uniform deterministic algorithm on explicit loopless graphs of maximum degree three that halts within a fixed polynomial number of finite-word instructions. It returns a checked perfect matching when one exists and a negative answer otherwise.

Proof. Run Edmonds’ deterministic polynomial-time maximum-cardinality matching algorithm [7], Section 2, pp. 451–452. For parallel edge copies, first deduplicate unordered endpoint pairs while retaining one original edge identifier for each pair. This preserves perfect matchability and explicit witness decoding. Return the computed matching if it covers every vertex, and a negative answer otherwise; check every returned identifier and vertex incidence before acceptance.

The classical algorithm, the deduplication, and this check have a fixed polynomial clock without a matchability promise. Their combinatorial records and polynomially bounded integer indices have polynomial bit cost, so charged multiword and touched-address implementations retain a fixed polynomial bound in the stated model. Exact maximum cardinality makes the returned answer correct in both cases.

The two witness-preserving reductions used with this fallback are proved explicitly in Section 9.

Matching states and structural operations

We describe a perfect-matching procedure on a loopless graph of maximum degree three. This section develops its combinatorial state, exact ledger transformations, and structural searches. The local implementation of projection and the phase analysis follow in Section 4. The dynamic optimization interface used here is Lemma 5.1, proved later.

The graph has N≤SN \le S vertices, where S=2sS = 2^s is a master size bound. Disconnected graphs are allowed; parallel edge copies retain separate identifiers, and degree counts incidences. A successful answer is an explicit perfect matching, checked before acceptance. A negative answer may arise from a capped randomized search, whose error is bounded later. A deterministic prerequisite failure instead suspends this parameter branch without an answer. Perfect matchability will prove progress, never a running-time bound.

The phase state and its ledgers

The empty graph is settled directly, and odd NN gives a negative answer. Otherwise start with the empty matching and work in phases. A phase starts with an actual matching MM, whose positive deficit is K=N/2−∣M∣K = N/2 - |M|. At deficit zero the procedure is finished. Within a phase we represent the changing matching by odd blocks and single vertices assigned to those blocks.

A bin is a physical odd vertex set with a constructive factor-critical witness: after prescribing any one vertex as its exposure, the others can be matched internally. Its weight is wd=(∣d∣+1)/2w_d = (|d| + 1)/2. The bins form a disjoint family D\mathcal{D}. The rows A\mathcal{A} are physical singleton vertices outside them. An explicit injection

μ:A→D\mu: \mathcal{A} \to\mathcal{D}

assigns each row along a specified physical edge to its bin. The bipartite incidence graph B\mathcal{B} contains every physical row–bin edge, with different incidences retained separately. Each row has degree at most three.

An assigned bin exposes the physical endpoint of its assigned edge and is matched there to its row. A free, or unassigned, bin exposes one unmatched vertex. The remaining unblocked vertices form a set UU of explicitly matched pairs. A phase may also set aside individual unmatched vertices as blockers. This state specifies an actual matching, although a changed internal exposure need not be propagated through a bin witness until materialization. Initially the bins are the unmatched singleton vertices, UU contains all matched pairs, and there are no rows or blockers.

Constructive odd blocks, with an exposed vertex chosen during expansion, follow the blossom contraction-and-expansion tradition of Edmonds [7] (Sections 4.10–4.14 and 7.1–7.2). Here each block carries the witness needed to expand the represented matching; the phase analysis below proves the required progress bound.

For X⊆DX \subseteq\mathcal{D}, define its captive rows and deficiency by

A(X)={r∈A:NB(r)⊆X},h(X)=∣X∣−∣A(X)∣.(1)A(X)=\{r\in A:N_B(r)\subseteq X\},\qquad h(X)=|X|-|A(X)|. \tag*{(1)}

Each row has its assigned bin as a neighbor. The injection therefore gives h(X)≥0h(X)\ge0, even at intermediate states. Write v(X)=∑d∈Xvdv(X)=\sum_{d\in X}v_d for a bin function vv.

Fix integers a≥1000a\ge1000 and 0≤σ≤a+10\le\sigma\le a+1, and set C=a+1C=a+1. The phase seeks

g∗=max⁡{1,⌈K100C⌉},L=⌈10000CNK⌉(2)g_*=\max\left\{1,\left\lceil\frac{K}{100C}\right\rceil\right\},\qquad L=\left\lceil\frac{10000CN}{K}\right\rceil \tag*{(2)}

gains, each increasing the matching size by one. The parameter LL will be the amount allocated by each row in the ledgers below. The choices balance the gain target against the work permitted per gain: Lg∗=Oa(N)Lg_*=O_a(N), including when K<100CK<100C, since then g∗=1g_*=1 and L≤10000CN+1L\le10000CN+1. At a phase boundary we materialize the matching and initialize a new state.

For the reset periods, pricing steps and exact arithmetic, put

B=2⌈s/a⌉,q=B−100,δ=S−1000,ε=S−3000.(3)B=2^{\lceil s/a\rceil},\qquad q=B^{-100},\qquad\delta=S^{-1000},\qquad\varepsilon=S^{-3000}. \tag*{(3)}

The top ledger uses the grid εZ\varepsilon\mathbb{Z}; the other ledgers use integers. Their common purpose is to retain enough unallocated capacity at each bin to rearrange the row assignment. Debt records a temporary shortfall from the specified residual floor.

Definition 3.1 (Ledger invariant). There are ledgers j=0,…,aj=0,\ldots,a, with cj=C−jc_j=C-j. Ledger jj has nonnegative incidence allocations xejx_e^j, with

References

  1. [1]V. E. Beneš. Optimal rearrangeable multistage connecting networks. Bell System Technical Journal, 43(4):1641–1656, 1964. doi: 10.1002/j.1538-7305.1964.tb04103.x. URL https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1964.tb04103.x.DOI
  2. [2]Claude Berge. Two theorems in graph theory. Proceedings of the National Academy of Sciences of the United States of America, 43(9):842–844, 1957. doi: 10.1073/pnas.43.9.842. URL https://doi.org/10.1073/pnas.43.9.842.
  3. [3]Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612–623. IEEE, 2022. doi: 10.1109/FOCS54457.2022.00064. URL https://arxiv.org/abs/2203.00671v2. Full version: arXiv:2203.00671v2.
  4. [4]Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, and Maximilian Probst Gutenberg. Almost-linear time algorithms for incremental graphs: Cycle detection, SCCs, s–t shortest path, and minimum-cost flow, 2023. URL https://arxiv.org/abs/2311.18295v1. arXiv:2311.18295v1.
  5. [5]Elias Dahlhaus and Marek Karpinski. Perfect matching for regular graphs is AC⁰-hard for the general matching problem. Journal of Computer and System Sciences, 44(1):94–102, 1992. doi: 10.1016/0022-0000(92)90005-4. URL https://doi.org/10.1016/0022-0000(92)90005-4.
  6. [6]Ran Duan, Seth Pettie, and Hsin-Hao Su. Scaling algorithms for weighted matching in general graphs. ACM Transactions on Algorithms, 14(1):8:1–8:35, January 2018. doi: 10.1145/3155301. URL https://doi.org/10.1145/3155301.
  7. [7]Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449–467, 1965. doi: 10.4153/CJM-1965-045-4. URL https://doi.org/10.4153/CJM-1965-045-4.
  8. [8]Jack Edmonds. Maximum matching and a polyhedron with 0, 1-vertices. Journal of Research of the National Bureau of Standards, Section B: Mathematics and Mathematical Physics, 69B(1–2):125–130, 1965. URL https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf.DOI
  9. [9]L. R. Ford, Jr. and D. R. Fulkerson. Network flow and systems of representatives. Canadian Journal of Mathematics, 10:78–84, 1958. doi: 10.4153/CJM-1958-009-1. URL https://doi.org/10.4153/CJM-1958-009-1.
  10. [10]Harold N. Gabow. The weighted matching approach to maximum cardinality matching. Fundamenta Informaticae, 154(1–4):109–130, 2017. doi: 10.3233/FI-2017-1555. URL https://arxiv.org/abs/1703.03998.
  11. [11]Harold N. Gabow. Maximum cardinality f-matching in time O(n²/3ₘ). ACM Transactions on Algorithms, 21(1):9:1–9:28, 2025. doi: 10.1145/3696668. URL https://arxiv.org/abs/2311.14236v1. Published online December 2, 2024.
  12. [12]Harold N. Gabow and Robert E. Tarjan. Faster scaling algorithms for general graph-matching problems. Journal of the ACM, 38(4):815–853, 1991. doi: 10.1145/115234.115366. URL https://doi.org/10.1145/115234.115366.
  13. [13]David Gale. A theorem on flows in networks. Pacific Journal of Mathematics, 7(2):1073–1082, 1957. URL https://msp.org/pjm/1957/7-2/pjm-v7-n2-p04-p.pdf.
  14. [14]Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su. Distributed MST and routing in almost mixing time. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 131–140. ACM, 2017. doi: 10.1145/3087801.3087827. URL https://groups.csail.mit.edu/tds/papers/Ghaffari/podcl117.pdf.DOI
  15. [15]Andrew V. Goldberg and Alexander V. Karzanov. Maximum skew-symmetric flows and matchings. Mathematical Programming, 100(3):537–568, 2004. doi: 10.1007/s10107-004-0505-z. URL https://arxiv.org/abs/math/0304290v2.
  16. [16]Philip Hall. On representatives of subsets. Journal of the London Mathematical Society, s1-10(1):26–30, 1935. doi: 10.1112/jlms/s1-10.37.26. URL https://doi.org/10.1112/jlms/s1-10.37.26.
  17. [17]Nicholas J. A. Harvey. Algebraic algorithms for matching and matroid problems. SIAM Journal on Computing, 39(2):679–702, 2009. doi: 10.1137/070684008. URL https://doi.org/10.1137/070684008.
  18. [18]John E. Hopcroft and Richard M. Karp. An n⁵⁄² algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4):225–231, 1973. doi: 10.1137/0202019. URL https://doi.org/10.1137/0202019.
  19. [19]A. V. Karzanov. An exact estimate of an algorithm for finding a maximum flow, applied to the problem “on representatives”. In Voprosy Kibernetiki. Trudy Seminara po Kombinatornoi Matematike (Moscow, 1971), pages 66–70. Sovetskoe Radio, Moscow, 1973. URL https://alexander-karzanov.net/ScannedOld/73_tochn-ots_transl.pdf. In Russian; English translation by the author.
  20. [20]Rohit Khandekar, Satish Rao, and Umesh V. Vazirani. Graph partitioning using single commodity flows. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pages 385–390. ACM, 2006. doi: 10.1145/1132516.1132574. URL https://people.eecs.berkeley.edu/~vazirani/pubs/partitioning.pdf.DOI
  21. [21]Rasmus Kyng, Simon Meierhans, and Maximilian Probst Gutenberg. A dynamic shortest paths toolbox: Low-congestion vertex sparsifiers and their applications, November 2023. URL https://arxiv.org/abs/2311.06402v1. Version 1, November 10, 2023.
  22. [22]Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg, and Aurelio Sulser. A simpler and faster min-cost flow solver via min-ratio cycles from distance oracles, 2026. URL https://arxiv.org/abs/2609.23852v1. Version 1, September 20, 2026.
  23. [23]Leonid A. Levin. Universal sequential search problems. Problems of Information Transmission, 9(3):265–266, 1973. URL https://www.mathnet.ru/eng/ppi914. Russian original in Problemy Peredachi Informatsii 9(3), 115–116.
  24. [24]László Lovász. On determinants, matchings, and random algorithms. In Lothar Budach, editor, Fundamentals of Computation Theory, FCT ’79, pages 565–574, Berlin, 1979. Akademie-Verlag. URL https://www.math.uwaterloo.ca/~harvey/W11/1979-Lovasz-OnDeterminantsMatchingsAndRandomAlgs.pdf.
  25. [25]Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back, 2013. URL https://arxiv.org/abs/1307.2205v3. FOCS 2013; full version 3, October 24, 2013.
  26. [26]Silvio Micali and Vijay V. Vazirani. An O(√|V| |E|) algorithm for finding maximum matching in general graphs. In 21st Annual Symposium on Foundations of Computer Science, pages 17–27. IEEE, 1980. doi: 10.1109/SFCS.1980.12. URL https://ics.uci.edu/~vazirani/MV.pdf.DOI
  27. [27]Gary L. Miller, Richard Peng, and Shen Chen Xu. Parallel graph decompositions using random shifts. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures, pages 196–203, 2013. doi: 10.1145/2486159.2486180. URL https://arxiv.org/abs/1307.3692.
  28. [28]Marcin Mucha and Piotr Sankowski. Maximum matchings via Gaussian elimination. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 248–255. IEEE, 2004. doi: 10.1109/FOCS.2004.40. URL https://www.mimuw.edu.pl/~mucha/pub/mucha_sankowski_focs04.pdf.DOI
  29. [29]Václav Rozhoň, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, and Jason Li. Undirected (1 + ε)-shortest paths via minor-aggregates: Near-optimal deterministic parallel & distributed algorithms, 2022. URL https://arxiv.org/abs/2204.05874v2. Version 2, September 23, 2022; author order randomized.
  30. [30]Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing markov chains. Information and Computation, 82(1):93–133, 1989. doi: 10.1016/0890-5401(89)90067-9. URL https://people.eecs.berkeley.edu/~sinclair/approx.pdf.DOI
  31. [31]Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362–391, 1983. doi: 10.1016/0022-0000(83)90006-5. URL https://www.cs.cmu.edu/afs/cs.cmu.edu/user/sleator/www/papers/dynamic-trees.pdf.DOI
  32. [32]Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32(3):652–686, 1985. doi: 10.1145/3828.3835. URL https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf.DOI
  33. [33]Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389–434, 2012. doi: 10.1007/s10208-011-9099-z. URL https://arxiv.org/abs/1004.4389v7. arXiv:1004.4389v7.
  34. [34]W. T. Tutte. The factorization of linear graphs. Journal of the London Mathematical Society, s1-22(2):107–111, 1947. doi: 10.1112/jlms/s1-22.2.107. URL https://doi.org/10.1112/jlms/s1-22.2.107.
  35. [35]W. T. Tutte. A short proof of the factor theorem for finite graphs. Canadian Journal of Mathematics, 6:347–352, 1954. doi: 10.4153/CJM-1954-033-3. URL https://doi.org/10.4153/CJM-1954-033-3.
  36. [36]Jan van den Brand, Yin-Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Bipartite matching in nearly-linear time on moderately dense graphs. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 919–930. IEEE, 2020. doi: 10.1109/FOCS46700.2020.00090. URL https://doi.org/10.1109/FOCS46700.2020.00090.
  37. [37]Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford. A deterministic almost-linear time algorithm for minimum-cost flow, 2023. URL https://arxiv.org/abs/2309.16629v1. arXiv:2309.16629v1; full version of the FOCS 2023 paper.
  38. [38]Jan van den Brand, Yang P. Liu, and Aaron Sidford. Dynamic maxflow via dynamic interior point methods. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1215–1228. ACM, 2023. doi: 10.1145/3564246.3585135. Full version: arXiv:2212.06315v1.DOI
  39. [39]Vijay V. Vazirani. A theory of alternating paths and blossoms from the perspective of minimum length. Mathematics of Operations Research, 49(3):2009–2047, 2024. doi: 10.1287/moor.2020.0388. URL https://ics.uci.edu/~vazirani/Matching_paper.pdf. Corrected version of record, updated November 15, 2024.DOI

Paper details

vlnc:W_g7qkfsyf
Version
v1 · latest
Published
License
LicenseRef-OpenAI-public
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

unreleased internal OpenAI model

View statement
Looking for related papers…
Contents