WorksComputer Science
Deterministic almost-linear time for general matching and network flow
Abstract
We give deterministic almost-linear-time algorithms for maximum-cardinality matching in general graphs and integral minimum-cost flow. With , both run in time for polynomially bounded integer flow data. Their circulation oracle charges every traversal of a returned walk. A clipped logarithmic potential handles flow thresholds under improving updates and maintains strong components under arc insertions. For subgraphs with degree bounds, two matching computations encode a factor of every feasible size. The underlying exchange argument also gives integral cardinality slices for capacitated factors and is compatible with sharp local rounding.
Introduction
Matching in a general graph must respect odd sets, while flow in a network must respect balances and capacities. Both algorithms find improvements by assigning prices and lengths to edges and searching for a circulation of large gain per unit of length. Its length charges every traversal in the returned walks.
Theorem 1.1 (Matching and flow). Let for a graph with vertices and edges. A maximum-cardinality matching in an undirected graph and a minimum-cost integral flow with prescribed balances and arc bounds in a directed graph can each be found in deterministic time
Flow data are integers of magnitude . The outputs are original matching edges and integral values on the original arcs, respectively. The flow algorithm reports infeasibility when appropriate.
An odd path replaces each vertex of the matching instance. On the resulting subcubic graph a phase either enlarges the matching or bounds its distance from optimum. For flow we extend the logarithmic potential by its tangent near zero. The extension measures capacity violations, and an Euler-tour rounding recovers an integral optimum. § 2–§ 4 give these arguments.
The flow algorithm also finds the first prefix meeting a cost threshold under insertions, relaxations of arc bounds and cost decreases. Its one-sided potential maintains the strong components of an insertion stream. A single sparse subgraph certifies their entire history (§ 5).
Two matching computations suffice to represent every feasible cardinality of a subgraph with degree intervals. With integral edge capacities, the same alternating-trail argument shows that every integer cardinality slice of the factor polytope is integral (§ 6). § 7 gives a common reduction for matching and flow using a spanning forest. Table 1 compares the running times with those for distances, spanners and cut trees.
| Problem | Total work | Output |
| Exact algorithms for matching, flow and strong components | ||
| General matching | Maximum set of disjoint original edges | |
| Unit edges with degree bounds | A factor of every feasible size, in one representation | |
| Static min-cost flow | Integral optimum and a description of the optimal face | |
| Improving flow updates | First prefix meeting the cost threshold and an integral flow | |
| Incremental strong components | Exact labels and one certificate for all prefixes | |
| Distance, spanner and cut algorithms from [12] | ||
| Incremental directed single-source distances | -approximate distances and simple paths | |
| Fully dynamic distances | Point estimates of stretch in polylogarithmic query time | |
| Fully dynamic spanners | , | Stretch , size , and or edge changes, respectively |
| Decremental strong forest | Fixed representatives and approximate paths to the terminal set | |
| Static Gomory–Hu tree | All pairwise minimum cut values and cut partitions |
Table 1. Deterministic running times. Dynamic bounds include initialization and all updates. Section 8 gives the accuracy and input assumptions for the metric bounds.
Here . In a static graph counts input edges. For an update sequence it is the number of initial edges plus the number of updates. For spanners, counts deletions. With and , write .
Prior work. Chen et al. [5] introduced the minimum-ratio-cycle approach to almost-linear-time flow. Van den Brand et al. [4] gave a deterministic algorithm, and Chen et al. [6] extended the approach to incremental flow and strong components. Kyng et al. [10] derive minimum-ratio cycles from a dynamic distance oracle. The general matching algorithm of OpenAI [14] is randomized.
The deterministic routing bound and matching phase used here are proved in the general matching manuscript in [12]. § 2 gives the parameter calculation behind the four-fifths exponent.
We work on a word RAM with word-sized identifiers and degree bounds. Longer arithmetic is charged at its actual word cost. Parallel edges retain their identifiers. A matching uses edges with distinct ends. For degree constraints a loop contributes two incidences.
Circulations and traversal length
Orient a multigraph arbitrarily. Its incidence matrix records head minus tail, with a zero column for each loop. Given prices and lengths , write
taking for a trivial kernel. Orienting the support by the signs of decomposes it into directed cycles with additive length and price. Thus a simple cycle attains any positive optimum.
Proposition 2.1 (Routing theorem [12 general matching, Section 8.1, Theorem 11.6 and Eq. (77)]). For degree at most three, fix polynomial bounds in a size parameter on graph size, integer labels and the total number of edits and queries. Each operation may depend on all completed operations. There is a deterministic data structure with a computable bound
A query returns a list of signed edges and forest paths projecting to a circulation . Write for the number of traversals of edge in the list, and put . If , then and .
Initialization costs per record. Updates and queries cost amortized, including path pieces and representation changes. Each native edge has at most forest copies, counting inactive copies. A copy has one fixed signed native edge or an empty image until its retirement, which exposes the old image.
Consume or discard each returned list before the next routing operation. Path aggregates compute and the price without expanding the list. Out-and-back traversals count twice in .
The exponent. At one level of routing, replacing an edge on a cycle by a walk leaves a local correction . The corrections and the routed cycle have the original total price. Their total traversal length therefore bounds the loss when one keeps the best ratio.
Put and . In [12 general matching, Eqs. (73)–(77)], set , repair depth and logarithmic shrinkage . The logarithmic local cost is , and each of levels contributes to log work and inverse quality. Hence
This choice gives the asserted exponent. The child-record growth has logarithm and stored labels use bits. The cited construction fixes its cap before the first update. Bounded sizes are handled directly.
Splitting degrees. In a numerical graph replace each vertex by a path with a port for every incident end. Give its connectors unit length and zero price. An original circulation lifts by putting the signed prefix imbalance on each connector. With ports in all, the added length is at most . Projection preserves the price and the balances. New ends append ports, and repricing reuses the old ones.
Maximum matching
Lemma 3.1 (Odd paths [12 general matching, Lemma 3.2]). Discard loops and isolated vertices. Replace a vertex of degree by a path of vertices, attaching its incident edges to distinct odd positions. Distinct ports separate parallel edges. For the resulting simple subcubic graph ,
where denotes the maximum matching size. Construction and decoding take linear time.
Proof. A matching of leaves at most one occupied port per path. Leave that port available, or the first port if none is occupied. The even segments on either side supply internal edges.
Conversely, let be the external edges of a matching of and let . Every internal edge uses an even vertex and an unoccupied odd vertex. Hence its path supplies at most edges, where .
Each vertex incident to chooses one of its edges. Keep those chosen at both ends. This discards at most edges, one charge per rejection, and gives a matching of size at least the input matching size minus .
Proposition 3.2 (Matching phase [12], general matching, Sections 7, 8.6 and 12.2). On an -vertex subcubic graph, a phase with target either gains matching edges or certifies that the initial gap was less than . On a certificate the phase keeps its gains. With the valid caps of Proposition 2.1, the cost per phase is .
The phase contracts factor-critical odd sets and prices circulations in an auxiliary allocation graph. If the initial gap was at least , after gains the symmetric difference with an optimum contains at least disjoint augmenting paths. The cited lemma turns their prefixes into a comparison circulation until the promised gain is reached. This is the low-gain certificate. The local projection costs sum over the phase by the volume bound in the cited construction. Its uniform implementation verifies a candidate maximum matching by an independent augmenting-path search.
Descending targets. Start with a greedy matching and the largest power of two for . Repeat until a certificate, then halve . Stop after the certificate at . Smaller graphs are immediate.
At entry to a scale the gap is less than . The phase guarantee therefore gives phases per scale. The last certificate gives gap zero. Since has vertices and edges, Lemma 3.1 proves the matching assertion of Theorem 1.1.
Integral flow with a fixed potential
Fix balances , a cost threshold , and an integral starting flow within the bounds . New arcs enter at zero. We first solve this threshold problem, then construct the starting flow and optimize over .
A feasible direction
Let bound the total number of arcs, including auxiliary arcs. Take a power of two bounding , , all numerical data and . Put , and . Extend the natural logarithm by its tangent at ,
For positive cost gap , define
At each prefix use the following rule.
If , round to an integral witness (§ 4.3).
Otherwise, query the priced graph. If the ratio test fails, this prefix has no flow of cost at most . Retain for the next insertion.
On success, add the scaled circulation of Lemma 4.2 and repeat.
Each update preserves .
Lemma 4.1 (Comparison). Write and . If is feasible with , then is a circulation and
Proof. For , the difference is , since . For , the same bound follows from . The cost term contributes .
One step for both potentials
Take to be the least power of two at least and put . Each coordinate is read at an anchor . For each arc term , , evaluate at that anchor. Denote the sum of these weights on by and their signed sum by . Thus .
Freeze a price at each edge. Give it integer price and length , with . Give port connectors price zero and length one. Sign the returned list to make , where is its native projection. Recall its full traversal length from Proposition 2.1.
Lemma 4.2 (Gain per step). Suppose for all . If and , choose a power of two such that
Set . Let be the remaining term of the potential after the arc terms. If lies above its tangent from to and
then the full potential increases by at least .
Proof. The total weighted motion on the list is bounded by . In particular .
Along the step, each slack differs from its anchor by at most . The map is 1-Lipschitz, so . Integration bounds the change in the arc terms below by .
Add the tangent inequality for . Price rounding gives , while . The total gain is at least .
Prices for the threshold test. At the start of an epoch read all coordinates and store . Use . Start a new epoch whenever . Between epochs refresh an edge when its accumulated motion requires a new anchor. The global cost term has the exact identity
As in Lemma 4.2, each true scale is within a factor of , and the right-hand side has magnitude at most at edge .
Round to the nearest integer. One slack is at most , so . As , the required price accuracy holds. At most ports occur, and the connectors and length rounding together add to the length of a lifted circulation. Lemma 4.1 therefore gives a rounded ratio at least whenever a feasible comparison exists. In that case the routing theorem guarantees .
For an accepted list, . The new gap is at least half the old one. Convexity of now supplies the tangent inequality, and Lemma 4.2 applies with .
Stopping and rounding
Let and . Each pair of arc terms satisfies
Inside the box this follows from for . At distance outside the box the slacks are , . Their contributions are at most and .
At a feasible starting flow above the threshold, . A new zero-flow arc reduces by at most , and changing anchors leaves unchanged. An integral start with already meets the threshold. Otherwise the gap stays at least through the last step. Summing Lemma 4.2 and (4) gives at every completed step
where counts accepted steps across all arrivals.
Lemma 4.3 (Euler rounding [7]). If , is integral and is integral, one can round to an integral flow with the same balances in scalar operations. Each lies in , and an affine objective specified by its coefficients on can be kept from increasing.
Proof. At digit , keep the edges with odd numerator . They have even degree at every vertex because is even. Orient an Euler tour in each component and let record its direction, zero elsewhere. A loop forms a one-edge tour. Both preserve the balances, stay in their integer intervals and lie on the next coarser grid. Their objectives average to the old value. Choose the cheaper sign. Each pass scans the edges and only their incident vertices.
When , apply Lemma 4.3 with the objective
It is affine on the rounding box because its breakpoints are integers. By (5), for large . The rounded objective is below , and each coordinate lies in . One unit of violation would already give objective at least . The output is therefore feasible and its integral cost at most .
The same rounding applies to the local flow projections in the matching phase [12 general matching, Sections 8.3–8.5]. There one minimizes the total violation alone. An initial violation less than one rounds to zero.
Cost of maintaining prices
Store signed increments and absolute motion on every forest copy. At retirement transfer these to the native base and a motion counter. Single-edge pieces update both directly. Connectors carry only length. An exact reading adds live signed increments to the base. Signed sums, path additions and minimum remaining motion are dynamic-tree aggregates [2, 12].
For a sufficiently small fixed dyadic , flag an edge if a copy accumulates motion or the retirement counter reaches . Round thresholds down to powers of two. At most live copies then give drift at most before a flag. Each flagged copy continues accumulating motion and emits just one notice. Complete the list, coalesce its notices by native edge, and clear each reported edge’s absolute counters before repricing it at its exact value. Drain retirement notices under the old maps before the next query.
Each report accounts for weighted motion on its edge since the last reset. Equation (3) charges only per list before cancellation, so lists cause reports. A report takes time. The gap estimate gives , so steps separate consecutive full epoch scans. With (5), the total time after the vertex scan is .
Lengths, prices and gaps have polynomial magnitude. A returned list has polynomially many traversals, so are polynomially bounded, and every power of two in (3) has bits. The iterates share a dyadic grid of this precision. Rounded reciprocals and exact signed cost sums take polylog time per aggregate operation. The prefix work bound and the polynomial size of one further transaction justify a fixed polynomial history bound in Proposition 2.1.
Initialization and optimization. Shift initial lower bounds into the balances and constant cost. Reject inconsistent bounds or balances whose sum is nonzero. Otherwise adjoin a root. With net inflow positive, direct an artificial arc from the root to each vertex of positive balance and from each vertex of negative balance to the root. Give each arc capacity equal to the absolute balance and saturate it. Set the original flows to zero.
Let bound on the original arcs over the current stream budget. Assign every artificial arc cost . Any integral augmented flow of cost at most uses only original arcs. An original witness extends by zero. This proves the incremental threshold assertion, including its integral witness.
For static optimization test for feasibility, then binary-search the integer thresholds in . There are tests, each on an instance of polynomial numerical range and records. This proves the flow assertion of Theorem 1.1. For maximum - flow with nonnegative capacities, give the original arcs zero cost and a return arc cost and capacity . After deleting the return arc, take the vertices reachable from in the residual network. They exclude , since a residual path would increase the flow. Every outgoing arc of this shore is saturated and every entering arc has zero flow, giving a minimum cut.
Relaxing bounds and prices
Fix the balances and keep lower bounds nonnegative. Allow insertions at lower bound zero, capacity increases, lower-bound decreases, cost decreases and threshold increases. For polynomial-range integer data, the first feasible prefix and its witness take total time.
Split each native arc at a private zero-balance vertex . The gate has initial bounds and cost zero. From to place an arc of the current cost and capacity , an upper bound on all capacities. At an upper-bound increase add its increment to the gate by a parallel arc. At a lower-bound decrease add the decrement by a reverse gate arc. At a cost decrease append a fresh arc from to at the new cost.
Conservation at puts the net gate flow within the current bounds. All priced arcs cost at least the current unit price. Conversely, any such lifts with forward flow , reverse flow , and all on a cheapest arc. Thus projection preserves feasibility at the cost threshold. An increase of in the threshold is represented by a loop of capacity and cost , whose saturation subtracts exactly . Process the constant number of insertions for each update as a batch. A budget restart rebuilds the current gates and resets the test to the current threshold.
Optimal potentials and the whole optimal face. Let be an integral optimum of a feasible flow instance. Its directed residual graph has forward costs and reverse costs wherever the corresponding residual capacity is positive. A negative cycle would improve , so the shortest distances from a new zero-cost source joined to all vertices exist.
One more flow call recovers the distances. Give all residual and source arcs capacity , each old vertex demand one, and the source supply . One shortest path per vertex attains cost . Any feasible flow costs at least this much by summing its nonnegative reduced costs against its arc values. Hence every positive arc in an optimum of this auxiliary instance is tight. Any vertices unreachable from the source in the positive support would have positive total demand and no incoming flow. A search of that support finds a shortest-path tree and computes all by summing its arc costs.
Put on a native arc. Nonnegative residual reduced costs imply for every feasible . Since , the difference of objective values is the sum of these nonnegative terms. Thus the whole optimal face is specified by the original bounds and balances together with whenever . In particular certify optimality and the description is obtained in time.
Strong components under insertions
For a nonnegative circulation, every positive arc lies on a directed cycle. The following version allows a small amount of negative flow.
Lemma 5.1. Let be a signed circulation on a directed graph. If , then can reach .
Proof. Otherwise the vertices reachable from contain and exclude . No arc leaves this set. The signed sum of its entering flows is zero, so is at most their total negative part. □
Theorem 5.2. Strongly connected component labels can be maintained under arc insertions in total time, with constant-time membership tests after initialization and after each insertion.
Proof. Start with singleton blocks and a zero circulation on the quotient. Discard internal arcs and insert new arcs at zero. Following the contraction principle of Chen et al. [6 Section 8.3], merge the ends of an arc when its flow reaches .
Choose a power of two of polynomial size large enough to cover the ports counted below. Use from § 4.2 and the one-sided potential . The frozen length and price of a native arc are both . Queue each native arc whose exact reading reaches . Drain the queue before querying, checking that each queued arc is still live, has value at least $1/4, and has distinct ends.
A surviving anchor is below . The drift between reports and the raw motion in a step are together at most in that coordinate. Thus up to each contraction. A directed cycle has rounded price equal to its length on native edges. Each native length is at least , whereas port detours cost at most . The lifted cycle has ratio at least . Failure of the acceptance test therefore certifies an acyclic quotient.
On an accepted step Lemma 4.2 applies with , , . All arc terms are nonpositive, and for . A birth contributes , and deleting internal arcs only increases the potential. With an upper bound on births, it follows that
Consequently and the total negative part is less than for large . Lemma 5.1 now makes every queued contraction safe. Adding the two old balance equations cancels internal arcs and preserves conservation in the quotient. Inductively each block lies in a true strong component. A quotient path lifts to an original walk by joining successive representatives within their true component. Conversely, original paths project to quotient walks. Hence an acyclic quotient gives precisely the true partition.
At a merge, move the smaller block by number of vertices. Relabel its vertices, retire internal arcs and append a fresh port for each moved surviving end on the larger block’s path. Old ports stay unused, so all active ports of a block lie on one path. Test the threshold at each retargeted arc, preserving its exact signed value throughout the edits. Each vertex and arc end moves times, so ports suffice. The motion accounting of § 4.4 and one failed query per settled prefix give the asserted total time.
Unknown stream length. For both online algorithms, start with separate power-of-two bounds on the graph size and the largest input magnitude. Whenever an arrival exceeds either bound, raise the exceeded bounds to the least powers of two covering the prefix and rebuild on that prefix before answering. For flow use the artificial starting flow. For components retain the last published partition and initialize the current quotient with zero flow. The budgets stay for size and for magnitudes. The rebuilds preserve (1).
A sparse certificate at every prefix
The algorithm can maintain an insertion-only subgraph with the same strong components at every prefix. When there are components, this certificate contains at most native arcs. A bidirected tree requires both arcs of each edge, attaining the bound. The additional total work is .
Use the component merges at the end of each external update, after the quotient has been certified acyclic. If a new component has old components as children, its quotient on these children is strongly connected. Indeed, paths between vertices of a strong component stay inside it. From a largest child find an outward spanning arborescence and an inward spanning arborescence of the quotient. Add their at most native arc identifiers. The earlier certificate was strongly connected inside each child, so the new certificate is strongly connected inside the merged block. It remains a subgraph of the input. Summing over settled merges gives . If is the certificate at time and its final value, then . Thus the final certificate with the original arrival times recovers the strong components at every prefix.
To find the quotient, keep the previous published labels until the end of the update. Group the transient contractions by their final block and scan the original incidence lists of every child except the largest. This sees every interchild arc. Retain only arcs internal to the new block, then relabel the smaller children. Each scanned vertex joins a published component at least twice as large, and an arc scan is charged to its scanned endpoint. The grouping itself costs at most logarithmic work per contraction using the old labels and their union log. A size-budget restart may start with the preceding published partition and zero quotient flow, leaving the certificate intact. This partition is still a refinement of the true partition, which is all the contraction proof requires. The same construction processes the initial graph at time zero.
For first-prefix queries, give each vertex a leaf at time zero and each settled merge a node with its prefix as timestamp. Its children are the merged components. Join the remaining roots to a virtual root at time . The first common prefix is the timestamp of the lowest common ancestor. An Euler tour of this -node tree reduces that ancestor to a range minimum of depths between the leaves’ first visits. Precompute minima on all intervals of power-of-two length and tabulate integer logarithms. Two overlapping intervals then answer each query in constant time after time and space.
Cardinalities of degree-constrained subgraphs
A -factor is a set of edge records satisfying at every vertex. A loop contributes two to the degree. Tutte reduced prescribed degrees to perfect matching [15]. For intervals we use optional matching vertices to make the cardinality of a factor visible in the size of a matching.
Theorem 6.1. For an undirected multigraph with integral degree intervals, two maximum-matching computations on simple subcubic graphs of size find smallest and largest factors or certify infeasibility, in total time . A linear-size representation gives constant-time edge membership and -time reporting for a factor of each feasible size . A single prescribed size interval can instead be tested, with a witness, by one perfect-matching computation.
Encoding a degree interval. At a vertex of degree , intersect its interval with , rejecting an empty intersection. Check isolated vertices directly. Assign its incidences to the inputs of a Beneš permutation network padded to a power of two [3]. The network has positions and arcs, and indegree and outdegree at most two. It routes any equally sized sets of inputs and outputs by vertex-disjoint paths.
At size one use an arc. At size , the two inputs of each pair can enter either of two size- copies at the corresponding port. Reverse these connections at the outputs. Extend a prescribed bijection to a permutation. Its connections form a 2-regular bipartite multigraph on input and output pairs. Alternating colors on every circuit gives one permutation for each copy.
Split every position into a minus and a plus vertex joined by an idle edge. Each network arc joins its tail’s plus to its head’s minus. Each original edge joins its two input minus vertices, using separate ports even for a loop. At vertex , delete the first output plus vertices. Mark the next output plus vertices as optional. All remaining vertices must be covered.
Each covered internal position is idle or has one active arc in and one out. Acyclicity makes the active arcs disjoint paths from selected incidences to outputs. Deleted plus vertices force active outputs. Optional plus vertices are uncovered exactly at active outputs. All remaining outputs are idle. Conversely, the routing property extends every factor to such a matching by using idle edges off its paths. If , the total number of uncovered optional vertices is
Each split vertex has degree at most three. Distinct incidence ports keep the graph simple for parallel records as well as loops.
Two matching computations. Call the graph just constructed . Take two copies and join corresponding optional vertices by single edges. A perfect matching restricts on either copy to a matching covering all required vertices. Conversely, duplicate any such matching and join the uncovered pairs. Thus the first maximum-matching computation either certifies infeasibility or supplies a matching of that covers the required vertices.
For , attach a private leaf to every optional vertex of . Now require the old vertices to be covered and allow leaves to be free. Extend to a seed by matching its uncovered vertices to their leaves. Deleting the leaf edges gives the inverse on matchings covering the required vertices. The uncovered leaves correspond to inactive optional outputs. For a factor of size , their number is . Both graphs are simple and subcubic since optional outputs originally had just an idle edge.
Find a maximum matching on in the second computation. On either graph let be the restriction of the answer and its seed. Starting from , flip the paths of on which has one extra edge. Their ends are free in , so required vertices stay covered. There is no path with an extra -edge, since it would augment . The result has size . By (6) this minimizes the factor size on and maximizes it on .
All intermediate sizes. Let be the two extremal factors. Color blue and red. At each vertex pair opposite-colored incidences as far as possible. The pairs partition the difference into alternating trails and circuits. All unpaired ends at a vertex have the same color, even when the vertex occurs twice on a trail.
Flipping any collection therefore keeps each degree between its values in and . Each trail changes cardinality by or , and no trail can decrease it, by minimality of . There are exactly increasing trails. Flip these in any order, assigning the neutral trails and circuits to the last flip if the sizes differ. If the sizes agree, retain . Pairing and tracing take linear time, and each edge changes at most once.
Store the initial state and flip time by original record index. At size , the factor consists of the permanently selected edges, a prefix of the entering edges ordered by flip time, and a suffix of the departing edges in that order. The trail scan tabulates the two endpoints for all sizes in space. This proves the membership and reporting bounds.
One prescribed interval. For , the number of active optional outputs in must belong to by (6). Intersect it with , where is the number of optional outputs, and retain values of parity . Reject if none remain. Write the endpoints as . Connect each optional plus vertices to a separate input minus vertex of one more permutation network. Delete its first output plus vertices and pair the next by disjoint edges. Require a perfect matching throughout.
The new network receives precisely the active optional outputs. Its first outputs must be active, and both members of each output pair are active together. Conversely any allowed count routes to the first outputs and the appropriate number of pairs. With no optional vertices, test the count zero and use itself. The additional network is simple and subcubic and has records. Its logarithmic factor is absorbed by (1), completing the proof of Theorem 6.1.
Local rounding and integer cardinality slices
The same exchanges control the support of a convex combination. For an integer matrix , a move is a nonzero integral vector in its kernel. A summand is conformal to if and in every coordinate. A move is primitive if it has no other conformal move. These moves form the Graver basis [8], finite by Dickson’s lemma in each orthant. Successive subtraction expresses every move as a sum of conformal primitive moves. For an integral linear form , write
with empty maxima zero.
Theorem 6.2 (Local support and integer levels). Fix a finite integral box and an integral right-hand side, and let be the integer solutions of in the box. Each has a convex representation in which the values of coordinate span at most , and the values of span at most . Each bound is sharp for its matrix and statistic. Intersecting the integer hull with any integral level of commutes with taking the integer hull, for every box and right-hand side, exactly when .
Proof. Among representations of , minimize the average of . If for two support points has , take a conformal primitive summand using . Exchange equal positive masses at for masses at . Both new points lie between the old ones coordinatewise and have the same sum. The sum of the two squared norms decreases by
Thus the support fits in a box of the claimed widths. Within that box minimize the average of . If , some conformal summand has . The same exchange strictly decreases this second average and stays in the box.
For a primitive , the box between and with right-hand side has just these two solutions, by primitivity. Their midpoint needs both, proving sharpness. If , such a segment crosses an intermediate integer level without an integer solution there. If , the support uses only the floor and ceiling of its mean statistic, proving the assertion for levels and also for intervals with integral endpoints. □
Corollary 6.3 (Capacitated factors). Allow integral lower and upper bounds on every edge multiplicity and on every vertex degree. Let be the convex hull of the integral factors and put . For integers ,
The minimum of any linear cost over factors of size is a discrete convex function on their interval of feasible sizes.
Proof. Write the upper degree requirements as equations with one bounded slack at each vertex. For a move, pair opposite-colored incidences at each vertex as in § 6, now using one copy per unit of difference and a single incidence per slack copy. Every component of the pairing is a circuit or a trail ending at two slack copies, and gives a conformal move. A primitive move consists of just one component. Its ordinary edge copies alternate in color, so its size change is or . Theorem 6.2 gives the formula. For optimizers of sizes , their midpoint has size and decomposes into integral factors of size . Some such factor costs at most the mean of the two optima.
Theorem 6.4 (Sharp local rounding). Suppose each column of consists of at most two signed unit incidences, allowing both at the same row. In Theorem 6.2, each . If is integral for an integer , the same representation can satisfy
For fixed , , the radius is sharp over all such fibers and points. For capacitated factors, taking gives these coordinate bounds together with support sizes and .
Proof. Put . Consider prescribed degrees in a loopless graph with integral bounds . Put , and . For a shore and , define
Here a vector evaluated on a set denotes the sum of its entries. In addition to the bounds and degree equations, the capacitated matching polytope is defined by when is odd [11 Eq. (4)]. The identity gives . Hence a violated odd inequality has .
The case is immediate. For , intersect the box with on each edge. Every changed bound has slack strictly above even in the smaller box. In either box a violated inequality must therefore use unchanged crossing bounds. Its parity depends only on and those bounds, as internal edges count twice. Thus the two boxes have exactly the same violated odd inequalities at , with the same left sides. Hull membership gives a convex representation in the smaller box.
To pass from prescribed degrees to , translate each variable to . Replace a negative incidence by , absorbing the constant into the target. Equal contributions at two ends give one ordinary edge. Complementary contributions give a two-edge path with internal degree . A loop with two equal contributions is replaced by a three-edge path back to its vertex, with both internal degrees and values . All edges representing this column have bounds . For columns with one end, duplicate the rows and the two-ended edges, then join the two copies of the incident row by an edge carrying its required contribution. A zero column supplies an independent floor-or-ceiling mixture. Duplicating a solution gives a lift, while either copy projects to a native solution. The lifts preserve integrality after multiplication by and preserve absolute coordinate displacements.
The resulting representation is in the native box of radius . Apply Theorem 6.2 inside this box, with the same linear form . To see that , apply the radius bound at to the midpoint in the primitive two-point example from that theorem. A coordinate with uses only the floor and ceiling of , giving radius , and a coordinate with is fixed. For sharpness, take the same two-point example with weights and when . For factors apply the theorem to the degree equations with bounded slacks, using the size statistic of Corollary 6.3.
For undirected graphs even the nearest factor can be at distance . Join a center to one vertex of each of disjoint triangles by a spoke of capacity two. Triangle edges have capacity one. Prescribe degree two at the center and its neighbors and degree one at the other vertices. Each triangle uses its spoke zero or two times, so exactly one spoke is doubled. Averaging the choices gives spoke value and distance at least from every factor. For a directed flow, the primitive moves are signed simple cycles. Theorem 6.2 then gives floor-or-ceiling support and radius .
Removing the forest part
A spanning forest separates the part of an instance that requires a general graph algorithm. Both problems admit constant-size summaries on a tree piece with two attachment vertices. Linear-size static reductions for cardinality matching parameterized by the feedback edge number were given by Mertzios, Nichterlein and Niedermeier [13].
Theorem 7.1 (A common reduction). Let be the cycle rank of the current graph , where counts the components of its underlying undirected graph, including isolates. In time, maximum matching and directed bounded minimum-cost flow each reduce to an instance of the same problem with vertices and edges, or are solved outright. An optimum of the reduced instance lifts to an original optimum, with a fixed offset in the objective. The reduction applies to weighted matching and preserves unit weights in the unweighted case. Under edge insertions, deletions and label changes on a fixed vertex set, the reduction can be maintained in amortized polylogarithmic time per edit and extracted in time, to obtain the reduced instance and its decoding information. All labels have polynomial magnitude in the size bound.
Proof. Choose a spanning forest and mark the endpoints of its complementary edges. In each tree containing marks, prune unmarked leaves, then suppress unmarked vertices of degree two. The remaining unmarked vertices have degree at least three, so there are at most as many as marks. The resulting paths, with their pruned branches, have two attachment vertices. Branches at a retained vertex form one piece with a single attachment. A tree without marks contributes just its optimum or an infeasibility flag. Process the pruned branches toward their roots and then sweep each retained path. Each piece needs only a summary at its attachments, called its ports.
Matching. For each subset of available ports, keep the optimum after deleting the other ports. When two pieces meet, assign their shared vertex to at most one child and maximize the sum. For ports , subtract the empty-port value. Write for the gains when , , or both are available. Since , the triangle on with weights on , , realizes all four values. One port needs only a private leaf. For unit weights, each port increases the optimum by at most one. If both singleton gains vanish, use either no edge or , according to . A single positive gain needs a leaf at that port. Two positive gains need a common neighbor for and separate leaves for . Thus the reduced instance can itself be unweighted.
Flow. Impose balances on the interior of a tree piece. In a one-port piece, eliminating leaves fixes all edge flows, the contribution at the port and the cost. In a two-port piece, prescribe the net contribution at its first port. Leaf elimination again fixes every flow. Off the path between the ports it is constant, and on the path it has the form . All capacities therefore cut out one integral interval for . The second port receives a constant minus , and the cost is affine in . Absorb the constants in the balances and objective. An empty interval signals infeasibility. Otherwise one directed arc represents the interval and cost, shifting its lower bound if needed. At a shared port that becomes internal, the two child contributions sum to its balance. If the port survives, add their contributions. These joins use only unit pivots and interval intersections.
Each join above uses a constant-size summary of each child and saves the choices for decoding. Restoring the complementary edges completes the reduction. A reverse pass recovers a solution on the original records in time. Both algorithms take total time. For cardinality matching the overhead can be evaluated at the reduced size , since the reduced graph is unweighted.
For the dynamic assertion maintain a spanning forest and the list of complementary edges by dynamic connectivity [9], and store these summaries in balanced top trees [2]. A cluster has at most two ports and a forest edit changes clusters. A change to a vertex balance affects only ancestors of an arbitrary incident forest edge, or just the isolate record if there is no such edge. Maintain the sum of the finite optima and the count of infeasible whole trees. Keep loops outside the forest and bucket parallel edges by endpoint pair. If a deleted forest record has a surviving parallel copy, update its representative and summary. Flow loops stay among the complementary edges.
At extraction, mark one incident forest edge per nonisolated marked vertex. Open the root-to-leaf paths to these edges and keep their two ends. Every other exposed cluster meets the marked vertices it contains only at ports. This produces pieces. Their two-port paths form a forest. Fold its unmarked leaves and suppress its unmarked degree-two vertices with the same joins as above. Untouched tree values are read from the maintained totals after subtracting each touched tree once, including marked isolates. The resulting instance has the size asserted in the theorem.
Distances, spanners and cut trees
The metric rows of Table 1 use the routing constructions in [12]. Lengths and capacities are nonnegative integers of polynomial magnitude.
Directed distances under insertions. For a fixed source, the incremental shortest-path algorithm of [12], incremental SSSP, Theorem 1.1 and Section 10 gives -estimates in constant query time and reports a simple path of original edges in time. The total work is
for with for a sufficiently small absolute . Constant or inverse-polylogarithmic accuracy gives the table entry.
Undirected distances and spanners. For fully dynamic point queries on undirected graphs, total work gives stretch whenever and [12], APSP frontier, Theorem 2.1. To extend the positive-length tradeoff to zero lengths, maintain connectivity in the zero-edge subgraph [9] and run the oracle on lengths . A simple shortest path uses at most edges, so for a finite distance the transformed distance divided by lies in . Return zero for a zero-connected pair and otherwise divide the estimate by , preserving infinity. The added work is . Taking gives the balanced bounds in the table.
The two explicit spanners in [12], dynamic spanners, Parts I and II] support insertions and deletions on a fixed vertex set of arbitrary degrees. Recourse counts changes to their original edge sets. For the second spanner it depends only on the vertex and deletion counts.
Decremental forests and static cuts. For a bounded-degree undirected graph and fixed terminals, the forest of [12], decremental strong forest, Sections 11–14 gives -approximate paths to the terminals for constant or inverse-polylogarithmic . Representatives are fixed, paths project to walks, and total recourse is . Substitution into the Gomory–Hu construction of Abboud et al. [1] gives the cut-tree bound in [12], decremental strong forest, Section 16] for arbitrary degrees. Removing any lightest tree edge on the path between two vertices partitions the original vertices into the shores of a minimum cut for that pair.
Acknowledgment. The author used OpenAI models to formulate results, develop and review proofs, draft the manuscript, and implement finite checks. The source manuscripts [12] were prepared with GPT-6 Astra Pro.
References
- [1]A. Abboud, R. Kyng, J. Li, D. Panigrahi, M. Probst Gutenberg, T. Saranurak, Weixuan Yuan and Wuwei Yuan. Deterministic almost-linear-time Gomory–Hu trees. arXiv:2507.20354, 2025.arxiv.org/abs/2507.20354
- [2]S. Alstrup, J. Holm, K. de Lichtenberg and M. Thorup. Maintaining information in fully dynamic trees with top trees. ACM Transactions on Algorithms 1 (2005), 243–264.DOI
- [3]V. E. Beneš. Optimal rearrangeable multistage connecting networks. Bell System Technical Journal 43 (1964), 1641–1656.DOI
- [4]J. van den Brand, L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. Probst Gutenberg, S. Sachdeva and A. Sidford. A deterministic almost-linear-time algorithm for minimum-cost flow. FOCS (2023), 503–514.arxiv.org/abs/2309.16629
- [5]L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. Probst Gutenberg and S. Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. FOCS (2022), 612–623.
- [6]L. Chen, R. Kyng, Y. P. Liu, S. Meierhans and M. Probst Gutenberg. Almost-linear time algorithms for incremental graphs: cycle detection, SCCs, s-t shortest path, and minimum-cost flow. STOC (2024), 1165–1173.arxiv.org/abs/2311.18295
- [7]E. Cohen. Approximate max-flow on small depth networks. SIAM Journal on Computing 24 (1995), 579–597.
- [8]J. E. Graver. On the foundations of linear and integer linear programming I. Mathematical Programming 9 (1975), 207–226.DOI
- [9]J. Holm, K. de Lichtenberg and M. Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM 48 (2001), 723–760.
- [10]R. Kyng, S. Meierhans, M. Probst Gutenberg and A. Sulser. A simpler and faster min-cost flow solver via min-ratio cycles from distance oracles. arXiv:2609.23852, 2026.arxiv.org/abs/2609.23852
- [11]A. N. Letchford, G. Reinelt and D. O. Theis. Odd minimum cut sets and b-matchings revisited. SIAM Journal on Discrete Mathematics 22 (2008), 1480–1487.arxiv.org/abs/math/0607088
- [12]Yilin Liu and GPT-6 Astra Pro. Graph algorithms for matching and flow. Algorithm Frontier, source snapshot 77140c2 (2026).
- [13]G. B. Mertzios, A. Nichterlein and R. Niedermeier. The power of linear-time data reduction for maximum matching. Algorithmica 82 (2020), 3521–3565.
- [14]OpenAI. Almost-linear-time maximum-cardinality matching in general graphs. OpenAI Math Release, 2026.DOI
- [15]W. T. Tutte. A short proof of the factor theorem for finite graphs. Canadian Journal of Mathematics 6 (1954), 347–352.DOI