betaFeedback

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 H=n+m+2H = n + m + 2, both run in Hexp⁡O((log⁡H)4/5(log⁡log⁡H)1/5)H \exp O((\log H)^{4/5}(\log \log H)^{1/5}) 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 H=n+m+2H = n + m + 2 for a graph with nn vertices and mm 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

HE4=Hexp⁡(O((log⁡H)4/5(log⁡log⁡(H+4))1/5))=H1+o(1).(1)H E_4 = H \exp\left(O\left((\log H)^{4/5}(\log\log(H+4))^{1/5}\right)\right) = H^{1+o(1)}. \tag*{(1)}

Flow data are integers of magnitude HO(1)H^{O(1)}. 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.

ProblemTotal workOutput
Exact algorithms for matching, flow and strong components
General matchingHE4H\mathcal{E}_4Maximum set of disjoint original edges
Unit edges with degree boundsHE4H\mathcal{E}_4A factor of every feasible size, in one representation
Static min-cost flowHE4H\mathcal{E}_4Integral optimum and a description of the optimal face
Improving flow updatesHE4H\mathcal{E}_4First prefix meeting the cost threshold and an integral flow
Incremental strong componentsHE4H\mathcal{E}_4Exact labels and one certificate for all prefixes
Distance, spanner and cut algorithms from [12]
Incremental directed single-source distancesHE4H\mathcal{E}_4(1+ε)(1+\varepsilon)-approximate distances and simple paths
Fully dynamic distancesHE4H\mathcal{E}_4Point estimates of stretch E4\mathcal{E}_4 in polylogarithmic query time
Fully dynamic spannersHEjH\mathcal{E}_j, j=4,5j=4,5Stretch Ej\mathcal{E}_j, size nEjn\mathcal{E}_j, and HE4H\mathcal{E}_4 or (n+D)E5(n+D)\mathcal{E}_5 edge changes, respectively
Decremental strong forestHE6H\mathcal{E}_6Fixed representatives and approximate paths to the terminal set
Static Gomory–Hu treeHE6H\mathcal{E}_6All 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 H=n+m+2H=n+m+2. In a static graph mm counts input edges. For an update sequence it is the number of initial edges plus the number of updates. For spanners, DD counts deletions. With U=log⁡(H+4)U=\log(H+4) and h=log⁡(U+4)h=\log(U+4), write Ej=exp⁡O(Uj/(j+1)h1/(j+1))\mathcal{E}_j=\exp O(U^{j/(j+1)}h^{1/(j+1)}).

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 BB records head minus tail, with a zero column for each loop. Given prices γe∈Z\gamma_e\in\mathbb{Z} and lengths ℓe∈Z>0\ell_e\in\mathbb{Z}_{>0}, write

ρ=max⁡Bv=0,v≠0∣γTv∣∑eℓe∣ve∣\rho=\max_{\substack{Bv=0,\,v\ne0}}\frac{|\gamma^{\mathsf{T}}v|}{\sum_e \ell_e|v_e|}

taking ρ=0\rho= 0 for a trivial kernel. Orienting the support by the signs of vv 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 SS 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

E=exp⁡O((log⁡S)4/5(log⁡log⁡(S+4))1/5).E=\exp O\left((\log S)^{4/5}(\log\log(S+4))^{1/5}\right).

A query returns a list of signed edges and forest paths projecting to a circulation vv. Write aea_e for the number of traversals of edge ee in the list, and put V=∑eℓeaeV=\sum_e \ell_ea_e. If ρ>0\rho>0, then V>0V>0 and ∣γTv∣≥ρV/E|\gamma^T v|\geq\rho V/E.

Initialization costs O(E)O(E) per record. Updates and queries cost O(E)O(E) amortized, including path pieces and representation changes. Each native edge has at most EE 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 VV and the price without expanding the list. Out-and-back traversals count twice in VV.

The exponent. At one level of routing, replacing an edge ee on a cycle by a walk ReR_e leaves a local correction e−Ree-R_e. 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 U=⌈log⁡2S⌉U=\lceil\log_2 S\rceil and h=⌈log⁡2(U+4)⌉h=\lceil\log_2(U+4)\rceil. In [12 general matching, Eqs. (73)–(77)], set p=s=tp=s=t, repair depth t2t^2 and logarithmic shrinkage x=⌈U/t⌉x=\lceil U/t\rceil. The logarithmic local cost is O(U/t+t3h)O(U/t+t^3h), and each of O(t)O(t) levels contributes O(U/t2+t3h)O(U/t^2+t^3h) to log work and inverse quality. Hence

log⁡E=O(U/t+t4h),t=⌊(U/h)1/5⌋.\log E=O(U/t+t^4h),\qquad t=\lfloor(U/h)^{1/5}\rfloor.

This choice gives the asserted exponent. The child-record growth has logarithm O(U/t2+th)=o(x)O(U/t^2+th)=o(x) and stored labels use O(Ut)=o(x2)O(Ut)=o(x^2) bits. The cited construction fixes its cap 2cex2^{ce^x} 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 MM ports in all, the added length is at most 2M∑e∣ve∣2M\sum_e|v_e|. 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 dd by a path of 2d−12d-1 vertices, attaching its incident edges to distinct odd positions. Distinct ports separate parallel edges. For the resulting simple subcubic graph JJ,

ν(J)=ν(G)+A,A=∑v(deg⁡G(v)−1),\nu(J)=\nu(G)+A,\qquad A=\sum_v(\deg_G(v)-1),

where ν\nu denotes the maximum matching size. Construction and decoding take linear time.

Proof. A matching of GG 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 d−1d-1 internal edges.

Conversely, let XX be the external edges of a matching of JJ and let sv=deg⁡X(v)s_v=\deg_X(v). Every internal edge uses an even vertex and an unoccupied odd vertex. Hence its path supplies at most min⁡(d−1,d−sv)=d−1−(sv−1)+\min(d-1,d-s_v)=d-1-(s_v-1)_+ edges, where x+=max⁡(x,0)x_+=\max(x,0).

Each vertex incident to XX chooses one of its edges. Keep those chosen at both ends. This discards at most ∑v(sv−1)+\sum_v(s_v-1)_+ edges, one charge per rejection, and gives a matching of size at least the input matching size minus AA.

Proposition 3.2 (Matching phase [12], general matching, Sections 7, 8.6 and 12.2). On an NN-vertex subcubic graph, a phase with target K≥1K \ge1 either gains Ω(max⁡{1,K/log⁡(N+2)})\Omega(\max\{1,K/\log(N+2)\}) matching edges or certifies that the initial gap was less than KK. On a certificate the phase keeps its gains. With the valid caps of Proposition 2.1, the cost per phase is O((N+1)E4polylog⁡(N+2))O((N+1)E^4\operatorname{polylog}(N+2)).

The phase contracts factor-critical odd sets and prices circulations in an auxiliary allocation graph. If the initial gap was at least KK, after ii gains the symmetric difference with an optimum contains at least K−iK-i 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 K≤N/2K\le N/2 for N≥2N\ge2. Repeat until a certificate, then halve KK. Stop after the certificate at K=1K=1. Smaller graphs are immediate.

At entry to a scale the gap is less than 2K2K. The phase guarantee therefore gives O(log⁡(N+2))O(\log(N+2)) phases per scale. The last certificate gives gap zero. Since JJ has O(n+m)O(n+m) vertices and edges, Lemma 3.1 proves the matching assertion of Theorem 1.1.

Integral flow with a fixed potential

Fix balances bb, a cost threshold FF, and an integral starting flow within the bounds [0,ue][0,u_e]. New arcs enter at zero. We first solve this threshold problem, then construct the starting flow and optimize over FF.

A feasible direction

Let N≥1N\ge1 bound the total number of arcs, including auxiliary arcs. Take a power of two S≥16S\ge16 bounding nn, NN, all numerical data and ∣F∣|F|. Put Q=S8Q=S^8, δ=1/Q\delta=1/Q and A=4NA=4N. Extend the natural logarithm by its tangent at δ\delta,

ϕ(s)={log⁡s,s≥δ,log⁡δ+(s−δ)/δ,s<δ,w(s)=ϕ′(s)=1/max⁡{s,δ}.\phi(s)= \begin{cases} \log s, & s\ge\delta,\\ \log\delta+(s-\delta)/\delta, & s<\delta, \end{cases} \qquad w(s)=\phi'(s)=1/\max\{s,\delta\}.
Equation not extracted

For positive cost gap z=cTf−Fz=c^{\mathsf T}f-F, define

P(f)=∑e[ϕ(fe)+ϕ(ue−fe)]−Alog⁡z.(2)P(f)=\sum_e[\phi(f_e)+\phi(u_e-f_e)]-A\log z. \tag*{(2)}

At each prefix use the following rule.

  1. If z≤1/4z \le1/4, round to an integral witness (§ 4.3).

  1. Otherwise, query the priced graph. If the ratio test fails, this prefix has no flow of cost at most FF. Retain ff for the next insertion.

  1. On success, add the scaled circulation of Lemma 4.2 and repeat.

Each update preserves Bf=bBf = b.

Lemma 4.1 (Comparison). Write ℓe=w(fe)+w(ue−fe)\ell_e = w(f_e) + w(u_e - f_e) and βe=w(fe)−w(ue−fe)\beta_e = w(f_e) - w(u_e - f_e). If yy is feasible with cTy≤Fc^{\mathsf T}y \le F, then v=y−fv = y - f is a circulation and

∇P(f)Tv≥∑eℓe∣ve∣+A−2N.\nabla P(f)^{\mathsf T}v \ge\sum_e \ell_e|v_e| + A - 2N.

Proof. For ve≥0v_e \ge0, the difference ℓe∣ve∣−βeve\ell_e|v_e| - \beta_ev_e is 2w(ue−fe)ve≤22w(u_e - f_e)v_e \le2, since ve≤ue−fev_e \le u_e - f_e. For ve<0v_e < 0, the same bound follows from −ve≤fe-v_e \le f_e. The cost term contributes −AcTv/z≥A-Ac^{\mathsf T}v/z \ge A.

One step for both potentials

Take DD to be the least power of two at least max⁡(2,E)\max(2,E) and put η=1/(64D)\eta= 1/(64D). Each coordinate is read at an anchor f^e\widehat{f}_e. For each arc term ϕ(a+σfe)\phi(a+\sigma f_e), σ∈{−1,1}\sigma\in\{-1,1\}, evaluate w(a+σf^e)w(a+\sigma\widehat{f}_e) at that anchor. Denote the sum of these weights on ee by LeL_e and their signed sum by β^e\widehat{\beta}_e. Thus ∣β^e∣≤Le|\widehat{\beta}_e| \le L_e.

Freeze a price GeG_e at each edge. Give it integer price γe\gamma_e and length ℓe=⌈QLe⌉\ell_e = \lceil QL_e\rceil, with ∣γe/Q−Ge∣≤ηLe/32|\gamma_e/Q-G_e| \le\eta L_e/32. Give port connectors price zero and length one. Sign the returned list to make T=γTv≥0T = \gamma^{\mathsf T}v \ge0, where vv is its native projection. Recall its full traversal length VV from Proposition 2.1.

Lemma 4.2 (Gain per step). Suppose Le∣fe−f^e∣≤η/1024L_e|f_e-\widehat{f}_e| \le\eta/1024 for all ee. If V>0V > 0 and T≥4ηVT \ge4\eta V, choose a power of two μ\mu such that

η2/512≤t:=μT/Q≤η2/256.(3)\eta^2/512 \le t := \mu T/Q \le\eta^2/256. \tag*{(3)}

Set d=μvd = \mu v. Let RR be the remaining term of the potential after the arc terms. If RR lies above its tangent from ff to f+df+d and

∇R(f)=α(G−β^),∣α−1∣≤η/16,\nabla R(f) = \alpha(G-\widehat{\beta}), \qquad|\alpha-1| \le\eta/16,

then the full potential increases by at least t/2t/2.

Proof. The total weighted motion on the list is bounded by M=μV/Q≤t/(4η)≤η/1024M = \mu V/Q \le t/(4\eta) \le\eta/1024. In particular ∑eLe∣de∣≤M\sum_e L_e|d_e| \le M.

Along the step, each slack ss differs from its anchor s^\widehat{s} by at most 2η/(1024w(s^))2\eta/(1024w(\widehat{s})). The map s↦max⁡(s,δ)s \mapsto\max(s,\delta) is 1-Lipschitz, so ∣w(s)−w(s^)∣≤(η/32)w(s^)|w(s)-w(\widehat{s})| \le(\eta/32)w(\widehat{s}). Integration bounds the change in the arc terms below by β^Td−ηM/32\widehat{\beta}^{\mathsf T}d-\eta M/32.

Add the tangent inequality for RR. Price rounding gives ∣GTd−t∣≤ηM/32|G^{\mathsf T}d-t| \le\eta M/32, while ∣β^Td∣≤M|\widehat{\beta}^{\mathsf T}d| \le M. The total gain is at least αt−ηM≥t/2\alpha t-\eta M \ge t/2.

Prices for the threshold test. At the start of an epoch read all coordinates and store r=zr=z. Use G=β^−Ac/rG=\widehat{\beta}-Ac/r. Start a new epoch whenever ∣z/r−1∣>η/1024|z/r-1|>\eta/1024. Between epochs refresh an edge when its accumulated motion requires a new anchor. The global cost term has the exact identity

∇P(f)−(r/z)G=β−(r/z)β^.\nabla P(f)-(r/z)G=\beta-(r/z)\widehat{\beta}.

As in Lemma 4.2, each true scale is within a factor 1+O(η/1024)1+O(\eta/1024) of LeL_e, and the right-hand side has magnitude at most ηLe/32\eta L_e/32 at edge ee.

Round QGeQG_e to the nearest integer. One slack is at most ue/2u_e/2, so Le≥1/(S+1)L_e \ge1/(S+1). As 1/η=So(1)1/\eta= S^{o(1)}, the required price accuracy holds. At most 2N2N ports occur, and the connectors and length rounding together add O(S−6)Q∑eLe∣ve∣O(S^{-6})Q\sum_e L_e|v_e| to the length of a lifted circulation. Lemma 4.1 therefore gives a rounded ratio at least 1/21/2 whenever a feasible comparison exists. In that case the routing theorem guarantees T≥V/(2E)>4ηVT \ge V/(2E) > 4\eta V.

For an accepted list, ∣cTd∣/r=∣(β^−G)Td∣/A≤(M+t+ηM/32)/A|c^\mathsf{T}d|/r = |(\hat{\beta}-G)^\mathsf{T}d|/A \le(M+t+\eta M/32)/A. The new gap is at least half the old one. Convexity of −Alog⁡z-A\log z now supplies the tangent inequality, and Lemma 4.2 applies with α=r/z\alpha= r/z.

Stopping and rounding

Let ve(f)=(−fe)++(fe−ue)+v_e(f)=(-f_e)_+ +(f_e-u_e)_+ and viol⁡(f)=∑eve(f)\operatorname{viol}(f)=\sum_e v_e(f). Each pair of arc terms satisfies

ϕ(fe)+ϕ(ue−fe)≤2log⁡(1+ue)−ve(f)/(2δ).(4)\phi(f_e)+\phi(u_e-f_e)\le2\log(1+u_e)-v_e(f)/(2\delta). \tag*{(4)}

Inside the box this follows from ϕ(s)≤log⁡(1+s)\phi(s)\le\log(1+s) for s≥0s\ge0. At distance a>0a>0 outside the box the slacks are −a-a, ue+au_e+a. Their contributions are at most −a/δ-a/\delta and log⁡(1+ue)+a\log(1+u_e)+a.

At a feasible starting flow above the threshold, P≥−O(Nlog⁡S)P\ge-O(N\log S). A new zero-flow arc reduces PP by at most O(log⁡S)O(\log S), and changing anchors leaves PP unchanged. An integral start with z≤1/4z\le1/4 already meets the threshold. Otherwise the gap stays at least 1/81/8 through the last step. Summing Lemma 4.2 and (4) gives at every completed step

J=O(Nη−2log⁡S),viol⁡(f)=O(Nδlog⁡S),(5)J=O(N\eta^{-2}\log S),\qquad\operatorname{viol}(f)=O(N\delta\log S), \tag*{(5)}

where JJ counts accepted steps across all arrivals.

Lemma 4.3 (Euler rounding [7]). If Bx=bBx=b, bb is integral and 2kx2^k x is integral, one can round xx to an integral flow yy with the same balances in O(n+(k+1)m)O(n+(k+1)m) scalar operations. Each yey_e lies in Ie=[⌊xe⌋,⌈xe⌉]I_e=[\lfloor x_e\rfloor,\lceil x_e\rceil], and an affine objective specified by its coefficients on ∏eIe\prod_e I_e can be kept from increasing.

Proof. At digit j=k,…,1j=k,\ldots,1, keep the edges with odd numerator 2jxe2^j x_e. They have even degree at every vertex because 2jb2^j b is even. Orient an Euler tour in each component and let he=±1h_e=\pm1 record its direction, zero elsewhere. A loop forms a one-edge tour. Both x±2−jhx\pm2^{-j}h 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 z≤1/4z\le1/4, apply Lemma 4.3 with the objective

cTx+P0viol⁡(x),B0=∑e∣ce∣(ue+1),P0=B0+max⁡(F,0)+1.c^\mathsf{T}x+P_0\operatorname{viol}(x),\qquad B_0=\sum_e |c_e|(u_e+1),\qquad P_0=B_0+\max(F,0)+1.

It is affine on the rounding box because its breakpoints are integers. By (5), P0viol⁡(f)+1/4<1P_0\operatorname{viol}(f)+1/4<1 for large SS. The rounded objective is below F+1F+1, and each coordinate lies in [−1,ue+1][-1,u_e+1]. One unit of violation would already give objective at least P0−B0≥F+1P_0-B_0\ge F+1. The output is therefore feasible and its integral cost at most FF.

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 c>0c > 0, flag an edge if a copy accumulates cη/(ELe)c\eta/(EL_e) motion or the retirement counter reaches cη/Lec\eta/L_e. Round thresholds down to powers of two. At most EE live copies then give drift at most 2cη/Le2c\eta/L_e 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 Ω(η/E)\Omega(\eta/E) weighted motion on its edge since the last reset. Equation (3) charges only O(η)O(\eta) per list before cancellation, so JJ lists cause O(EJ)O(EJ) reports. A report takes O(EpolylogS)O(E\mathop{\rm polylog} S) time. The gap estimate gives ∣cTd∣/r=O(η/N)|c^{T}d|/r = O(\eta/N), so Ω(N)\Omega(N) steps separate consecutive full epoch scans. With (5), the total time after the vertex scan is O((N+1)E4polylogS)O((N+1)E^4\mathop{\rm polylog} S).

Lengths, prices and gaps have polynomial magnitude. A returned list has polynomially many traversals, so T,VT,V are polynomially bounded, and every power of two in (3) has O(log⁡S)O(\log S) bits. The iterates share a dyadic grid of this precision. Rounded reciprocals and exact signed cost sums take polylog SS 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 B∗B_* bound ∑e∣ce∣ue\sum_e |c_e|u_e on the original arcs over the current stream budget. Assign every artificial arc cost 2B∗+∣F∣+12B_* + |F| + 1. Any integral augmented flow of cost at most FF uses only original arcs. An original witness extends by zero. This proves the incremental threshold assertion, including its integral witness.

For static optimization test B∗B_* for feasibility, then binary-search the integer thresholds in [−B∗,B∗][-B_*,B_*]. There are O(log⁡S)O(\log S) tests, each on an instance of polynomial numerical range and O(n+m)O(n+m) records. This proves the flow assertion of Theorem 1.1. For maximum ss-tt flow with nonnegative capacities, give the original arcs zero cost and a return arc t→st \to s cost −1-1 and capacity ∑eue\sum_e u_e. After deleting the return arc, take the vertices reachable from ss in the residual network. They exclude tt, 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 HE4HE_4 total time.

Split each native arc e=uve = uv at a private zero-balance vertex aea_e. The gate u→aeu \to a_e has initial bounds [le0,ue0][l_e^0,u_e^0] and cost zero. From aea_e to vv place an arc of the current cost and capacity UU, 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 aea_e to vv at the new cost.

Conservation at aea_e puts the net gate flow xex_e within the current bounds. All priced arcs cost at least the current unit price. Conversely, any such xex_e lifts with forward flow max⁡(xe,le0)\max(x_e,l_e^0), reverse flow (le0−xe)+(l_e^0-x_e)_+, and all xex_e on a cheapest arc. Thus projection preserves feasibility at the cost threshold. An increase of Δ\Delta in the threshold is represented by a loop of capacity Δ\Delta and cost −1-1, whose saturation subtracts exactly Δ\Delta. 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 ff be an integral optimum of a feasible flow instance. Its directed residual graph has forward costs cec_e and reverse costs −ce-c_e wherever the corresponding residual capacity is positive. A negative cycle would improve ff, so the shortest distances pvp_v 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 nn, each old vertex demand one, and the source supply nn. One shortest path per vertex attains cost ∑vpv\sum_v p_v. 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 pvp_v by summing its arc costs.

Put cˉe=ce−(BTp)e\bar{c}_e=c_e-(B^Tp)_e on a native arc. Nonnegative residual reduced costs imply cˉe(ye−fe)≥0\bar{c}_e(y_e-f_e)\ge0 for every feasible yy. Since B(y−f)=0B(y-f)=0, 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 ye=fey_e=f_e whenever cˉe≠0\bar{c}_e\ne0. In particular f,pf,p certify optimality and the description is obtained in HE4HE_4 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 ff be a signed circulation on a directed graph. If fuv>∑e(−fe)+f_{uv}>\sum_e(-f_e)_+, then vv can reach uu.

Proof. Otherwise the vertices reachable from vv contain vv and exclude uu. No arc leaves this set. The signed sum of its entering flows is zero, so fuvf_{uv} is at most their total negative part. □

Theorem 5.2. Strongly connected component labels can be maintained under arc insertions in HE4HE_4 total time, with constant-time membership tests after initialization and after each insertion.

Proof. Start with singleton blocks and a zero circulation ff 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 1/41/4.

Choose a power of two SS of polynomial size large enough to cover the O(n+mlog⁡(n+2))O(n+m\log(n+2)) ports counted below. Use Q,δ,ηQ,\delta,\eta from § 4.2 and the one-sided potential Φ(f)=∑eϕ(fe)\Phi(f)=\sum_e\phi(f_e). The frozen length and price of a native arc are both ∣Qw(f^e)∣\lvert Qw(\hat{f}_e)\rvert. Queue each native arc whose exact reading reaches 1/41/4. 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 1/41/4. The drift between reports and the raw motion in a step are together at most 2ηmax⁡(f^e,δ)/10242\eta\max(\hat{f}_e,\delta)/1024 in that coordinate. Thus fe<1/2f_e<1/2 up to each contraction. A directed cycle has rounded price equal to its length on native edges. Each native length is at least 4Q4Q, whereas port detours cost at most 2S∑e∣ve∣2S\sum_e |v_e|. The lifted cycle has ratio at least 1/21/2. Failure of the acceptance test therefore certifies an acyclic quotient.

On an accepted step Lemma 4.2 applies with G=β^=w(f^)G=\hat{\beta}=w(\hat{f}), R=0R=0, α=1\alpha=1. All arc terms are nonpositive, and ϕ(s)≤−(−s)+/δ\phi(s)\leq-(-s)_+/\delta for s<1/2s<1/2. A birth contributes log⁡δ−1\log\delta-1, and deleting internal arcs only increases the potential. With mm an upper bound on births, it follows that

−m(1−log⁡δ)+Ω(Jη2)≤Φ(f)≤−δ−1∑e(−fe)+.-m(1-\log\delta)+\Omega(J\eta^2)\leq\Phi(f)\leq-\delta^{-1}\sum_e(-f_e)_+.

Consequently J=O(mη−2log⁡S)J=O(m\eta^{-2}\log S) and the total negative part is less than 1/41/4 for large SS. 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 O(log⁡(n+2))O(\log(n+2)) times, so O(n+mlog⁡(n+2))O(n+m\log(n+2)) 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 O(H)O(H) for size and HO(1)H^{O(1)} for magnitudes. The O(log⁡H)O(\log H) 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 cc components, this certificate contains at most 2(n−c)2(n-c) native arcs. A bidirected tree requires both arcs of each edge, attaining the bound. The additional total work is O((n+m)log⁡(n+2))O((n+m)\log(n+2)).

Use the component merges at the end of each external update, after the quotient has been certified acyclic. If a new component has r≥2r\geq2 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 2(r−1)2(r-1) 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 r−1r-1 over settled merges gives n−cn-c. If CtC_t is the certificate at time tt and C∗C_* its final value, then Ct⊆C∗∩Gt⊆GtC_t\subseteq C_*\cap G_t\subseteq G_t. 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 +∞+\infty. The first common prefix is the timestamp of the lowest common ancestor. An Euler tour of this O(n)O(n)-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 O(nlog⁡(n+2))O(n\log(n+2)) time and space.

Cardinalities of degree-constrained subgraphs

A (g,f)(g,f)-factor is a set XX of edge records satisfying gv≤deg⁡X(v)≤fvg_v \le\deg_X(v) \le f_v 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 O(n+mlog⁡(m+2))O(n+m\log(m+2)) find smallest and largest factors or certify infeasibility, in total time HE4H E_4. A linear-size representation gives constant-time edge membership and O(s+1)O(s+1)-time reporting for a factor of each feasible size ss. 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 d>0d>0, intersect its interval with [0,d][0,d], 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 O(dlog⁡(d+2))O(d\log(d+2)) 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 2k2k, the two inputs of each pair can enter either of two size-kk 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 vv, delete the first gvg_v output plus vertices. Mark the next fv−gvf_v-g_v 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 s=∣X∣s=|X|, the total number of uncovered optional vertices is

2s−∑vgv.(6)2s-\sum_v g_v. \tag*{(6)}

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 J−J_-. 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 M−M_- of J−J_- that covers the required vertices.

For J+J_+, attach a private leaf to every optional vertex of J−J_-. Now require the old vertices to be covered and allow leaves to be free. Extend M−M_- to a seed M+M_+ 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 ss, their number is ∑vfv−2s\sum_v f_v - 2s. Both graphs are simple and subcubic since optional outputs originally had just an idle edge.

Find a maximum matching on J−⊔J+J_- \mathbin{\sqcup} J_+ in the second computation. On either graph let QQ be the restriction of the answer and MM its seed. Starting from MM, flip the paths of M△QM \mathbin{\triangle} Q on which QQ has one extra edge. Their ends are free in MM, so required vertices stay covered. There is no path with an extra MM-edge, since it would augment QQ. The result has size ∣Q∣|Q|. By (6) this minimizes the factor size on J−J_- and maximizes it on J+J_+.

All intermediate sizes. Let X,YX,Y be the two extremal factors. Color X∖YX \setminus Y blue and Y∖XY \setminus X 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 XX and YY. Each trail changes cardinality by 00 or ±1\pm1, and no trail can decrease it, by minimality of XX. There are exactly ∣Y∣−∣X∣|Y|-|X| 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 XX. 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 ss, 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 O(m+1)O(m+1) space. This proves the membership and reporting bounds.

One prescribed interval. For a≤s≤ba \le s \le b, the number of active optional outputs in J−J_- must belong to [2a−∑vgv,2b−∑vgv][2a-\sum_v g_v,2b-\sum_v g_v] by (6). Intersect it with [0,p][0,p], where pp is the number of optional outputs, and retain values of parity ∑vgv\sum_v g_v. Reject if none remain. Write the endpoints as A,BA,B. Connect each optional plus vertices to a separate input minus vertex of one more permutation network. Delete its first AA output plus vertices and pair the next B−AB-A by disjoint edges. Require a perfect matching throughout.

The new network receives precisely the active optional outputs. Its first AA outputs must be active, and both members of each output pair are active together. Conversely any allowed count routes to the first AA outputs and the appropriate number of pairs. With no optional vertices, test the count zero and use J−J_- itself. The additional network is simple and subcubic and has O(mlog⁡(m+2))O(m\log(m+2)) 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 AA, a move is a nonzero integral vector in its kernel. A summand gg is conformal to hh if gihi≥0g_i h_i \ge0 and ∣gi∣≤∣hi∣|g_i| \le|h_i| 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 cc, write

Dc=max⁡g primitive∣cTg∣,Di=max⁡g primitive∣gi∣,D_c = \max_{g\ \mathrm{primitive}} |c^{\mathsf T}g|,\qquad D_i = \max_{g\ \mathrm{primitive}} |g_i|,

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 SS be the integer solutions of Ay=bAy=b in the box. Each x∈conv⁡Sx \in\operatorname{conv} S has a convex representation in which the values of coordinate ii span at most DiD_i, and the values of cTyc^{\mathsf T}y span at most DcD_c. Each bound is sharp for its matrix and statistic. Intersecting the integer hull with any integral level of cTyc^{\mathsf T}y commutes with taking the integer hull, for every box and right-hand side, exactly when Dc≤1D_c \le1.

Proof. Among representations of xx, minimize the average of ∥y∥2\|y\|^2. If h=z−yh=z-y for two support points has ∣hi∣>Di|h_i|>D_i, take a conformal primitive summand gg using ii. Exchange equal positive masses at y,zy,z for masses at y+g,z−gy+g,z-g. Both new points lie between the old ones coordinatewise and have the same sum. The sum of the two squared norms decreases by

2∑j∣gj∣(∣hj∣−∣gj∣)>0.2\sum_j |g_j|(|h_j|-|g_j|)>0.

Thus the support fits in a box of the claimed widths. Within that box minimize the average of (cTy)2(c^{\mathsf T}y)^2. If cTh>Dcc^{\mathsf T}h>D_c, some conformal summand has 0<cTg≤Dc0<c^{\mathsf T}g\le D_c. The same exchange strictly decreases this second average and stays in the box.

For a primitive g=g+−g−g=g^+-g^-, the box between g−g^- and g+g^+ with right-hand side Ag−Ag^- has just these two solutions, by primitivity. Their midpoint needs both, proving sharpness. If Dc>1D_c>1, such a segment crosses an intermediate integer level without an integer solution there. If Dc≤1D_c\le1, 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 PP be the convex hull of the integral factors and put s(y)=∑eyes(y)=\sum_e y_e. For integers a≤ba\le b,

P∩{a≤s(x)≤b}=conv⁡{y∈P∩Zm:a≤s(y)≤b}.P\cap\{a\le s(x)\le b\}=\operatorname{conv}\{y\in P\cap\mathbb{Z}^m:a\le s(y)\le b\}.

The minimum of any linear cost over factors of size kk 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 00 or ±1\pm1. Theorem 6.2 gives the formula. For optimizers of sizes k−1,k+1k-1,k+1, their midpoint has size kk and decomposes into integral factors of size kk. Some such factor costs at most the mean of the two optima.

Theorem 6.4 (Sharp local rounding). Suppose each column of AA consists of at most two signed unit incidences, allowing both at the same row. In Theorem 6.2, each Di≤2D_i \le2. If qxqx is integral for an integer q≥1q \ge1, the same representation can satisfy

∣yi−xi∣≤Di(1−1/q)in every coordinate.(7)|y_i-x_i| \le D_i(1-1/q) \qquad\text{in every coordinate.} \tag*{(7)}

For fixed AA, ii, qq the radius is sharp over all such fibers and points. For capacitated factors, taking c=sc=s gives these coordinate bounds together with support sizes ⌊s(x)⌋\lfloor s(x)\rfloor and ⌈s(x)⌉\lceil s(x)\rceil.

Proof. Put Rq=2−2/qR_q = 2-2/q. Consider prescribed degrees dd in a loopless graph with integral bounds [l,u][l,u]. Put v=x−lv=x-l, c=u−lc=u-l and d′=d−deg⁡(l)d'=d-\deg(l). For a shore WW and F⊆δWF \subseteq\delta W, define

L=v(δW∖F)+(c−v)(F),π=d′(W)+c(F).L = v(\delta W \setminus F) + (c-v)(F), \qquad\pi= d'(W) + c(F).

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 L≥1L \ge1 when π\pi is odd [11 Eq. (4)]. The identity v(δW)=d′(W)−2v(E(W))v(\delta W)=d'(W)-2v(E(W)) gives qL≡qπ(mod2)qL \equiv q\pi\pmod{2}. Hence a violated odd inequality has L≤1−2/qL \le1-2/q.

The case q=1q=1 is immediate. For q≥2q \ge2, intersect the box with [⌈xe−Rq⌉,⌊xe+Rq⌋][\lceil x_e-R_q\rceil,\lfloor x_e+R_q\rfloor] on each edge. Every changed bound has slack strictly above Rq−1=1−2/qR_q-1=1-2/q even in the smaller box. In either box a violated inequality must therefore use unchanged crossing bounds. Its parity depends only on d(W)d(W) and those bounds, as internal edges count twice. Thus the two boxes have exactly the same violated odd inequalities at xx, with the same left sides. Hull membership gives a convex representation in the smaller box.

To pass from prescribed degrees to AA, translate each variable to 0≤t≤ce0 \le t \le c_e. Replace a negative incidence −t-t by (ce−t)−ce(c_e-t)-c_e, 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 cec_e. A loop with two equal contributions is replaced by a three-edge path back to its vertex, with both internal degrees cec_e and values z,ce−z,zz,c_e-z,z. All edges representing this column have bounds [0,ce][0,c_e]. 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 qq and preserve absolute coordinate displacements.

The resulting representation is in the native box of radius RqR_q. Apply Theorem 6.2 inside this box, with the same linear form cc. To see that Di≤2D_i \le2, apply the radius bound at q=2q=2 to the midpoint in the primitive two-point example from that theorem. A coordinate with Di=1D_i=1 uses only the floor and ceiling of xix_i, giving radius 1−1/q1-1/q, and a coordinate with Di=0D_i=0 is fixed. For sharpness, take the same two-point example with weights 1/q1/q and 1−1/q1-1/q when q≥2q \ge2. For factors apply the theorem to the degree equations with bounded slacks, using the size statistic of Corollary 6.3. □\square

For undirected graphs even the nearest factor can be at distance 2−2/q2-2/q. Join a center to one vertex of each of qq 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 qq choices gives spoke value 2/q2/q and distance at least 2−2/q2-2/q 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 1−1/q1-1/q.

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 r=∣E(G)∣−n+cr = |E(G)| - n + c be the cycle rank of the current graph GG, where cc counts the components of its underlying undirected graph, including isolates. In O(n+m)O(n + m) time, maximum matching and directed bounded minimum-cost flow each reduce to an instance of the same problem with O(r+1)O(r + 1) 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 O((r+1)log⁡(n+2))O((r + 1)\log(n + 2)) 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 rr 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 a,ba, b, subtract the empty-port value. Write p,q,sp, q, s for the gains when aa, bb, or both are available. Since s≥max⁡(p,q)≥0s \ge\max(p, q) \ge0, the triangle on a,b,wa, b, w with weights p,q,sp, q, s on awaw, bwbw, abab 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 abab, according to ss. A single positive gain gg needs a leaf at that port. Two positive gains need a common neighbor for s=1s = 1 and separate leaves for s=2s = 2. 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 tt 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 de±td_e \pm t. All capacities therefore cut out one integral interval for tt. The second port receives a constant minus tt, and the cost is affine in tt. 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 O(n+m)O(n + m) time. Both algorithms take O(H)+(r+1)E4O(H) + (r + 1)\mathcal{E}_4 total time. For cardinality matching the overhead can be evaluated at the reduced size O(r+1)O(r + 1), 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 O(log⁡(n+2))O(\log(n + 2)) 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 O((r+1)log⁡(n+2))O((r + 1)\log(n + 2)) 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 (1+ε)(1 + \varepsilon)-estimates in constant query time and reports a simple path of kk original edges in O((k+1)polylog⁡H)O((k + 1)\operatorname{polylog} H) time. The total work is

Hexp⁡O(U4/5h1/5+U(h+log⁡(1/ε)))H\exp O\left(U^{4/5}h^{1/5} + \sqrt{U\left(h + \log(1/\varepsilon)\right)}\right)

for 0<ε≤1/20 < \varepsilon\le1/2 with log⁡(1/ε)≤cU\log(1/\varepsilon) \le cU for a sufficiently small absolute cc. Constant or inverse-polylogarithmic accuracy gives the table entry.

Undirected distances and spanners. For fully dynamic point queries on undirected graphs, total work Hexp⁡O(U/t+t3h)H\exp O(U/t + t^{3}h) gives stretch exp⁡O(t4h)\exp O(t^{4}h) whenever t→∞t \to\infty and t2h=o(U)t^{2}h = o(U) [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 nℓe+1n\ell_e + 1. A simple shortest path uses at most n−1n - 1 edges, so for a finite distance d≥1d \ge1 the transformed distance divided by nn lies in [d,d+(n−1)/n]⊆[d,2d][d, d + (n - 1)/n] \subseteq[d, 2d]. Return zero for a zero-connected pair and otherwise divide the estimate by nn, preserving infinity. The added work is Hpolylog⁡HH\operatorname{polylog} H. Taking t≍(U/h)1/5t \asymp(U/h)^{1/5} 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 (1+ε)(1 + \varepsilon)-approximate paths to the terminals for constant or inverse-polylogarithmic ε\varepsilon. Representatives are fixed, paths project to walks, and total recourse is Hε6H\varepsilon_6. 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. [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. [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. [3]V. E. Beneš. Optimal rearrangeable multistage connecting networks. Bell System Technical Journal 43 (1964), 1641–1656.DOI
  4. [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. [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. [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. [7]E. Cohen. Approximate max-flow on small depth networks. SIAM Journal on Computing 24 (1995), 579–597.
  8. [8]J. E. Graver. On the foundations of linear and integer linear programming I. Mathematical Programming 9 (1975), 207–226.DOI
  9. [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. [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. [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. [12]Yilin Liu and GPT-6 Astra Pro. Graph algorithms for matching and flow. Algorithm Frontier, source snapshot 77140c2 (2026).
  13. [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. [14]OpenAI. Almost-linear-time maximum-cardinality matching in general graphs. OpenAI Math Release, 2026.DOI
  15. [15]W. T. Tutte. A short proof of the factor theorem for finite graphs. Canadian Journal of Mathematics 6 (1954), 347–352.DOI

Paper details

vlnc:W_26yrbz39
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

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

  • Computer Science

OpenAI models, GPT-6 Astra Pro

View statement
Looking for related papers…
Contents