Introduction
In the random-order streaming model, the edges of a fixed graph arrive in a uniformly random permutation. We seek a large matching after one pass, using memory near-linear in the number of vertices. The input graph is otherwise arbitrary.
For maximum cardinality matching, Bernstein obtained a ( 2 / 3 − ε ) (2/3 - \varepsilon) ( 2/3 − ε ) -approximation in one pass using O ε ( n log 2 n ) O_{\varepsilon}(n \log^{2} n) O ε ( n log 2 n ) bits [5 ] . Assadi and Behnezhad subsequently crossed the 2 / 3 2/3 2/3 threshold, obtaining a ( 2 / 3 + ε 0 ) (2/3 + \varepsilon_{0}) ( 2/3 + ε 0 ) -approximation for an absolute constant ε 0 > 0 \varepsilon_{0} > 0 ε 0 > 0 , with an explicit improvement of approximately 10 − 14 10^{-14} 1 0 − 14 [2 ] . For maximum weight matching, Hashemi and Wrzos-Kaminska obtained a ( 2 / 3 − ε ) (2/3 - \varepsilon) ( 2/3 − ε ) -approximation [13 ] . All three guarantees hold for both bipartite and general graphs.
The weighted algorithm of Hashemi and Wrzos-Kaminska builds on Bernstein’s approach using an unfolding of integer weights. An original edge of weight w w w produces w w w unweighted edges between copies of its endpoints; we call the original edge the parent of each resulting copied edge. These copies arrive together as a batch when their parent arrives, so the resulting stream is not a uniformly random permutation of the copied edges.
Refolding a set of copied edges means returning to the original weighted subgraph formed by their parents. Even when the selected copies form a matching, their parents may share vertices. In a general graph, the refolded subgraph need not contain a matching whose weight is as large as the number of selected copies. Hashemi and Wrzos-Kaminska’s analysis handles both the correlations within arriving batches and this refolding difficulty while preserving the 2 / 3 − ε 2/3-\varepsilon 2/3 − ε guarantee [13 ] . Our improvement combines a stronger bipartite cardinality certificate with a historical transfer theorem that carries this certificate to weighted general graphs without reducing the approximation coefficient.
For any fixed ε > 0 \varepsilon> 0 ε > 0 , we obtain a 0.71295-approximation for unweighted matching and a ( 0.71295 − ε ) (0.71295-\varepsilon) ( 0.71295 − ε ) -approximation for weighted matching. Both guarantees hold for bipartite and general graphs.
Theorem 1.1 (Main result). Let n ≥ 2 n \ge2 n ≥ 2 , and let G G G be a simple graph on a known vertex universe of size at most n n n , whose edges arrive in a uniformly random order. For every 0 < δ < 1 0 < \delta< 1 0 < δ < 1 , put Λ = 1 + log ( n / δ ) \Lambda= 1 + \log(n/\delta) Λ = 1 + log ( n / δ ) . There is a deterministic one-pass algorithm that returns a matching of size at least 0.71295 ν ( G ) 0.71295\,\nu(G) 0.71295 ν ( G ) with probability at least 1 − δ 1-\delta 1 − δ over the arrival order, using O ( n Λ 6 ) O(n\Lambda^6) O ( n Λ 6 ) bits, where ν ( G ) \nu(G) ν ( G ) is the maximum matching size.
For every fixed 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 , a deterministic one-pass algorithm for positive rational edge weights returns a matching of weight at least
( 0.71295 − ε ) OPT w ( G ) (0.71295-\varepsilon)\operatorname{OPT}_{w}(G) ( 0.71295 − ε ) OPT w ( G ) with probability at least 1 − δ 1-\delta 1 − δ over the arrival order, where OPT w ( G ) \operatorname{OPT}_{w}(G) OPT w ( G ) is the maximum matching weight. It uses
O ε ( n Λ 6 ( B w t + Λ ) ) O_{\varepsilon}\bigl(n\Lambda^{6}(B_{\mathrm{wt}}+\Lambda)\bigr) O ε ( n Λ 6 ( B wt + Λ ) ) bits, where B w t B_{\mathrm{wt}} B wt bounds the binary length of each input numerator and denominator. Neither algorithm requires the stream length in advance; the weighted algorithm also does not require the weight range. Running time is polynomial in the encoded input size for fixed ε \varepsilon ε .
Table 1 summarizes the previous and new approximation guarantees in all four settings. All entries return a matching in one random-order pass. The previous unweighted bound uses O ( n log 2 n ) O(n\log^2 n) O ( n log 2 n ) bits when the stream length is known; geometric guesses remove that assumption at an additional logarithmic cost. In the same bit accounting, the previous weighted algorithm uses O ε ( n log n ( 1 + log R ) ( B w t + log n ) ) O_{\varepsilon}(n\log n(1+\log R)(B_{\mathrm{wt}}+\log n)) O ε ( n log n ( 1 + log R ) ( B wt + log n )) bits, where R R R is the ratio of the largest to the smallest edge weight. Our storage bound has no separate dependence on R R R ; it still charges the encoded precision of the weights. In particular, O ( log n ) O(\log n) O ( log n ) -bit weights and inverse-polynomial failure probability give O ε ( n log 7 n ) O_{\varepsilon}(n\log^7 n) O ε ( n log 7 n ) bits. The constants in our space bound are large.
Table 1. Approximation guarantees for one-pass matching in random-order streams. Previous guarantees are due to Assadi and Behnezhad [2 ] for unweighted matching and Hashemi and Wrzos-Kaminska [13 ] for weighted matching.
Assadi and Behnezhad showed that, even for unweighted bipartite graphs, achieving a ( 1 − η n ) (1-\eta_n) ( 1 − η n ) -approximation in one random-order pass requires n 1 + Ω ( 1 / log log n ) n^{1+\Omega(1/\log\log n)} n 1 + Ω ( 1/ l o g l o g n ) space for some η n = Θ ( 1 / log n ) \eta_n=\Theta(1/\log n) η n = Θ ( 1/ log n ) [2 ] . This leaves open how far constant-factor approximation can be improved in near-linear space. For adversarial edge order, Assadi, Jiang, and Xiang proved that no one-pass semi-streaming algorithm can achieve any constant approximation ratio greater than 1/2 with constant success probability, even for unweighted bipartite graphs [3 ] .
A transfer theorem for weighted general graphs. For a weighted graph K K K , define the deletion price of a vertex set X X X by
D K ( X ) = OPT w ( K ) − OPT w ( K − X ) . D_K(X) = \operatorname{OPT}_w(K) - \operatorname{OPT}_w(K-X). D K ( X ) = OPT w ( K ) − OPT w ( K − X ) .
This measures the loss in maximum matching weight caused by deleting X X X . Suppose K 0 ⊆ ⋯ ⊆ K m K_0 \subseteq\cdots\subseteq K_m K 0 ⊆ ⋯ ⊆ K m is an increasing sequence of graphs with fixed edge weights. Our structural theorem bounds the sum of deletion prices of pairwise disjoint vertex sets, even when each price is measured in a different graph in the sequence. Its proof uses a submodular potential defined by pairs of matchings with marked vertices. A weighted Tutte matrix supplies the submodularity.
Consider a phase that maintains a graph K K K and stores an arriving edge precisely when adding it increases the maximum matching weight. Immediately after each test, adding the tested edge cannot increase the optimum: a stored edge is already present, and a rejected edge did not improve it. Thus, for a tested edge u v uv uv and the graph K K K immediately after its test,
w ( u v ) ≤ D K ( { u , v } ) . w(uv) \le D_K(\{u,v\}). w ( uv ) ≤ D K ({ u , v }) .
This inequality need not remain valid as K K K grows, because an edge rejected earlier can become useful after later insertions. The historical theorem lets us bound the sum of deletion prices for disjoint vertex sets while evaluating each price at the relevant test time.
To apply the historical inequality to unfolded edges, we must handle matchings of copies whose original parents may share vertices. An auxiliary bipartite graph and integral matching duality resolve this difficulty. The resulting theorem transfers a cardinality certificate on copied graphs to a weighted matching guarantee in the original general graph, without reducing the approximation coefficient. The copied graphs cross a fixed cut used only in the proof. Thus one certificate suffices for all four settings in Table 1 . The transfer requires support whose parents are present at the start of a phase and selected copies whose parents are initially present or tested later. It is therefore not a reduction from an arbitrary unweighted streaming algorithm.
A stronger repair certificate. The algorithm first acquires a sparse reference graph in the unfolding and subsequently stores copies whose endpoint-degree sum in that reference is small. A bank of phases supplements this shared graph. To analyze one designated phase, fix a benchmark matching and a minimum vertex cover of the shared graph restricted to the analytic cut. If the shared graph has a small maximum matching, many benchmark edges have both endpoints outside the cover. Their endpoints have large combined reference degree, providing support for fractional matchings in the two vertex-deletion graphs of the transfer theorem. Benchmark edges that are available to the phase provide additional contributions.
The repair uses all vertices outside the cover. Their contributions to the two deletion matchings depend on their role in the benchmark matching. We record these roles and the reference degrees in a degree profile, including benchmark edges with both endpoints in the cover. After grouping vertices by degree interval, every graph arising in this analysis gives a feasible solution to a finite linear program. An exact rational dual certificate proves that the shared-graph and repair bounds cannot both be below 0.7129530279 . . . times the benchmark value. After accounting for concentration error and the acquisition prefix, the ratio remains above 0.71295.
Related techniques. Early improvements over greedy matching in random-order streams use augmentation and careful exposure of the stream [15 , 8 ] . Our reference construction belongs to the line of degree-constrained matching sparsifiers developed in [6 , 1 ] and used for random-order matching by Bernstein [5 ] . Graph unfolding originates with Kao, Lam, Sung, and Ting [14 ] ; its use for streaming matching was developed in [4 , 13 ] . We use standard separated weight bands and greedy combination to remove the weight range, while discarding only entire local instances [11 , 7 ] . The algebraic representation uses the weighted even-factor identity attributed to Cunningham and Geelen by Kobayashi and Takazawa [16 Theorem 4.2] ; our structural contribution is the deletion potential and its historical bound.
After the model and notation, section 3 presents the algorithm and proof overview. Sections 4 and 5 establish the historical transfer and the repair certificate. The appendices give the algebraic, probabilistic, and space details. The formal verification and AI methodology are described in section F.
Model and notation
All graphs are finite and simple. We write ν ( G ) \nu(G) ν ( G ) for maximum matching cardinality and OPT w ( G ) \operatorname{OPT}_{w}(G) OPT w ( G ) for maximum matching weight, or OPT ( G ) \operatorname{OPT}(G) OPT ( G ) when the weights are understood. A vertex deletion removes every edge incident to a deleted vertex. An algorithm returns an actual matching of input edges.
The random-order distribution is a uniform permutation of the original edges of a fixed input graph. A stream of batches is a uniform permutation of fixed, disjoint batches, each with at most κ \kappa κ edges; the order within each batch is fixed. Restriction to a fixed subset of original labels preserves uniform order. Edges belonging to one batch remain dependent throughout the analysis. The algorithms below are deterministic; their success probability is over the input permutation. Random cuts and repair choices are used only in the analysis.
Space is measured in bits. Original vertex identifiers use O ( log n ) O(\log n) O ( log n ) bits. For rational weights, B w t B_{\mathrm{wt}} B wt denotes the largest binary length of an input numerator or denominator; it need not be known in advance. Our bounds include these weight encodings, as well as the stored edges, indices, counters, and temporary matching workspace.
For integer weights in [ W ] [W] [ W ] , the canonical unfolding ϕ ( G ) \phi(G) ϕ ( G ) has copies v 1 , … , v W v_1,\ldots,v_W v 1 , … , v W of every original vertex. An original edge u v uv uv of weight w w w produces the w w w edges
u i v w + 1 − i ( 1 ≤ i ≤ w ) . u_i v_{w+1-i}\qquad(1 \le i \le w). u i v w + 1 − i ( 1 ≤ i ≤ w ) .
These edges arrive as one batch when their parent arrives. An original matching unfolds to a matching of cardinality equal to its weight. If G G G is bipartite, the reverse optimum equality also holds. We will only use this reverse implication on graphs crossing a specified cut. For general graphs we use the historical transfer theorem instead.
Lemma 2.1 (Bipartite refolding). For a bipartite graph A A A with integer weights in [ W ] [W] [ W ] , ν ( ϕ ( A ) ) = OPT w ( A ) \nu(\phi(A))=\operatorname{OPT}_{w}(A) ν ( ϕ ( A )) = OPT w ( A ) . Consequently every partial copied matching supported on originals crossing one fixed original-vertex cut has cardinality at most the maximum matching weight of those originals.
Proof. Unfolding an original optimum proves one direction. Integral weighted bipartite matching duality supplies nonnegative integer vertex prices p v p_v p v with p u + p v ≥ w u v p_u+p_v \ge w_{uv} p u + p v ≥ w uv and ∑ v p v = OPT w ( A ) \sum_v p_v=\operatorname{OPT}_{w}(A) ∑ v p v = OPT w ( A ) ; this is the standard assignment duality underlying the Hungarian method [17 ] . Take the bottom min { p v , W } \min\{p_v,W\} min { p v , W } copies of each vertex. If neither endpoint of a copied edge u i v w + 1 − i u_i v_{w+1-i} u i v w + 1 − i were selected, then i > p u i>p_u i > p u and w + 1 − i > p v w+1-i>p_v w + 1 − i > p v , implying w > p u + p v w>p_u+p_v w > p u + p v , a contradiction. Thus these vertices cover ϕ ( A ) \phi(A) ϕ ( A ) and their number is at most OPT w ( A ) \operatorname{OPT}_w(A) OPT w ( A ) . Every copied matching is bounded by this cover size. The final assertion follows by restricting to the given cut and then to the partial copied support.
An edge e e e is closed in K K K if OPT ( K + e ) = OPT ( K ) \operatorname{OPT}(K+e)=\operatorname{OPT}(K) OPT ( K + e ) = OPT ( K ) . Every edge already present in K K K is closed. For a cut ( L , R ) (L,R) ( L , R ) and a crossing matching T T T , let I L ( T ) I_L(T) I L ( T ) and I R ( T ) I_R(T) I R ( T ) denote its left and right endpoint sets. The same notation applies to copied matchings in the unfolded graph.
We use the exact constant
R ∗ = 2896371675910694789 4062500000000000000 , a ∗ = ( R ∗ − 10 − 7 ) ( 1 − 2 ⋅ 10 − 8 ) > 0.71295. R_*=\frac{2896371675910694789}{4062500000000000000},\qquad a_*=(R_*-10^{-7})(1-2\cdot10^{-8})>0.71295. R ∗ = 4062500000000000000 2896371675910694789 , a ∗ = ( R ∗ − 1 0 − 7 ) ( 1 − 2 ⋅ 1 0 − 8 ) > 0.71295.
The bounded-integer algorithm achieves a ∗ a_* a ∗ . The arbitrary-weight reduction spends a separately chosen ε \varepsilon ε allowance.
Algorithm and proof overview
We first work with integer weights in [ W ] [W] [ W ] . There are two kinds of stored graphs: a sparse shared graph in the unfolding, and a bank of phase graphs on the original vertices. The shared graph supplies a baseline matching. Each phase supplements the part of that graph available at its start by retaining later edges with positive insertion gain. All matching computations in the phases use the original weights.
Acquisition and the phase bank
Acquiring a reference. Process each original arrival as its fixed batch of unfolded copies. The acquisition procedure maintains a copied reference H H H : insert a copy u v uv uv if d H ( u ) + d H ( v ) < ( 1 − λ 0 ) β 0 d_H(u)+d_H(v)<(1-\lambda_0)\beta_0 d H ( u ) + d H ( v ) < ( 1 − λ 0 ) β 0 , and then delete edges whose endpoint-degree sum exceeds β 0 \beta_0 β 0 until the upper constraint is restored. A fixed tie rule makes these updates deterministic. Divide acquisition into epochs of original arrivals and freeze H H H at the end of the first epoch with no insertion. Subsequent degree tests use this frozen reference.
The reason for an empty epoch is statistical. If many remaining originals contained an underfull copy, a uniformly ordered epoch would be unlikely to avoid all of them. Meanwhile, a bounded potential limits the number of epochs containing an insertion. These two facts let us freeze after a short prefix and store the subsequent underfull copies within a prescribed cap, except on a charged failure event. Theorems D.1 and D.2 give the potential and the conditional sampling argument.
The state after freezing. Write e 1 , … , e m e_1,\ldots,e_m e 1 , … , e m for the remaining original edges. Let U ≤ i U_{\le i} U ≤ i be the copied edges among their first i i i batches that are underfull with respect to H H H , and let par ( D ) \operatorname{par}(D) par ( D ) denote the original parents of a copied edge set D D D . The phase-bank procedure is as follows.
On arrival e i e_i e i , add its underfull copies to U ≤ i U_{\le i} U ≤ i and retain their original parent and timestamp. If this would exceed the prescribed cap, abort this local instance.
For every phase already started at a cutoff c < i c<i c < i , update its current original graph by
K c ← { K c + e i , OPT w ( K c + e i ) > OPT w ( K c ) , K c , otherwise . K_c\leftarrow
\begin{cases}
K_c+e_i, & \operatorname{OPT}_w(K_c+e_i)>\operatorname{OPT}_w(K_c),\\
K_c, & \text{otherwise}.
\end{cases} K c ← { K c + e i , K c , OPT w ( K c + e i ) > OPT w ( K c ) , otherwise .
If i i i is a scheduled cutoff, start a new phase with K i = par ( H ∪ U ≤ i ) K_i=\operatorname{par}(H\cup U_{\le i}) K i = par ( H ∪ U ≤ i ) .
At the end of a nonaborted execution, return a maximum-weight matching in the union of the full shared parent graph par ( H ∪ U ≤ m ) \operatorname{par}(H \cup U_{\le m}) par ( H ∪ U ≤ m ) and all final phase graphs.
Thus a later underfull edge is saved in the shared graph, while an existing phase applies the same insertion test to it as to every other arrival. A phase’s initial support contains only records available at its cutoff. This distinction matters in the transfer argument below.
Every tested edge is closed in its post-test host: an accepted edge is present, and a rejected edge has zero insertion gain. The host only grows, but an edge’s closure need not persist as it grows. We will use closure at the edge’s own test time. Each accepted edge raises the integral optimum by at least one, and that optimum is at most W ⌊ n / 2 ⌋ W\lfloor n/2\rfloor W ⌊ n /2 ⌋ . Hence a phase adds at most this many original edges beyond its initialization. Exact matching calls are performed on the retained host; their running time and bit workspace are accounted for in section D.
Phase starts follow a geometric grid of reached suffix positions. The complete algorithm also runs acquisition instances for dyadic guesses of the input length, all from the beginning of the stream. At the end it uses the scale containing the actual length. Exact buffers handle short inputs and short suffixes; a fallback matching handles aborted instances. These rules make the procedure causal even when the length is unknown, and hard caps bound its space on every execution. Only one acquisition instance and one of its phases are needed for the approximation proof.
From a copied certificate to the returned matching
Fix an optimum original matching before exposing the stream. After acquisition, retain its suffix edges as the benchmark M M M , and put μ = w ( M ) \mu= w(M) μ = w ( M ) . Its unfolded matching M = ϕ ( M ) \mathcal{M} = \phi(M) M = ϕ ( M ) has exactly μ \mu μ edges. The prefix analysis will show that μ \mu μ is close to the input optimum.
An original-vertex cut used only for analysis. Choose a cut separating the endpoints of every edge of M M M , and assign all copies of an original vertex to its side. Independent orientations of benchmark pairs, together with independent sides for unmatched vertices, show that such a cut can also approximately halve every reference degree. We fix one balanced cut after fixing the unordered suffix and the acquisition history. The existence argument uses the large reference-degree scale; the algorithm never computes the cut.
Let H ′ H' H ′ , U ′ U' U ′ be the crossing parts of the full shared copied graphs, and put B = H ′ ∪ U ′ B = H' \cup U' B = H ′ ∪ U ′ and b = ν ( B ) b = \nu(B) b = ν ( B ) . The balanced cut preserves the reference upper-degree bounds and the lower-degree bounds on non-underfull benchmark copies, after rescaling the threshold. It also preserves every edge of M \mathcal{M} M . Thus the benchmark loses no weight at this step. Bipartite refolding (theorem 2.1) gives a matching of weight at least b b b among the retained original parents. If V V V denotes the returned value, then V ≥ b V \ge b V ≥ b on a nonaborted execution.
The certificate supplied by one phase. For a designated cutoff c c c , let A 0 A_0 A 0 be a copied graph across the analytic cut whose parents belong to the phase’s initial host. Let J J J be a copied matching across the same cut whose parents are either initially present or tested after c c c . The historical copied transfer of theorem 4.4 gives
ν ( A 0 − I L ( J ) ) + ν ( A 0 − I R ( J ) ) + ∣ J ∣ 2 ≤ OPT w ( K c f i n a l ) ≤ V . (1) \frac{\nu(A_0-I_L(J))+\nu(A_0-I_R(J))+|J|}{2} \le\operatorname{OPT}_w(K_c^{\mathrm{final}}) \le V. \tag*{(1)} 2 ν ( A 0 − I L ( J )) + ν ( A 0 − I R ( J )) + ∣ J ∣ ≤ OPT w ( K c final ) ≤ V . (1)
The ordinary support A 0 A_0 A 0 must be present from the start. The selected edges J J J need only have a closure time along the phase. In particular, an available benchmark parent arriving by cutoff c c c is initially present, and one arriving after c c c is tested. Either case is valid, even if that later test rejects it. Several selected copies can share the same original parent and its closure time.
The two terms in (1) measure how much support survives deleting the selected left endpoints and deleting the selected right endpoints. Their average, together with ∣ J ∣ / 2 |J|/2 ∣ J ∣/2 , is a lower bound on an original weighted optimum. This is the step that lets us analyze bipartite copied graphs while the algorithm runs on a general graph.
To lower-bound the deletion terms, take a minimum vertex cover C C C of B B B . If b b b is already large, the shared base suffices. Otherwise many benchmark edges have both endpoints outside C C C . Reference incidences at these endpoints provide fractional matching support after deletion. Available benchmark edges and other outside vertices provide further contributions. Section 5 constructs the two fractional matchings and records which contributions can coexist. Its finite degree-profile certificate bounds the better of the base and repair values for every feasible profile.
Using random order
Condition on a concrete ordered acquisition history ending at the freeze. The remaining original labels are uniformly ordered. This conditioning fixes the reference, the unordered underfull graph, the benchmark and the analytic cut. It includes no condition on future cap survival or on the success of a phase.
Represent this suffix order by independent uniform clocks on the original labels. Every copy inherits its parent’s clock. The repair uses two fixed thresholds α < ω \alpha< \omega α < ω , specified in section 5: early labels have clock at most α \alpha α , and late labels have clock greater than ω \omega ω . It defines A 0 A_0 A 0 from the reference and early available benchmark gates described in section 5, and selects J J J from benchmark copies according to their availability and clock. For every clock outcome z z z , define
Q ( z ) = max { b , ν ( A 0 ( z ) − I L ( J ( z ) ) ) + ν ( A 0 ( z ) − I R ( J ( z ) ) ) + ∣ J ( z ) ∣ 2 } . Q(z) = \max\left\{b,\frac{\nu(A_0(z)-I_L(J(z)))+\nu(A_0(z)-I_R(J(z)))+|J(z)|}{2}\right\}. Q ( z ) = max { b , 2 ν ( A 0 ( z ) − I L ( J ( z ))) + ν ( A 0 ( z ) − I R ( J ( z ))) + ∣ J ( z ) ∣ } .
The repair concentration argument applies to this analytic quantity under the original product distribution of clocks.
It remains to compare Q Q Q with an actual phase. On the long-suffix branch, let m m m be the final suffix length and designate the grid cutoff just below ( α + ω ) m / 2 (\alpha+\omega)m/2 ( α + ω ) m /2 . The grid is sufficiently fine that, except on a small binomial-tail event, every early label precedes this cutoff and every late label follows it. On this cutoff bracket , provided the local instance has not aborted, all parents of A 0 A_0 A 0 are present initially, and every parent selected in J J J is initial or subsequently tested. (1) and the full-base bound then give V ≥ Q V \ge Q V ≥ Q . Choosing the designated cutoff for analysis does not require knowing m m m during the stream: that phase was launched when its position was reached.
We therefore bound repair failure without conditioning on the bracket, and add the bracket failure probability separately. No independence between these events is needed. Integrating over freeze histories, and adding the underfull-cap and prefix-loss probabilities, gives the bounded-integer coefficient ( R ∗ − 10 − 7 ) ( 1 − 2 ⋅ 10 − 8 ) > 0.71295 (R_* - 10^{-7})(1 - 2\cdot10^{-8}) > 0.71295 ( R ∗ − 1 0 − 7 ) ( 1 − 2 ⋅ 1 0 − 8 ) > 0.71295 . The exact schedule, error allocations and bit bounds appear in section D. Finally, the weight-range reduction in section E runs this algorithm on normalized weight windows and combines their output matchings, spending only the separately chosen ε \varepsilon ε allowance. Each surviving window retains its complete filtered history. The probability bound is taken over complete executions on fixed windows before restricting to the survivors.
Historical deletion bounds
Closure can disappear as the host grows. For example, an edge b c bc b c of weight 2 is closed in the graph consisting of a b ab ab of weight 2. After inserting a d ad a d of weight 3, adding b c bc b c raises the optimum from 3 to 5. We account for each edge at the time when it is closed.
For a set of marked vertices M M M , call a pair of matchings ( N 1 , N 2 ) (N_1,N_2) ( N 1 , N 2 ) admissible if N 1 N_1 N 1 avoids M M M and each component of N 1 △ N 2 N_1\mathbin{\triangle}N_2 N 1 △ N 2 contains at most one marked vertex. Define
F K ( M ) = max { w ( N 1 ) + w ( N 2 ) : ( N 1 , N 2 ) is admissible in K } . F_K(M)=\max\{w(N_1)+w(N_2):(N_1,N_2)\text{ is admissible in }K\}. F K ( M ) = max { w ( N 1 ) + w ( N 2 ) : ( N 1 , N 2 ) is admissible in K } .
Common edges are counted twice. The component condition concerns the two matchings, not the ambient graph, so an admissible pair remains admissible when the host grows. Marks identify the vertices whose deletion prices we still need to charge.
Lemma 4.1 (Marked-pair submodularity). For every graph with nonnegative weights, F K F_K F K is submodular:
F K ( S ∪ T ) + F K ( S ∩ T ) ≤ F K ( S ) + F K ( T ) . F_K(S\cup T)+F_K(S\cap T)\le F_K(S)+F_K(T). F K ( S ∪ T ) + F K ( S ∩ T ) ≤ F K ( S ) + F K ( T ) .
The proof represents F K ( M ) F_K(M) F K ( M ) by weighted Tutte minors whose columns avoid M M M . Determinant exchange gives submodularity; the matching interpretation and the full algebraic proof are in section A.
Three properties now suffice:
F K ( ∅ ) = 2 OPT ( K ) , (2) F_K(\varnothing)=2\operatorname{OPT}(K), \tag*{(2)} F K ( ∅ ) = 2 OPT ( K ) , (2)
K ⊆ H ⟹ F K ( M ) ≤ F H ( M ) , (3) K\subseteq H\quad\Longrightarrow\quad F_K(M)\le F_H(M), \tag*{(3)} K ⊆ H ⟹ F K ( M ) ≤ F H ( M ) , (3)
F K ( M ∖ X ) − F K ( M ) ≥ D K ( X ) ( X ⊆ M ) . (4) F_K(M\setminus X)-F_K(M)\ge D_K(X)\quad(X\subseteq M). \tag*{(4)} F K ( M ∖ X ) − F K ( M ) ≥ D K ( X ) ( X ⊆ M ) . (4)
The first two follow directly from the definition. For the third, submodularity gives F K ( M ∖ X ) − F K ( M ) ≥ F K ( ∅ ) − F K ( X ) F_K(M\setminus X)-F_K(M)\ge F_K(\varnothing)-F_K(X) F K ( M ∖ X ) − F K ( M ) ≥ F K ( ∅ ) − F K ( X ) . Since the first matching avoids X X X , F K ( X ) ≤ OPT ( K − X ) + OPT ( K ) F_K(X)\le\operatorname{OPT}(K-X)+\operatorname{OPT}(K) F K ( X ) ≤ OPT ( K − X ) + OPT ( K ) , proving (4). Thus releasing marks pays their deletion price, while host growth supplies nonnegative additional slack.
Theorem 4.2 (Historical deletion inequality). Let K 0 ⊆ ⋯ ⊆ K m K_0\subseteq\cdots\subseteq K_m K 0 ⊆ ⋯ ⊆ K m have fixed nonnegative edge weights. Let X 1 , … , X k X_1,\ldots,X_k X 1 , … , X k be pairwise disjoint vertex sets, with observation times t i ∈ { 0 , … , m } t_i\in\{0,\ldots,m\} t i ∈ { 0 , … , m } , and put M = ⋃ i X i M=\bigcup_i X_i M = ⋃ i X i . Then
∑ i D K t i ( X i ) ≤ 2 OPT ( K m ) − F K 0 ( M ) . \sum_i D_{K_{t_i}}(X_i)\le2\operatorname{OPT}(K_m)-F_{K_0}(M). i ∑ D K t i ( X i ) ≤ 2 OPT ( K m ) − F K 0 ( M ) .
Proof. Order the sets by observation time. Start with all vertices in M M M marked. Move the host to the next observation time and release that set of marks. Host growth cannot decrease the potential, by (3); releasing X i X_i X i increases it by at least D K t i ( X i ) D_{K_{t_i}}(X_i) D K t i ( X i ) , by (4). After all releases, advance the host to K m K_m K m . No marks remain, so the final potential is 2 OPT ( K m ) 2\operatorname{OPT}(K_m) 2 OPT ( K m ) . Summing proves the claim. Equal observation times and observations in K 0 K_0 K 0 are allowed. □ \square □
Corollary 4.3 (Historical cut transfer). Let the hosts be as in theorem 4.2. Fix a cut ( L , R ) (L,R) ( L , R ) , a crossing graph A ⊆ K 0 A\subseteq K_0 A ⊆ K 0 , and a crossing matching T T T . If each e ∈ T e\in T e ∈ T is closed in some K t e K_{t_e} K t e , then
OPT ( A − I L ( T ) ) + OPT ( A − I R ( T ) ) + w ( T ) ≤ 2 OPT ( K m ) . \operatorname{OPT}(A-I_L(T))+\operatorname{OPT}(A-I_R(T))+w(T)\le2\operatorname{OPT}(K_m). OPT ( A − I L ( T )) + OPT ( A − I R ( T )) + w ( T ) ≤ 2 OPT ( K m ) .
The two deletion optima give an admissible pair: their alternating components can be oriented so that the first matching avoids every endpoint of T T T . Closure of u v uv uv gives w u v ≤ D K t u v ( { u , v } ) w_{uv}\le D_{K_{t_{uv}}}(\{u,v\}) w uv ≤ D K t uv ({ u , v }) , so theorem 4.2 applies. The parity argument is given in section A.1.
Theorem 4.4 (Historical copied transfer). Assume fixed integer weights in [ W ] [W] [ W ] and hosts K 0 ⊆ ⋯ ⊆ K m K_0\subseteq\cdots\subseteq K_m K 0 ⊆ ⋯ ⊆ K m . Fix a cut ( L , R ) (L,R) ( L , R ) , a crossing original graph A ⊆ K 0 A\subseteq K_0 A ⊆ K 0 , and an arbitrary crossing proposal
graph P P P . Suppose every e ∈ P e \in P e ∈ P is closed in some historical host K t e K_{t_e} K t e . For any partial copied supports B 1 , B 2 ⊆ ϕ ( A ) B_1,B_2 \subseteq\phi(A) B 1 , B 2 ⊆ ϕ ( A ) and any matching J ⊆ ϕ ( P ) J \subseteq\phi(P) J ⊆ ϕ ( P ) ,
ν ( B 1 − I L ( J ) ) + ν ( B 2 − I R ( J ) ) + ∣ J ∣ ≤ 2 OPT ( K m ) . \nu(B_1-I_L(J))+\nu(B_2-I_R(J))+|J|\leq2\operatorname{OPT}(K_m). ν ( B 1 − I L ( J )) + ν ( B 2 − I R ( J )) + ∣ J ∣ ≤ 2 OPT ( K m ) .
The original parents of J J J need not form a matching.
The key is to cover all proposal edges with one pair of price vectors. This separates the disjointness needed for historical charging from the weaker copied-matching condition in the conclusion.
Proof. Use two layers L 1 ∪ R 1 L^1\cup R^1 L 1 ∪ R 1 and L 2 ∪ R 2 L^2\cup R^2 L 2 ∪ R 2 , each carrying a copy of A A A . Add the mixed edge u 1 v 2 u^1v^2 u 1 v 2 of weight w u v w_{uv} w uv for every proposal u v ∈ P uv\in P uv ∈ P , oriented with u ∈ L u\in L u ∈ L and v ∈ R v\in R v ∈ R . The resulting graph is bipartite with parts L 1 ∪ L 2 L^1\cup L^2 L 1 ∪ L 2 and R 1 ∪ R 2 R^1\cup R^2 R 1 ∪ R 2 .
An auxiliary matching splits into ordinary matchings M 1 , M 2 M_1,M_2 M 1 , M 2 in the two layers and mixed edges whose original parents form a matching T ⊂ P T\subset P T ⊂ P . Moreover, M 1 M_1 M 1 avoids I L ( T ) I_L(T) I L ( T ) and M 2 M_2 M 2 avoids I R ( T ) I_R(T) I R ( T ) . Consequently, theorem 4.3 bounds the weight of every auxiliary matching by 2 OPT ( K m ) 2\operatorname{OPT}(K_m) 2 OPT ( K m ) . Integral bipartite duality gives nonnegative integer vertex prices p 1 , p 2 p^1,p^2 p 1 , p 2 of total cost at most 2 OPT ( K m ) 2\operatorname{OPT}(K_m) 2 OPT ( K m ) such that
p u j + p v j ≥ w u v ( u v ∈ A , j = 1 , 2 ) , p u 1 + p v 2 ≥ w u v ( u v ∈ P ) . p^j_u+p^j_v\geq w_{uv}\quad(uv\in A,\ j=1,2),\qquad p^1_u+p^2_v\geq w_{uv}\quad(uv\in P). p u j + p v j ≥ w uv ( uv ∈ A , j = 1 , 2 ) , p u 1 + p v 2 ≥ w uv ( uv ∈ P ) .
This single pair of price vectors covers all of P P P , even when its edges have common original endpoints.
In copied layer j j j , let C j C_j C j contain the bottom min { p v j , W } \min\{p^j_v,W\} min { p v j , W } copies of every vertex v v v . As in theorem 2.1, C j C_j C j covers ϕ ( A ) \phi(A) ϕ ( A ) and hence B j B_j B j . The mixed constraint also covers every selected proposal copy u i v w u v + 1 − i ∈ J u_i v_{w_{uv}+1-i}\in J u i v w uv + 1 − i ∈ J by its left endpoint in C 1 C_1 C 1 or its right endpoint in C 2 C_2 C 2 . Otherwise the integer indices would give w u v > p u 1 + p v 2 w_{uv}>p^1_u+p^2_v w uv > p u 1 + p v 2 .
Since J J J is a copied matching, distinct edges use distinct left endpoints and distinct right endpoints. It follows that
∣ C 1 ∩ I L ( J ) ∣ + ∣ C 2 ∩ I R ( J ) ∣ ≥ ∣ J ∣ . |C_1\cap I_L(J)|+|C_2\cap I_R(J)|\geq|J|. ∣ C 1 ∩ I L ( J ) ∣ + ∣ C 2 ∩ I R ( J ) ∣ ≥ ∣ J ∣.
Deleting these vertices from the two covers gives
ν ( B 1 − I L ( J ) ) + ν ( B 2 − I R ( J ) ) ≤ ∣ C 1 ∣ + ∣ C 2 ∣ − ∣ J ∣ ≤ 2 OPT ( K m ) − ∣ J ∣ , \nu(B_1-I_L(J))+\nu(B_2-I_R(J))\leq|C_1|+|C_2|-|J|
\leq2\operatorname{OPT}(K_m)-|J|, ν ( B 1 − I L ( J )) + ν ( B 2 − I R ( J )) ≤ ∣ C 1 ∣ + ∣ C 2 ∣ − ∣ J ∣ ≤ 2 OPT ( K m ) − ∣ J ∣ ,
as required. No matching condition on the original parents of J J J was used in this last step. □
All these statements hold for each fixed trajectory. Observation times, partial supports, and selected copies may therefore be chosen after the trajectory is known, provided the stated hypotheses hold. The ambient hosts K i K_i K i may be general graphs; only the auxiliary supports and proposals cross the specified cut.
The repair profile
We describe the deterministic profile underlying the approximation constant. All graphs in this section cross one fixed analytic cut ( L , R ) (L,R) ( L , R ) . This cut is distinct from the vertex cover used below: the cover may contain vertices on both sides, and edges may have both endpoints in it. Let H H H be the reference, B = H ∪ U B=H\cup U B = H ∪ U the full shared base, and C \mathcal{C} C a minimum vertex cover of B B B . Write b = ∣ C ∣ = ν ( B ) b=|\mathcal{C}|=\nu(B) b = ∣ C ∣ = ν ( B ) and let the fixed surviving suffix benchmark M \mathcal{M} M have size μ \mu μ . Sizes and degrees refer to the copied graph. The scale β \beta β is the degree bound after restriction to the analytic cut; its relation to the acquisition scale β 0 \beta_0 β 0 is given in section D. Put a v = d H ( v ) / β a_v=d_H(v)/\beta a v = d H ( v ) / β . The reference construction supplies
a u + a v ≤ 1 ( u v ∈ H ) , a u + a v ≥ 1 − λ ( u v ∈ M ∖ B ) , 0 ≤ λ ≤ 10 − 8 . a_u+a_v\leq1\quad(uv\in H),\qquad a_u+a_v\geq1-\lambda\quad(uv\in M\setminus B),\qquad0\leq\lambda\leq10^{-8}. a u + a v ≤ 1 ( uv ∈ H ) , a u + a v ≥ 1 − λ ( uv ∈ M ∖ B ) , 0 ≤ λ ≤ 1 0 − 8 .
All normalized degrees lie in [ 0 , 1 ) [0,1) [ 0 , 1 ) , and every available internal benchmark edge also has endpoint-degree sum at most one. We classify benchmark edges relative to C C C and B B B . There are r r r edges outside C C C , called roots. A benchmark edge between C C C and its complement has either an available center G G G (the edge is in B B B ) or a missing center M M M . Benchmark-unmatched centers form P P P . Internal benchmark edges have both endpoints in C C C ; their endpoints form I I I if the edge is available and J J J otherwise. Let their pair counts be z I , z J z_I,z_J z I , z J . Thus
μ = r + ∣ G ∣ + ∣ M ∣ + z I + z J , ∣ I ∣ = 2 z I , ∣ J ∣ = 2 z J . \mu=r+|G|+|M|+z_I+z_J,\qquad|I|=2z_I,\qquad|J|=2z_J. μ = r + ∣ G ∣ + ∣ M ∣ + z I + z J , ∣ I ∣ = 2 z I , ∣ J ∣ = 2 z J .
Outside vertices are root endpoints S S S , missing partners T T T , available partners A A A , or benchmark-unmatched vertices O O O . In particular ∣ S ∣ = 2 r |S|=2r ∣ S ∣ = 2 r , ∣ T ∣ = ∣ M ∣ |T|=|M| ∣ T ∣ = ∣ M ∣ and ∣ A ∣ = ∣ G ∣ |A|=|G| ∣ A ∣ = ∣ G ∣ . The center count gives a useful exact identity:
μ − b = r − ∣ P ∣ − z I − z J , r ≥ μ − b . (5) \mu-b=r-|P|-z_I-z_J,\qquad r\geq\mu-b. \tag*{(5)} μ − b = r − ∣ P ∣ − z I − z J , r ≥ μ − b . (5)
Thus a small base forces many roots. Their edges cannot belong to B B B , since neither endpoint is in its cover, and their endpoint degrees must satisfy the missing-edge lower bound. The repair uses these degrees to find edges in the two deletion graphs. It also retains the contributions of the other outside vertices; they need not be root endpoints to help complete a matching.
Reference support. Set
α = 11 20 , p = 1 − α , ω = 550001 10 6 , d = 1 100 . \alpha=\frac{11}{20},\qquad p=1-\alpha,\qquad\omega=\frac{550001}{10^6},\qquad d=\frac{1}{100}. α = 20 11 , p = 1 − α , ω = 1 0 6 550001 , d = 100 1 .
An available crossing benchmark edge is active when its original parent arrives before clock α \alpha α . All other centers send support in the primary construction without an activity coin. Give each reference incidence from an outside vertex x x x to a center c c c weight
s x c = 1 β max { d , 1 − a x } . s_{xc}=\frac{1}{\beta\max\{d,1-a_x\}}. s x c = β max { d , 1 − a x } 1 .
Set s x c = 0 s_{xc}=0 s x c = 0 when c x ∉ H cx\notin H c x ∈ / H . These weights satisfy
∑ x s x c ≤ 1 , ∑ c s x c = a x max { d , 1 − a x } , s x c ≤ 100 β . (6) \sum_x s_{xc}\leq1,\qquad\sum_c s_{xc}=\frac{a_x}{\max\{d,1-a_x\}},\qquad s_{xc}\leq\frac{100}{\beta}. \tag*{(6)} x ∑ s x c ≤ 1 , c ∑ s x c = max { d , 1 − a x } a x , s x c ≤ β 100 . (6)
Indeed, a center of reference degree D c > 0 D_c>0 D c > 0 has at most D c D_c D c outside neighbors, and a c + a x ≤ 1 a_c+a_x\leq1 a c + a x ≤ 1 gives s x c ≤ 1 / D c s_{xc}\leq1/D_c s x c ≤ 1/ D c for each of them. Every neighbor of an outside vertex lies in C C C , which proves the column identity. The cap d d d bounds the contribution of an individual incidence even at outside vertices of degree close to β \beta β . Internal reference edges do not carry repair support, but they still count in D c D_c D c and hence in the row bound. Define the fixed loads
L x = p ∑ c ∈ G s x c + ∑ c ∈ M ∪ P ∪ I ∪ J s x c , B x = ω ∑ c ∈ M ∪ J s x c + ∑ c ∈ P s x c . L_x=p\sum_{c\in G}s_{xc}+\sum_{c\in M\cup P\cup I\cup J}s_{xc},\qquad B_x=\omega\sum_{c\in M\cup J}s_{xc}+\sum_{c\in P}s_{xc}. L x = p c ∈ G ∑ s x c + c ∈ M ∪ P ∪ I ∪ J ∑ s x c , B x = ω c ∈ M ∪ J ∑ s x c + c ∈ P ∑ s x c .
The total support sent by all centers is at most b b b . In particular, at most b b b outside vertices have a x > 1 / 2 a_x>1/2 a x > 1/2 .
Two deletion constructions. Let M 0 M_0 M 0 consist of the late roots, inactive available crossing edges, late missing crossing edges, every available internal edge, and the late missing internal edges. Here late means that the original parent arrives after clock ω \omega ω . This selected set is a subset of the benchmark matching. On the cutoff bracket proved in section D, its parents are initial or subsequently tested in the designated phase, so theorem 4.4 applies.
The transfer inequality reduces the analysis to constructing one matching after deleting selected left endpoints and another after deleting selected right endpoints. Each selected benchmark edge contributes one unit in addition to these two matching sizes. An active available edge instead contributes one unit to each matching. The repair uses reference edges to fill the space left by deletions and inactive gates. Missing partners participate in this repair just as root endpoints do. An internal benchmark edge contributes a single selected edge but has two center endpoints that can send support; keeping these two counts distinct is essential. More explicitly, write H C , C ‾ H_{C,\overline{C}} H C , C for the reference incidences between the cover and its complement, and E a c t E_{\mathrm{act}} E act for the active available benchmark edges. We construct matchings in
D ℓ = ( H C , C ‾ ∪ E a c t ) − I ℓ ( M 0 ) , ℓ ∈ { L , R } . (7) D_\ell= (H_{C,\overline{C}} \cup E_{\mathrm{act}}) - I_\ell(M_0), \qquad\ell\in\{L,R\}. \tag*{(7)} D ℓ = ( H C , C ∪ E act ) − I ℓ ( M 0 ) , ℓ ∈ { L , R } . (7)
These are subgraphs of the deletion graphs in the transfer inequality. Each is also bipartite with parts C , C ‾ C,\overline{C} C , C , which is the bipartition used to round the fractional repair.
The two deletion graphs leave different vertices available. Relative to an outside vertex, call the deletion graph for its cut side primary and the other secondary. The repair uses the following capacities:
Table 2.
Available incidences are scaled by the reciprocal of the indicated positive rate. Active crossing benchmark edges receive unit weight in both constructions. Their endpoints send or receive no support. On an incidence c x cx c x , the primary construction is opposite the cut side of c c c . The probabilities that a center can send support in the two constructions are
Table 3.
and these are precisely the coefficients defining L x L_x L x and B x B_x B x . For example, an inactive available crossing edge is selected: its center is deleted in the secondary construction, while its outside partner is deleted in the primary one. If it is active, both endpoints are occupied by its unit edge instead. An available internal edge is always selected; each of its two centers therefore survives only its primary construction. A missing internal edge has the same sender rates as a missing crossing center, but its selected-edge credit is paid once per pair.
Lemma 5.1 (From support to deletion matchings). In construction ℓ \ell ℓ , let r c ℓ r_c^\ell r c ℓ and q x ℓ q_x^\ell q x ℓ be the row and column loads of the nonnegative raw support after the survival indicators and reciprocal availability factors are applied. If g = ∣ E a c t ∣ g = |E_{\mathrm{act}}| g = ∣ E act ∣ , then
ν ( D ℓ ) ≥ g + ∑ x min { q x ℓ , 1 } − ∑ c ( r c ℓ − 1 ) + . \nu(D_\ell) \ge g + \sum_x \min\{q_x^\ell,1\} - \sum_c (r_c^\ell-1)_+. ν ( D ℓ ) ≥ g + x ∑ min { q x ℓ , 1 } − c ∑ ( r c ℓ − 1 ) + .
Proof. First scale each row with load above one down to one. This removes exactly ∑ c ( r c ℓ − 1 ) + \sum_c(r_c^\ell-1)_+ ∑ c ( r c ℓ − 1 ) + mass. Next scale overloaded columns down to one; the remaining mass is the sum of their clipped loads. Because u ↦ min { u , 1 } u \mapsto\min\{u,1\} u ↦ min { u , 1 } is nondecreasing and 1-Lipschitz, the first operation reduced this sum by at most the mass it removed. The resulting support is a fractional matching. Its endpoints avoid those of the active gates, so adding their unit edges gives a fractional matching in D ℓ D_\ell D ℓ . Bipartite matching integrality proves the claim. □
This bound charges center overload once and keeps the full clipped contribution of every outside vertex. In particular, a missing partner has exactly the same availability as a root endpoint. Discarding its support would lose a nonnegative contribution to the certificate. The same applies to an unmatched outside vertex, which is always available; an available partner can help only in its secondary construction. The full support tables and clipping calculation are in sections B.3 and B.4.
The corresponding clipped target for an outside vertex is
f x = { min { L x , ω } + min { B x , 1 } , x ∈ S ∪ T , min { B x , p } , x ∈ A , min { L x , 1 } + min { B x , 1 } , x ∈ O . f_x =
\begin{cases}
\min\{L_x,\omega\}+\min\{B_x,1\}, & x\in S\cup T,\\
\min\{B_x,p\}, & x\in A,\\
\min\{L_x,1\}+\min\{B_x,1\}, & x\in O.
\end{cases} f x = ⎩ ⎨ ⎧ min { L x , ω } + min { B x , 1 } , min { B x , p } , min { L x , 1 } + min { B x , 1 } , x ∈ S ∪ T , x ∈ A , x ∈ O .
An available crossing pair contributes one gate edge to each deletion matching when active and one selected edge otherwise, giving mean credit 1 + α 1+\alpha 1 + α . Each root, missing crossing pair or missing internal pair contributes one selected edge when late, giving mean credit 1 − ω 1-\omega 1 − ω ; an available internal pair contributes one unconditionally. Adding these credits to the outside support targets gives the deterministic profile
F = ( 1 + α ) ∣ G ∣ + ( 1 − ω ) ( r + ∣ M ∣ + z J ) + z I + ∑ x f x 2 . (8) F=\frac{(1+\alpha)|G|+(1-\omega)(r+|M|+z_J)+z_I+\sum_x f_x}{2}. \tag*{(8)} F = 2 ( 1 + α ) ∣ G ∣ + ( 1 − ω ) ( r + ∣ M ∣ + z J ) + z I + ∑ x f x . (8)
The factor 1 / 2 1/2 1/2 comes from averaging the two deletion matching sizes. The quantities f x f_x f x are deterministic targets, not an assertion that clipping commutes with expectation. The probability argument below controls actual sender loads before using these targets and bounds the total row-clipping loss. It does not multiply means of dependent sender and receiver indicators. The exact construction and its equivalent loss accounting appear in section B.5.
A finite certificate for all graph profiles. The degree conditions couple the supply of reference incidences to the benchmark pairs that require them. Retaining these constraints prevents one from choosing independently a small base, many missing pairs, and arbitrarily little repair support. We encode the relevant counts in a linear relaxation. Its feasible points may include objects that are not graphs; only the map from every actual graph into the relaxation is needed.
Lemma 5.2 (Universal profile bound). Every graph profile satisfying the conditions above obeys
max { b , F } ≥ R ∗ μ . \max\{b,F\}\ge R_*\mu. max { b , F } ≥ R ∗ μ .
Certificate proof. The case max { b , F } ≥ μ \max\{b,F\}\ge\mu max { b , F } ≥ μ is immediate. Otherwise normalize counts by μ \mu μ . Partition the possible degrees into the 152 rational intervals supplied with the certificate. Record each center’s type and interval; for outside vertices, also record the affine arms attaining the minima after evaluating the reciprocal support factor at the degree interval’s lower endpoint. This replacement decreases support and therefore decreases the profile. Once an interval and a minimizing arm are fixed, each contribution is linear: a constant arm is its cap times a vertex count, and a load arm is a fixed rational combination of reference incidence counts. The minimizing arms are chosen from the actual lowered loads; no estimate of their location is assumed.
Variables count vertex classes, reference-edge classes and benchmark pair classes. Reference edges within C C C are counted once as edges and twice in the degree constraints. Counts are divided by μ \mu μ and reference-edge counts by β μ \beta\mu β μ , so the degree rows express the normalized degrees of the actual graph. The incidence counts retain the identity
∑ c ∈ C a c − ∑ x ∉ C a x = 2 ∣ E ( H [ C ] ) ∣ β . \sum_{c\in C} a_c-\sum_{x\notin C}a_x=\frac{2|E(H[C])|}{\beta}. c ∈ C ∑ a c − x ∈ / C ∑ a x = β 2∣ E ( H [ C ]) ∣ .
This is why internal reference edges cannot simply be omitted from the profile, even though the repair itself uses only outside-center edges. The constraints preserve endpoint balances, lower and upper degree bounds, benchmark normalization, and the two degree moments
∑ x ∈ S a x ≥ ( 1 − λ ) r , ∑ c ∈ M a c + ∑ x ∈ T a x ≥ ( 1 − λ ) ∣ M ∣ . \sum_{x\in S}a_x\ge(1-\lambda)r,\qquad\sum_{c\in M}a_c+\sum_{x\in T}a_x\ge(1-\lambda)|M|. x ∈ S ∑ a x ≥ ( 1 − λ ) r , c ∈ M ∑ a c + x ∈ T ∑ a x ≥ ( 1 − λ ) ∣ M ∣.
These are consequences of the actual paired endpoint constraints. The value variable dominates b / μ b/\mu b / μ and the lowered F / μ F/\mu F / μ .
All variables except the unmatched outside count in the first degree interval have total mass at most 267. In particular, the first positive interval starts at 1 / 256 1/256 1/256 , so the positive-interval unmatched count is at most 256 after normalization. The remaining unmatched count is unbounded and is excluded from the mass inequality.
Thus every actual graph gives a feasible point of the relaxation with value max { b , F } / μ \max\{b,F\}/\mu max { b , F } / μ . Write the relaxation as minimizing c T z c^Tz c T z subject to A z = a Az=a A z = a , B z ≤ b 0 Bz\le b_0 B z ≤ b 0 and z ≥ 0 z\ge0 z ≥ 0 . The supplied rational dual vectors y , t y,t y , t satisfy
t ≤ 0 , A T y + B T t ≤ c , a T y + b 0 T t = R ∗ . t\le0,\qquad A^Ty+B^Tt\le c,\qquad a^Ty+b_0^Tt=R_*. t ≤ 0 , A T y + B T t ≤ c , a T y + b 0 T t = R ∗ .
Multiplying by a feasible z z z gives c T z ≥ y T A z + t T B z ≥ a T y + b 0 T t = R ∗ c^Tz\ge y^TAz+t^TBz\ge a^Ty+b_0^Tt=R_* c T z ≥ y T A z + t T B z ≥ a T y + b 0 T t = R ∗ . Thus the conclusion uses only exact finite inequalities, rather than an optimizer’s reported value. The certificate checks all 996,325 admissible columns, including the columns for internal pairs. The complete variables, constraints, graph-to-profile map, and exact certificate verification are in section C. In particular, the unbounded interval-zero count is checked without a numerical tolerance.
Finite probability loss. Use local tolerance ε ∗ = 10 − 12 \varepsilon_*=10^{-12} ε ∗ = 1 0 − 12 and reference scale β 0 = 10 30 κ L \beta_0=10^{30}\kappa L β 0 = 1 0 30 κ L , where L = ⌈ log 2 ( 100 N / δ 0 ) ⌉ L=\lceil\log_2(100N/\delta_0)\rceil L = ⌈ log 2 ( 100 N / δ 0 )⌉ and N N N is the number of unfolded vertices. The local upper- and lower-load events have failure at most exp ( − ε ∗ 2 β / ( 4000 κ ) ) \exp(-\varepsilon_*^2\beta/(4000\kappa)) exp ( − ε ∗ 2 β / ( 4000 κ )) each. There are at most 2 b 2b 2 b center events and 6 μ 6\mu 6 μ relevant outside events. Low-degree unmatched outside vertices cannot overflow; their aggregate support is collected by sender, avoiding a union bound over all such vertices. All concentration is grouped by original parent, so copies of an edge always share one random clock.
If b ≥ 0.714 μ b\ge0.714\mu b ≥ 0.714 μ , the shared base already suffices. Otherwise r > 0.286 μ r>0.286\mu r > 0.286 μ and μ ≥ 0.49 β \mu\ge0.49\beta μ ≥ 0.49 β , which ensure that the aggregate and local errors are below 10 − 7 μ 10^{-7}\mu 1 0 − 7 μ . The designated phase and shared base then certify, on the repair and cutoff good events,
V ≥ max { b , F − 10 − 7 μ } ≥ ( R ∗ − 10 − 7 ) μ . V\ge\max\{b,F-10^{-7}\mu\}\ge(R_*-10^{-7})\mu. V ≥ max { b , F − 1 0 − 7 μ } ≥ ( R ∗ − 1 0 − 7 ) μ .
The acquisition prefix preserves at least a 1 − 2 ⋅ 10 − 8 1-2\cdot10^{-8} 1 − 2 ⋅ 1 0 − 8 fraction of a fixed input optimum on its good event. Including the separate acquisition and cutoff failure allocations gives the bounded integer coefficient a ∗ > 0.71295 a_*>0.71295 a ∗ > 0.71295 .
Section B proves the complete repair and probability bounds; section D gives acquisition, cutoff and resource accounting.
The marked-pair potential and weighted Tutte minors
We prove theorem 4.1 and the parity argument used in theorem 4.3. Write F ( M ) = F K ( M ) F(M)=F_K(M) F ( M ) = F K ( M ) for the marked-pair optimum defined in section 4.
The matrix representation. First suppose the weights are nonnegative integers. Order V V V , introduce independent commuting variables z e z_e z e for the original undirected edges, and work over Q ( z e : e ∈ E ) ( t ) \mathbb{Q}(z_e:e\in E)(t) Q ( z e : e ∈ E ) ( t ) . The weighted Tutte matrix is
A u v = { z u v t w ( u v ) u v ∈ E , u < v , − z u v t w ( u v ) u v ∈ E , v < u , 0 otherwise. A_{uv}=
\begin{cases}
z_{uv}t^{w(uv)} & uv\in E,\ u<v,\\
-z_{uv}t^{w(uv)} & uv\in E,\ v<u,\\
0 & \text{otherwise.}
\end{cases} A uv = ⎩ ⎨ ⎧ z uv t w ( uv ) − z uv t w ( uv ) 0 uv ∈ E , u < v , uv ∈ E , v < u , otherwise.
Both orientations use the same variable . For R ⊆ V R\subseteq V R ⊆ V , define
g ( R ) = max I , J ⊆ V , ∣ I ∣ = ∣ J ∣ , J ⊆ R det A [ I , J ] ≠ 0 deg t det A [ I , J ] . g(R)=\max_{\substack{I,J\subseteq V,\ |I|=|J|,\ J\subseteq R\\ \det A[I,J]\ne0}}\deg_t\det A[I,J]. g ( R ) = I , J ⊆ V , ∣ I ∣ = ∣ J ∣ , J ⊆ R d e t A [ I , J ] = 0 max deg t det A [ I , J ] .
The empty minor has determinant one and is included.
Lemma A.1 (Matching interpretation). For every M ⊆ V M\subseteq V M ⊆ V , F ( M ) = g ( V ∖ M ) F(M)=g(V\setminus M) F ( M ) = g ( V ∖ M ) .
Proof. A nonzero Leibniz term of det A [ I , J ] \det A[I,J] det A [ I , J ] is a bijection from I I I to J J J , viewed as directed edges. Every vertex has in-degree and out-degree at most one, so its nontrivial components are directed paths and directed cycles; loops are excluded by the zero diagonal. A vertex outside J J J can only be the initial vertex of a path.
Group terms by their multiset of undirected edges, retaining multiplicity. Every path has a uniquely determined orientation, since its source lies in I ∖ J I\setminus J I ∖ J and its sink in J ∖ I J\setminus I J ∖ I . A doubled edge is a directed two-cycle and also has a unique orientation. A cycle of length at least three has two orientations. Reversing a cycle of length ℓ \ell ℓ preserves the permutation sign and changes the product of matrix entries by ( − 1 ) ℓ (-1)^\ell ( − 1 ) ℓ . Hence a fiber containing an odd cycle cancels. A fiber with only even cycles has coefficient ± 2 c \pm2^c ± 2 c , where c c c counts its cycles of length at least four, and does not cancel in characteristic zero. Distinct fibers have distinct z z z -monomials, so cannot cancel each other even when their t t t -degrees agree.
For a surviving fiber, alternately color the edges of each path and even cycle with colors 1 and 2; put a doubled edge into both colors. Since J J J avoids M M M , a marked vertex incident to an edge must be a path source. Each path has only one source, so every nontrivial component contains at most one mark. Start a path with color 2 when its source is marked. Thus color 1 avoids M M M , and the resulting pair is M M M -admissible. Its weight equals the degree of the fiber. This gives g ( V ∖ M ) ≤ F ( M ) g(V\setminus M)\le F(M) g ( V ∖ M ) ≤ F ( M ) .
Conversely, the symmetric difference of an admissible pair decomposes into paths and even cycles. Orient each marked path away from its marked endpoint; such an endpoint is exposed by N 1 N_1 N 1 . Orient other paths arbitrarily, orient even cycles cyclically, and replace each common edge by a two-cycle. The resulting directed factor has equal-size row and column supports I , J I,J I , J , with J ∩ M = ∅ J\cap M=\varnothing J ∩ M = ∅ . Its undirected fiber has no odd cycle, so its monomial survives in det A [ I , J ] \det A[I,J] det A [ I , J ] , with degree w ( N 1 ) + w ( N 2 ) w(N_1)+w(N_2) w ( N 1 ) + w ( N 2 ) . This proves the reverse inequality.
This is the symmetric-digraph specialization of the weighted even-factor identity of Cunningham and Geelen, as stated in [16 Theorem 4.2] . The two opposite arcs of an undirected edge have equal weight, so the odd-cycle-symmetry hypothesis of that theorem is satisfied. The shared variables and doubled two-cycles are essential to the specialization.
Actual determinant exchange. For a fixed matrix C C C with rows indexed by V V V over a rational-function field, assume an always-available set D D D of columns contains a nonsingular square basis. Let h ( R ) h(R) h ( R ) be the largest degree of a nonsingular maximal minor whose columns are in D ∪ R D \cup R D ∪ R . For a nonzero rational function, its degree is the numerator degree minus the denominator degree. Degrees add under multiplication, and the degree of a nonzero sum is at most the largest degree of its nonzero summands.
Lemma A.2 (Availability submodularity). h ( U ∪ W ) + h ( U ∩ W ) ≤ h ( U ) + h ( W ) h(U \cup W) + h(U \cap W) \le h(U) + h(W) h ( U ∪ W ) + h ( U ∩ W ) ≤ h ( U ) + h ( W ) .
Proof. We use the following actual-matrix exchange fact. Given nonsingular square matrices P , Q P,Q P , Q and a prescribed set S S S of column positions, there is a permutation of the columns of Q Q Q such that exchanging the columns at S S S produces two nonsingular matrices P ′ , Q ′ P',Q' P ′ , Q ′ satisfying
deg det P + deg det Q ≤ deg det P ′ + deg det Q ′ . \deg\det P + \deg\det Q \le\deg\det P' + \deg\det Q'. deg det P + deg det Q ≤ deg det P ′ + deg det Q ′ .
To see this, normalize to P = I P=I P = I and Q = B = P − 1 Q Q=B=P^{-1}Q Q = B = P − 1 Q . Split the rows into S S S and its complement. Multilinearity gives the generalized Laplace identity
det B = ∑ T ⊆ V det B S , T , ( B S , T ) i j = { B i j ( i ∈ S ) ⟺ ( j ∈ T ) , 0 otherwise . \det B = \sum_{T \subseteq V} \det B_{S,T}, \qquad(B_{S,T})_{ij} =
\begin{cases}
B_{ij} & (i \in S) \Longleftrightarrow(j \in T),\\
0 & \text{otherwise}.
\end{cases} det B = T ⊆ V ∑ det B S , T , ( B S , T ) ij = { B ij 0 ( i ∈ S ) ⟺ ( j ∈ T ) , otherwise .
Some nonzero summand has degree at least that of det B \det B det B . Any surviving Leibniz term of this summand supplies a permutation aligning T T T with S S S . After that permutation, its determinant is, up to sign, the product of the two complementary exchanged determinants. Both factors are nonzero. Multiplying back by P P P proves the stated inequality. This is a direct generalized Laplace argument; see also [18 ] for the general multiple-exchange framework.
Now take maximizing column tuples P P P for D ∪ ( U ∪ W ) D \cup(U \cup W) D ∪ ( U ∪ W ) and Q Q Q for D ∪ ( U ∩ W ) D \cup(U \cap W) D ∪ ( U ∩ W ) . Prescribe exactly the positions of P P P whose columns are unavailable in D ∪ U D \cup U D ∪ U . After exchange, the first tuple is available in D ∪ U D \cup U D ∪ U . Every removed column lies in W W W , while every column of Q Q Q is available on both sides; hence the second tuple is available in D ∪ W D \cup W D ∪ W . Their nonsingularity and the exchange inequality prove the claim. Repeated columns need no extra assumption: a nonsingular tuple cannot contain them. □
Apply Lemma A.2 to C = [ A ∣ I ] C=[A \mid I] C = [ A ∣ I ] , with all identity columns always available. Expanding along the selected identity columns identifies every nonsingular maximal minor, up to sign, with an ordinary minor A [ I , J ] A[I,J] A [ I , J ] , and every ordinary minor can be padded in this manner. Thus g g g is submodular. Complementation preserves submodularity, so Lemma A.1 gives
F ( S ∪ T ) + F ( S ∩ T ) ≤ F ( S ) + F ( T ) . F(S \cup T) + F(S \cap T) \le F(S) + F(T). F ( S ∪ T ) + F ( S ∩ T ) ≤ F ( S ) + F ( T ) .
The argument extends from integer to nonnegative rational weights by common scaling, and then to nonnegative real weights by continuity. Explicitly,
∣ F w ( M ) − F v ( M ) ∣ ≤ 2 ∑ e ∈ E ∣ w e − v e ∣ , \lvert F_w(M) - F_v(M) \rvert\le2\sum_{e \in E} \lvert w_e - v_e \rvert, ∣ F w ( M ) − F v ( M )∣ ≤ 2 e ∈ E ∑ ∣ w e − v e ∣ ,
because each matching pair uses an edge at most twice. Applying the rational result to ⌊ k w e ⌋ / k \lfloor kw_e \rfloor/k ⌊ k w e ⌋ / k and letting k → ∞ k \to\infty k → ∞ therefore proves submodularity for nonnegative real weights.
From the potential to cut transfer
Proof of theorem 4.3. Let P 1 P_1 P 1 and P 2 P_2 P 2 be optimum matchings in A − I L ( T ) A-I_L(T) A − I L ( T ) and A − I R ( T ) A-I_R(T) A − I R ( T ) , respectively. Mark the endpoints of T T T . A marked left vertex is exposed by P 1 P_1 P 1 , and a marked right vertex is exposed by P 2 P_2 P 2 . Hence any mark incident to P 1 △ P 2 P_1\mathbin{\triangle}P_2 P 1 △ P 2 is an endpoint of an alternating path.
Such a path cannot have two marked endpoints. If they lie on the same side of the cut, their incident edges belong to the same matching, so the path has odd length; bipartiteness requires even length. If they lie on opposite sides, the incident edges belong to different matchings, so the path has even length; bipartiteness requires odd length. Common edges contain no mark because each belongs to both matchings.
On each marked component, interchange the two matching colors if needed so that the first matching avoids its mark. This gives an admissible pair ( N 1 , N 2 ) (N_1,N_2) ( N 1 , N 2 ) in A A A with
w ( N 1 ) + w ( N 2 ) = OPT ( A − I L ( T ) ) + OPT ( A − I R ( T ) ) . w(N_1)+w(N_2)=\operatorname{OPT}(A-I_L(T))+\operatorname{OPT}(A-I_R(T)). w ( N 1 ) + w ( N 2 ) = OPT ( A − I L ( T )) + OPT ( A − I R ( T )) .
For e = u v e=uv e = uv , adjoining e e e to an optimum of K t e − { u , v } K_{t_e}-\{u,v\} K t e − { u , v } gives a matching in K t e + e K_{t_e}+e K t e + e . Closure thus implies w e ≤ D K t e ( { u , v } ) w_e\le D_{K_{t_e}}(\{u,v\}) w e ≤ D K t e ({ u , v }) . The endpoint pairs of T T T are disjoint, so theorem 4.2, together with the displayed admissible pair, proves the corollary.
The typed repair and its finite probability bound
This appendix proves the graph and probability estimates used by the internal-pair profile. The two deletion constructions are actual subgraphs, and their lower bounds come from explicitly constructed fractional matchings. All random variables are functions of independent original-edge labels. Copies with the same parent are never treated as independent.
The fixed reference instance and notation
Fix the reference graph H H H , the complete reference-plus-underfull graph, a vertex cover C C C of the latter, and a benchmark matching Q Q Q of size μ \mu μ . Every edge under consideration crosses the analytic bipartition Z = ( Z 0 , Z 1 ) Z=(Z_0,Z_1) Z = ( Z 0 , Z 1 ) , including the edges of Q Q Q . The cover C C C need not be one side of Z Z Z . In particular, reference and benchmark edges may have both endpoints in C C C . Write b = ∣ C ∣ b=|C| b = ∣ C ∣ and C ‾ = V ( H ) ∖ C \overline{C}=V(H)\setminus C C = V ( H ) ∖ C , including isolated benchmark or unmatched vertices when needed.
Partition the centers into G , M , P , I , J G,M,P,I,J G , M , P , I , J . A center in G G G has an available benchmark edge to C ‾ \overline{C} C ; a center in M M M has a missing benchmark edge to C ‾ \overline{C} C ; and a center in P P P is unmatched by Q Q Q . The sets I I I and J J J consist of the endpoints of available and missing benchmark edges internal to C C C , respectively. Thus I I I and J J J are vertex sets. Let I \mathcal{I} I and J \mathcal{J} J be their pair sets, and put
z I = ∣ I ∣ = ∣ I ∣ / 2 , z J = ∣ J ∣ = ∣ J ∣ / 2. z_I=|\mathcal{I}|=|I|/2,\qquad z_J=|\mathcal{J}|=|J|/2. z I = ∣ I ∣ = ∣ I ∣/2 , z J = ∣ J ∣ = ∣ J ∣/2.
Partition the outside vertices into S , T , A , O S,T,A,O S , T , A , O : root endpoints, partners of M M M centers, partners of G G G centers, and benchmark-unmatched vertices. Let R \mathcal{R} R be the root-pair set and r = ∣ R ∣ = ∣ S ∣ / 2 r=|\mathcal{R}|=|S|/2 r = ∣ R ∣ = ∣ S ∣/2 . The benchmark matching gives the exact identities
b = ∣ G ∣ + ∣ M ∣ + ∣ P ∣ + ∣ I ∣ + ∣ J ∣ , (9) b=|G|+|M|+|P|+|I|+|J|, \tag*{(9)} b = ∣ G ∣ + ∣ M ∣ + ∣ P ∣ + ∣ I ∣ + ∣ J ∣ , (9)
μ = r + ∣ G ∣ + ∣ M ∣ + z I + z J , (10) \mu=r+|G|+|M|+z_I+z_J, \tag*{(10)} μ = r + ∣ G ∣ + ∣ M ∣ + z I + z J , (10)
∣ S ∣ = 2 r , ∣ T ∣ = ∣ M ∣ , ∣ A ∣ = ∣ G ∣ . (11) |S|=2r,\qquad|T|=|M|,\qquad|A|=|G|. \tag*{(11)} ∣ S ∣ = 2 r , ∣ T ∣ = ∣ M ∣ , ∣ A ∣ = ∣ G ∣. (11)
There is no upper bound on ∣ O ∣ |O| ∣ O ∣ .
In the final streaming application, the benchmark is obtained by deleting from a fixed original optimum every original edge exposed during acquisition. Consequently every benchmark parent is a physical suffix label. Since H H H contains only acquisition-prefix copies, available benchmark copies in G G G and I I I belong to the underfull graph. No auxiliary clock for an already exposed benchmark parent is needed.
Let B \mathcal{B} B be the finite set of original suffix labels. Each copied benchmark edge has a parent e ∈ B e \in\mathcal{B} e ∈ B . Assume at most κ \kappa κ benchmark copies have any one parent. This is a multiplicity condition, not an independence condition. For the canonical unfolding with weights at most W W W , it follows with κ = W \kappa= W κ = W : copies of one original edge in a copied matching have distinct left indices in { 1 , … , W } \{1,\ldots,W\} { 1 , … , W } . Restricting to any of the disjoint types above can only reduce that count.
We use the parameters
α = 11 20 , p = 1 − α = 9 20 , ω = 550001 10 6 , ε = 10 − 12 , d = 10 − 2 . (12) \alpha= \frac{11}{20},\qquad p=1-\alpha=\frac{9}{20},\qquad\omega=\frac{550001}{10^6},\qquad\varepsilon=10^{-12},\qquad d=10^{-2}. \tag*{(12)} α = 20 11 , p = 1 − α = 20 9 , ω = 1 0 6 550001 , ε = 1 0 − 12 , d = 1 0 − 2 . (12)
The support cap d d d agrees with section 5. We denote the local failure allowance by δ 0 \delta_0 δ 0 . For every vertex let a v = deg H ( v ) / β a_v=\deg_H(v)/\beta a v = deg H ( v ) / β . The reference degree conditions are
β > 0 , a u + a v ≤ 1 ( u v ∈ H ) . (13) \beta>0,\qquad a_u+a_v\le1\quad(uv\in H). \tag*{(13)} β > 0 , a u + a v ≤ 1 ( uv ∈ H ) . (13)
They imply 0 ≤ a v < 1 0\le a_v<1 0 ≤ a v < 1 : an isolated vertex has a v = 0 a_v=0 a v = 0 , and a nonisolated vertex has a neighbor of degree at least one, hence degree at most β − 1 \beta-1 β − 1 . Define, for x ∈ C ‾ x\in\overline{C} x ∈ C ,
d x = max { d , 1 − a x } , w c x = { ( β d x ) − 1 , c x ∈ H , 0 , c x ∉ H . (14) d_x=\max\{d,1-a_x\},\qquad
w_{cx}=
\begin{cases}
(\beta d_x)^{-1}, & cx\in H,\\
0, & cx\notin H.
\end{cases} \tag*{(14)} d x = max { d , 1 − a x } , w c x = { ( β d x ) − 1 , 0 , c x ∈ H , c x ∈ / H . (14)
Only outside-center reference incidences receive support. Edges internal to C C C are included in the degrees in (13).
Lemma B.1 (Reference capacities). For every center c c c and outside vertex x x x ,
∑ x w c x ≤ 1 , ∑ c w c x = a x d x ≤ 1 d x , 0 ≤ w c x ≤ 1 β d x ≤ 100 β . (15) \sum_x w_{cx}\le1,\qquad
\sum_c w_{cx}=\frac{a_x}{d_x}\le\frac{1}{d_x},\qquad
0\le w_{cx}\le\frac{1}{\beta d_x}\le\frac{100}{\beta}. \tag*{(15)} x ∑ w c x ≤ 1 , c ∑ w c x = d x a x ≤ d x 1 , 0 ≤ w c x ≤ β d x 1 ≤ β 100 . (15)
Proof. All neighbors of x x x lie in C C C , because C C C covers H H H . The column identity therefore follows by counting its β a x \beta a_x β a x incidences. For the row bound, put D c = deg H ( c ) D_c=\deg_H(c) D c = deg H ( c ) . If D c = 0 D_c=0 D c = 0 there is nothing to prove. Otherwise, every outside neighbor x x x satisfies β ( 1 − a x ) ≥ D c \beta(1-a_x)\ge D_c β ( 1 − a x ) ≥ D c by (13), so w c x ≤ 1 / D c w_{cx}\le1/D_c w c x ≤ 1/ D c . There are at most D c D_c D c such neighbors. The remaining inequalities follow from a x < 1 a_x<1 a x < 1 and d x ≥ d = 1 / 100 d_x\ge d=1/100 d x ≥ d = 1/100 . □ \square □
The selected matching and the two deletion graphs
Give each original label e e e an independent category Z e ∈ { 0 , 1 , 2 } Z_e\in\{0,1,2\} Z e ∈ { 0 , 1 , 2 } with probabilities
Pr [ Z e = 0 ] = α , Pr [ Z e = 1 ] = ω − α , Pr [ Z e = 2 ] = 1 − ω . \Pr[Z_e=0]=\alpha,\qquad\Pr[Z_e=1]=\omega-\alpha,\qquad\Pr[Z_e=2]=1-\omega. Pr [ Z e = 0 ] = α , Pr [ Z e = 1 ] = ω − α , Pr [ Z e = 2 ] = 1 − ω .
Write χ e = 1 { Z e = 0 } \chi_e=\mathbf{1}_{\{Z_e=0\}} χ e = 1 { Z e = 0 } and η e = 1 { Z e ≠ 2 } \eta_e=\mathbf{1}_{\{Z_e\ne2\}} η e = 1 { Z e = 2 } . A copied edge reads the indicators of its original parent. Different copies of a parent can have different cover types, but they still read these same indicators. Let G a c t = { g ∈ G : χ par ( g ) = 1 } G_{\mathrm{act}}=\{g\in G:\chi_{\operatorname{par}(g)}=1\} G act = { g ∈ G : χ par ( g ) = 1 } .
For a fixed realization, select the following submatching Q 0 ⊆ Q Q_0\subseteq Q Q 0 ⊆ Q :
These are subsets of one matching, so their endpoints are pairwise disjoint. For ℓ ∈ { 0 , 1 } \ell\in\{0,1\} ℓ ∈ { 0 , 1 } let
X ℓ = V ( Q 0 ) ∩ Z ℓ . X_{\ell}=V(Q_{0})\cap Z_{\ell}. X ℓ = V ( Q 0 ) ∩ Z ℓ .
Let H C , C ˉ H_{C,\bar{C}} H C , C ˉ contain the outside-center edges of H H H , and let E a c t E_{\mathrm{act}} E act be the benchmark gate edges indexed by G a c t G_{\mathrm{act}} G act . The graph used for the ℓ \ell ℓ th repair is exactly
D ℓ = ( H C , C ˉ ∪ E a c t ) − X ℓ . (16) D_{\ell}=(H_{C,\bar{C}}\cup E_{\mathrm{act}})-X_{\ell}. \tag*{(16)} D ℓ = ( H C , C ˉ ∪ E act ) − X ℓ . (16)
Thus a center or outside vertex survives precisely when it is not a selected endpoint on side Z ℓ Z_{\ell} Z ℓ . Each active gate is absent from Q 0 Q_{0} Q 0 . Both its endpoints consequently survive in both graphs D 0 , D 1 D_{0},D_{1} D 0 , D 1 .
For the repair estimate, let V V V be any real-valued function of the clocks satisfying
ν ( D 0 ) + ν ( D 1 ) + ∣ Q 0 ∣ ≤ 2 V , V ≥ b , (17) \nu(D_{0})+\nu(D_{1})+|Q_{0}|\le2V,\qquad V\ge b, \tag*{(17)} ν ( D 0 ) + ν ( D 1 ) + ∣ Q 0 ∣ ≤ 2 V , V ≥ b , (17)
where ν \nu ν denotes maximum matching cardinality in the copied graph. The analytic score
max { b , ν ( D 0 ) + ν ( D 1 ) + ∣ Q 0 ∣ 2 } \max\left\{b,\frac{\nu(D_{0})+\nu(D_{1})+|Q_{0}|}{2}\right\} max { b , 2 ν ( D 0 ) + ν ( D 1 ) + ∣ Q 0 ∣ }
satisfies this interface for every clock realization, as does the score obtained from larger deletion graphs. We apply the probability bound below to such an analytic score without conditioning on a cutoff event. In the streaming application, the structural transfer theorem compares this score with the actual output only on the cutoff bracket proved in section D. That comparison is used after the repair probability bound. It does not require persistence of weighted rejections.
Survival, occupancy, and the exact support tables
For an outside vertex x x x , call the construction with ℓ = Z ( x ) \ell=Z(x) ℓ = Z ( x ) its primary construction , and the other its secondary construction . A center sends primary support in the construction opposite its own cut side, and secondary support on its own cut side. These conventions agree on an incidence c x ∈ H cx\in H c x ∈ H , because Z ( c ) ≠ Z ( x ) Z(c)\ne Z(x) Z ( c ) = Z ( x ) .
Exclude both endpoints of every active gate from raw support. Let S c + , S c − S_c^{+},S_c^{-} S c + , S c − be the resulting sender indicators and R x + , R x − R_x^{+},R_x^{-} R x + , R x − the receiver indicators. They are as follows; each indicator on a paired vertex uses that pair’s original parent.
Table 4.
Table 5.
Here h x σ = E R x σ h_x^\sigma= ER_x^\sigma h x σ = E R x σ for σ ∈ { + , − } \sigma\in\{+,-\} σ ∈ { + , − } . Every positive h x σ h_x^\sigma h x σ exceeds 1 / 3 1/3 1/3 .
We verify the survival rules explicitly. An inactive G G G pair is selected, so its center is deleted in the secondary construction and its outside partner is deleted in the primary construction. If the gate is active, both endpoints are occupied by its unit gate edge and are excluded from support in both constructions. This gives the G G G and A A A rows of the tables. A missing crossing pair is selected exactly when η = 0 \eta= 0 η = 0 . Its center always survives in the primary construction and survives in the secondary construction exactly when η = 1 \eta= 1 η = 1 ; its partner has the opposite deletion rule. A late root pair is selected, so either root endpoint survives its primary construction exactly when η = 1 \eta= 1 η = 1 and always survives its secondary construction. Available internal pairs are always selected; each endpoint therefore survives precisely its primary construction. Missing internal pairs give the same sender rule as M M M . Finally, vertices in P P P and O O O are neither selected nor occupied. These cases exhaust all vertices.
For a construction ℓ \ell ℓ and an incidence c x cx c x , let σ \sigma σ be + + + if ℓ = Z ( x ) \ell= Z(x) ℓ = Z ( x ) and − - − otherwise. Define the raw support by
f c x ℓ = { S c σ R x σ w c x / h x σ , h x σ > 0 , 0 , h x σ = 0. (18) f_{cx}^{\ell} =
\begin{cases}
S_c^\sigma R_x^\sigma w_{cx}/h_x^\sigma, & h_x^\sigma> 0,\\
0, & h_x^\sigma= 0.
\end{cases} \tag*{(18)} f c x ℓ = { S c σ R x σ w c x / h x σ , 0 , h x σ > 0 , h x σ = 0. (18)
For the zero-capacity case one may equivalently use denominator one, since the receiver indicator is identically zero. The survival table proves that every nonzero entry of f ℓ f^\ell f ℓ is an edge of D ℓ D_\ell D ℓ and neither endpoint is occupied by an active gate. This proves support and collision avoidance directly from the deletion rule, rather than assuming them as properties of an abstract fractional solution.
Two-stage clipping and integral matching value
We record the clipping calculation in a form that charges only center overloads. For any nonnegative matrix f : C × C → R f:C \times C \to\mathbb{R} f : C × C → R , write r c = ∑ x f c x r_c = \sum_x f_{cx} r c = ∑ x f c x , q x = ∑ c f c x q_x = \sum_c f_{cx} q x = ∑ c f c x , and define
f ^ c x = f c x max { 1 , r c } , f ~ c x = f ^ c x max { 1 , ∑ c ′ f ^ c ′ x } . \widehat{f}_{cx} = \frac{f_{cx}}{\max\{1,r_c\}}, \qquad
\widetilde{f}_{cx} = \frac{\widehat{f}_{cx}}{\max\{1,\sum_{c'}\widehat{f}_{c'x}\}}. f c x = max { 1 , r c } f c x , f c x = max { 1 , ∑ c ′ f c ′ x } f c x .
Both operations decrease entries and preserve support. The first makes every row sum at most one, and the second makes every column sum at most one without increasing any row sum.
Lemma B.2 (Clipping loss). The repaired mass satisfies
∑ c , x f ~ c x ≥ ∑ x min { q x , 1 } − ∑ c ( r c − 1 ) + . (19) \sum_{c,x}\widetilde{f}_{cx} \ge\sum_x \min\{q_x,1\} - \sum_c (r_c-1)_+. \tag*{(19)} c , x ∑ f c x ≥ x ∑ min { q x , 1 } − c ∑ ( r c − 1 ) + . (19) Proof. Row clipping changes row c c c from mass r c r_c r c to min { r c , 1 } \min\{r_c,1\} min { r c , 1 } , so it removes exactly ∑ c ( r c − 1 ) + \sum_c(r_c-1)_+ ∑ c ( r c − 1 ) + . If q ^ x = ∑ c f ^ c x \widehat{q}_x = \sum_c \widehat{f}_{cx} q x = ∑ c f c x , column clipping then removes exactly ∑ x ( q ^ x − 1 ) + \sum_x(\widehat{q}_x-1)_+ ∑ x ( q x − 1 ) + . Since f ^ ≤ f \widehat{f} \le f f ≤ f entrywise, q ^ x ≤ q x \widehat{q}_x \le q_x q x ≤ q x . Consequently
∑ c , x f ~ c x ≥ ∑ c , x f c x − ∑ c ( r c − 1 ) + − ∑ x ( q x − 1 ) + = ∑ x min { q x , 1 } − ∑ c ( r c − 1 ) + . \sum_{c,x}\widetilde{f}_{cx}
\ge\sum_{c,x} f_{cx} - \sum_c(r_c-1)_+ - \sum_x(q_x-1)_+
= \sum_x\min\{q_x,1\} - \sum_c(r_c-1)_+. c , x ∑ f c x ≥ c , x ∑ f c x − c ∑ ( r c − 1 ) + − x ∑ ( q x − 1 ) + = x ∑ min { q x , 1 } − c ∑ ( r c − 1 ) + . In particular, no column overload is subtracted twice.
Apply this construction to f ℓ f^\ell f ℓ and add a unit on each active gate. The active gates form a matching. Each of their rows and columns is identically zero in f ℓ f^\ell f ℓ and remains zero after clipping. The sum of the unit gates and f ~ ℓ \tilde{f}^\ell f ~ ℓ is therefore a fractional matching in the actual bipartite incidence graph D ℓ D_\ell D ℓ , with parts C , C ‾ C,\overline{C} C , C .
For completeness, every fractional matching in a bipartite graph has mass at most the size of an integral matching. To see the needed version, take a maximum matching M ∗ M_* M ∗ . Starting at unmatched vertices on the left, follow unmatched edges from left to right and matched edges from right to left. Let L ∗ , R ∗ L_*,R_* L ∗ , R ∗ be the reached sets. No unmatched right vertex is reached, since it would give an augmenting path. The set ( C ∖ L ∗ ) ∪ R ∗ (C\setminus L_*)\cup R_* ( C ∖ L ∗ ) ∪ R ∗ covers every edge: an uncovered unmatched edge would extend the reachability search, and the endpoints of a matched edge are reached together. Exactly one endpoint of every matching edge belongs to this cover, and no unmatched vertex does, so the cover has size ∣ M ∗ ∣ |M_*| ∣ M ∗ ∣ . Summing the fractional degree constraints over the cover bounds the fractional mass by ∣ M ∗ ∣ |M_*| ∣ M ∗ ∣ .
Let g = ∣ G a c t ∣ g=|G_{\mathrm{act}}| g = ∣ G act ∣ . We have proved, for each realized construction,
ν ( D ℓ ) ≥ g + ∑ x min { ∑ c f c x ℓ , 1 } − ∑ c ( ∑ x f c x ℓ − 1 ) + . (20) \nu(D_\ell)\ge g+\sum_x\min\left\{\sum_c f^\ell_{cx},1\right\}-\sum_c\left(\sum_x f^\ell_{cx}-1\right)_+. \tag*{(20)} ν ( D ℓ ) ≥ g + x ∑ min { c ∑ f c x ℓ , 1 } − c ∑ ( x ∑ f c x ℓ − 1 ) + . (20)
This argument also proves integrality of the witness without requiring any independence of its entries.
The deterministic profile and exact bare credit
Define the two deterministic sender loads
L x = ∑ c ∈ G p w c x + ∑ c ∈ M ∪ P ∪ I ∪ J w c x , (21) L_x=\sum_{c\in G}p\,w_{cx}+\sum_{c\in M\cup P\cup I\cup J}w_{cx}, \tag*{(21)} L x = c ∈ G ∑ p w c x + c ∈ M ∪ P ∪ I ∪ J ∑ w c x , (21)
B x = ∑ c ∈ M ∪ J ω w c x + ∑ c ∈ P w c x . (22) B_x=\sum_{c\in M\cup J}\omega\,w_{cx}+\sum_{c\in P}w_{cx}. \tag*{(22)} B x = c ∈ M ∪ J ∑ ω w c x + c ∈ P ∑ w c x . (22)
They are the means of the unscaled primary and secondary sender sums. Set m x + = L x m_x^+=L_x m x + = L x , m x − = B x m_x^-=B_x m x − = B x . The outside profile is
Ψ = ∑ x ∈ S ∪ T ( min { L x , ω } + min { B x , 1 } ) + ∑ x ∈ A min { B x , p } + ∑ x ∈ O ( min { L x , 1 } + min { B x , 1 } ) . (23) \Psi=\sum_{x\in S\cup T}\left(\min\{L_x,\omega\}+\min\{B_x,1\}\right)+\sum_{x\in A}\min\{B_x,p\}
+\sum_{x\in O}\left(\min\{L_x,1\}+\min\{B_x,1\}\right). \tag*{(23)} Ψ = x ∈ S ∪ T ∑ ( min { L x , ω } + min { B x , 1 } ) + x ∈ A ∑ min { B x , p } + x ∈ O ∑ ( min { L x , 1 } + min { B x , 1 } ) . (23)
Equivalently, Ψ = ∑ x , σ min { m x σ , h x σ } \Psi=\sum_{x,\sigma}\min\{m_x^\sigma,h_x^\sigma\} Ψ = ∑ x , σ min { m x σ , h x σ } . The full profile is
F = ( 1 + α ) ∣ G ∣ + ( 1 − ω ) ( r + ∣ M ∣ + z J ) + z I + Ψ 2 . (24) F=\frac{(1+\alpha)|G|+(1-\omega)(r+|M|+z_J)+z_I+\Psi}{2}. \tag*{(24)} F = 2 ( 1 + α ) ∣ G ∣ + ( 1 − ω ) ( r + ∣ M ∣ + z J ) + z I + Ψ . (24)
Using (11), this is exactly
F = b − p ∣ G ∣ + ( 1 + ω ) ∣ M ∣ + 2 ( ∣ P ∣ + ∣ I ∣ + ∣ J ∣ ) 2 + Ψ + ( 1 − ω ) r + z I + ( 1 − ω ) z J 2 . (25) F=b-\frac{p|G|+(1+\omega)|M|+2(|P|+|I|+|J|)}{2}+\frac{\Psi+(1-\omega)r+z_I+(1-\omega)z_J}{2}. \tag*{(25)} F = b − 2 p ∣ G ∣ + ( 1 + ω ) ∣ M ∣ + 2 ( ∣ P ∣ + ∣ I ∣ + ∣ J ∣ ) + 2 Ψ + ( 1 − ω ) r + z I + ( 1 − ω ) z J . (25)
This identity explains the factors of two on internal endpoint sets. One available internal pair contributes one selected edge, rather than two, and the same is true of a selected missing internal pair.
Let ℓ R , ℓ M , ℓ J \ell_R,\ell_M,\ell_J ℓ R , ℓ M , ℓ J be the numbers of late pairs in R , M , J \mathcal{R},M,\mathcal{J} R , M , J , respectively. The selection rule gives
∣ Q 0 ∣ = ℓ R + ( ∣ G ∣ − g ) + ℓ M + z I + ℓ J . |Q_0|=\ell_R+(|G|-g)+\ell_M+z_I+\ell_J. ∣ Q 0 ∣ = ℓ R + ( ∣ G ∣ − g ) + ℓ M + z I + ℓ J .
Thus the exact bare credit from the two gate matchings and the selected matching is
2 g + ∣ Q 0 ∣ = ∣ G ∣ + g + ℓ R + ℓ M + z I + ℓ J . (26) 2g+|Q_0|=|G|+g+\ell_R+\ell_M+z_I+\ell_J. \tag*{(26)} 2 g + ∣ Q 0 ∣ = ∣ G ∣ + g + ℓ R + ℓ M + z I + ℓ J . (26)
No expectation or approximation has entered this equality.
A concentration lemma with shared parent clocks
We use the following elementary form of Hoeffding’s inequality. Suppose Y i Y_i Y i depends only on the categorical clock of parent π ( i ) \pi(i) π ( i ) and takes values in a fixed interval of length u i ≥ 0 u_i\ge0 u i ≥ 0 . For each original parent put U e = ∑ i : π ( i ) = e u i U_e=\sum_{i:\pi(i)=e}u_i U e = ∑ i : π ( i ) = e u i . Then, for t > 0 t>0 t > 0 ,
Pr [ ∑ i Y i − E ∑ i Y i ≥ t ] , Pr [ E ∑ i Y i − ∑ i Y i ≥ t ] ≤ exp ( − 2 t 2 ∑ e U e 2 ) . (27) \Pr\left[\sum_iY_i-\mathbb{E}\sum_iY_i\ge t\right],\quad
\Pr\left[\mathbb{E}\sum_iY_i-\sum_iY_i\ge t\right]
\le\exp\left(-\frac{2t^2}{\sum_eU_e^2}\right). \tag*{(27)} Pr [ i ∑ Y i − E i ∑ Y i ≥ t ] , Pr [ E i ∑ Y i − i ∑ Y i ≥ t ] ≤ exp ( − ∑ e U e 2 2 t 2 ) . (27)
When the denominator is zero the random sum is constant and either strict positive-deviation event is empty. Here is a proof, including the bounded-variable estimate. If Y Y Y takes values in [ a , a + u ] [a,a+u] [ a , a + u ] with u > 0 u>0 u > 0 , set m = ( E Y − a ) / u ∈ [ 0 , 1 ] m=(\mathbb{E}Y-a)/u\in[0,1] m = ( E Y − a ) / u ∈ [ 0 , 1 ] . Convexity of the exponential on this interval gives, for s = λ u s=\lambda u s = λ u ,
E e λ ( Y − E Y ) ≤ ( 1 − m ) e − m s + m e ( 1 − m ) s . \mathbb{E}e^{\lambda(Y-\mathbb{E}Y)}
\le(1-m)e^{-ms}+me^{(1-m)s}. E e λ ( Y − E Y ) ≤ ( 1 − m ) e − m s + m e ( 1 − m ) s .
For 0 < m < 1 0<m<1 0 < m < 1 the logarithm of the right side is g ( s ) = log ( 1 − m + m e s ) − m s g(s)=\log(1-m+me^s)-ms g ( s ) = log ( 1 − m + m e s ) − m s . It satisfies g ( 0 ) = g ′ ( 0 ) = 0 g(0)=g'(0)=0 g ( 0 ) = g ′ ( 0 ) = 0 and
g ′ ′ ( s ) = q s ( 1 − q s ) ≤ 1 4 , q s = m e s 1 − m + m e s . g''(s)=q_s(1-q_s)\le\frac14,\qquad q_s=\frac{me^s}{1-m+me^s}. g ′′ ( s ) = q s ( 1 − q s ) ≤ 4 1 , q s = 1 − m + m e s m e s .
Integrating this bound twice gives g ( s ) ≤ s 2 / 8 g(s)\le s^2/8 g ( s ) ≤ s 2 /8 for s ≥ 0 s\ge0 s ≥ 0 . The cases m = 0 , 1 m=0,1 m = 0 , 1 or u = 0 u=0 u = 0 are constant and satisfy the same estimate.
Now group all terms with parent e e e into one variable. The grouped variables are independent across original labels, and each has range length at most U e U_e U e . Multiplying the preceding moment bounds and applying Markov’s inequality gives exp ( − λ t + λ 2 ∑ e U e 2 / 8 ) \exp(-\lambda t+\lambda^2\sum_eU_e^2/8) exp ( − λ t + λ 2 ∑ e U e 2 /8 ) for every λ > 0 \lambda>0 λ > 0 . If ∑ e U e 2 > 0 \sum_eU_e^2>0 ∑ e U e 2 > 0 , choose λ = 4 t / ∑ e U e 2 \lambda=4t/\sum_eU_e^2 λ = 4 t / ∑ e U e 2 to obtain the upper tail in (27). Applying the same argument to − Y i -Y_i − Y i proves the lower tail. The zero-range case was handled above.
We repeatedly use the deterministic implication
U e ≤ K for all e , ∑ e U e ≤ S ⟹ ∑ e U e 2 ≤ K S . (28) U_e\le K\ \text{for all }e,\qquad\sum_eU_e\le S
\quad\Longrightarrow\quad
\sum_eU_e^2\le KS. \tag*{(28)} U e ≤ K for all e , e ∑ U e ≤ S ⟹ e ∑ U e 2 ≤ K S . (28)
Only nonconstant terms enter U e U_e U e . In particular, arbitrarily many vertices with deterministic indicators contribute zero range.
Actual local load events
Fix a construction ℓ \ell ℓ and center c c c . For an outside vertex x x x , use the corresponding primary or secondary flag σ \sigma σ and set h ^ x σ = h x σ \widehat{h}^{\sigma}_x=h^{\sigma}_x h x σ = h x σ if h x σ > 0 h^{\sigma}_x>0 h x σ > 0 , and one otherwise. Dropping the sender indicator in (18) yields the pointwise inequality
c x ℓ ≤ T c ℓ : = ∑ x w c x h ^ x σ R x σ . (29) c^\ell_x\le T^\ell_c:=\sum_x\frac{w_{cx}}{\widehat{h}^{\sigma}_x}R^\sigma_x. \tag*{(29)} c x ℓ ≤ T c ℓ := x ∑ h x σ w c x R x σ . (29)
The mean of the summand is w c x w_{cx} w c x when h x o > 0 h_x^o>0 h x o > 0 and zero otherwise. Hence E T c ℓ ≤ 1 \mathbb{E}T_c^\ell\le1 E T c ℓ ≤ 1 by Lemma B.1. Every coefficient is at most 3 w c x ≤ 300 / β 3w_{cx}\le300/\beta 3 w c x ≤ 300/ β , and their sum is at most three. For a fixed original parent, at most 2 κ 2\kappa 2 κ outside endpoints have a nonconstant receiver indicator: each benchmark copy has at most two endpoints. Thus its grouped range is at most 600 κ / β 600\kappa/\beta 600 κ / β , and the sum of grouped ranges is at most three. (28) gives
∑ e ( U e r o w ) 2 ≤ 1800 κ β . (30) \sum_e (U_e^{\mathrm{row}})^2 \le\frac{1800\kappa}{\beta}. \tag*{(30)} e ∑ ( U e row ) 2 ≤ β 1800 κ . (30)
It follows that the actual row exceeds 1 + ε 1+\varepsilon 1 + ε with probability at most exp ( − ε 2 β / ( 900 κ ) ) \exp(-\varepsilon^2\beta/(900\kappa)) exp ( − ε 2 β / ( 900 κ )) . For a fixed outside vertex x x x and flag σ \sigma σ , define the unscaled sender sum
T x σ = ∑ c w c x S c σ , E T x σ = m x σ . T_x^\sigma=\sum_c w_{cx}S_c^\sigma,\qquad\mathbb{E}T_x^\sigma=m_x^\sigma. T x σ = c ∑ w c x S c σ , E T x σ = m x σ .
Its coefficients are at most 1 / ( β d x ) 1/(\beta d_x) 1/ ( β d x ) and sum to at most 1 / d x 1/d_x 1/ d x . At most 2 κ 2\kappa 2 κ centers with a given parent have nonconstant sender indicators, including both endpoints of a missing internal pair. Therefore
∑ e ( U e c o l ) 2 ≤ 2 κ β d x 2 . (31) \sum_e (U_e^{\mathrm{col}})^2\le\frac{2\kappa}{\beta d_x^2}. \tag*{(31)} e ∑ ( U e col ) 2 ≤ β d x 2 2 κ . (31)
Hoeffding with tolerance ε / d x \varepsilon/d_x ε / d x shows that T x σ < m x σ − ε / d x T_x^\sigma<m_x^\sigma-\varepsilon/d_x T x σ < m x σ − ε / d x has probability at most exp ( − ε 2 β / κ ) \exp(-\varepsilon^2\beta/\kappa) exp ( − ε 2 β / κ ) . Whenever x x x is live, its actual raw column is exactly T x σ / h x σ T_x^\sigma/h_x^\sigma T x σ / h x σ . Consequently, on the complementary event,
∑ c f c x ℓ ≥ m x σ h x σ − ε d x h x σ ≥ m x σ h x σ − 300 ε . (32) \sum_c f_{cx}^{\ell}\ge\frac{m_x^\sigma}{h_x^\sigma}-\frac{\varepsilon}{d_xh_x^\sigma}\ge\frac{m_x^\sigma}{h_x^\sigma}-300\varepsilon. \tag*{(32)} c ∑ f c x ℓ ≥ h x σ m x σ − d x h x σ ε ≥ h x σ m x σ − 300 ε . (32)
We used d x ≥ 1 / 100 d_x\ge1/100 d x ≥ 1/100 and h x σ ≥ 1 / 3 h_x^\sigma\ge1/3 h x σ ≥ 1/3 . These arguments require no conditioning on the clock of c c c or x x x . The row bound drops the sender indicator before taking an expectation. The column sum is concentrated unconditionally, and its implication for a live receiver is pointwise. Hence an incidence whose endpoints share the same original parent causes no bias. It is already accounted for in the grouped ranges. For both event types we will use the common weaker bound
q l o c = exp ( − ε 2 β 4000 κ ) . (33) q_{\mathrm{loc}}=\exp\left(-\frac{\varepsilon^2\beta}{4000\kappa}\right). \tag*{(33)} q loc = exp ( − 4000 κ ε 2 β ) . (33)
Low unmatched leaves and the local error sum
Define
O l o w = { x ∈ O : ∑ c w c x ≤ 1 } . O_{\mathrm{low}}=\left\{x\in O:\sum_c w_{cx}\le1\right\}. O low = { x ∈ O : c ∑ w c x ≤ 1 } .
Every unmatched vertex with a x ≤ 1 / 2 a_x\le1/2 a x ≤ 1/2 belongs to this set, because a x / d x ≤ a x / ( 1 − a x ) ≤ 1 a_x/d_x\le a_x/(1-a_x)\le1 a x / d x ≤ a x / ( 1 − a x ) ≤ 1 . A vertex of O l o w O_{\mathrm{low}} O low is always live, has normalization one, and has actual raw load at most ∑ c w c x ≤ 1 \sum_c w_{cx}\le1 ∑ c w c x ≤ 1 in either construction. We therefore retain its raw load without an individual lower-load event.
Call the remaining outside vertices significant. There are at most b b b vertices in O ∖ O l o w O\setminus O_{\mathrm{low}} O ∖ O low : each contributes more than one to the sum ∑ x ∑ c w c x \sum_x\sum_c w_{cx} ∑ x ∑ c w c x , which is at most b b b by the center capacities. The matched outside vertices number 2 r + ∣ M ∣ + ∣ G ∣ ≤ 2 μ 2r+|M|+|G|\le2\mu 2 r + ∣ M ∣ + ∣ G ∣ ≤ 2 μ . On the branch b ≤ μ b\le\mu b ≤ μ , the total number of significant receivers is at most 3 μ 3\mu 3 μ . There are therefore at most 2 b + 2 ( 3 μ ) ≤ 8 μ 2b+2(3\mu)\le8\mu 2 b + 2 ( 3 μ ) ≤ 8 μ local events, including both constructions.
For a significant receiver define
Y x σ = R x σ min { m x σ , h x σ } h x σ , Y_x^\sigma= R_x^\sigma\frac{\min\{m_x^\sigma,h_x^\sigma\}}{h_x^\sigma}, Y x σ = R x σ h x σ min { m x σ , h x σ } ,
with value zero if h x σ = 0 h_x^\sigma=0 h x σ = 0 . For a low unmatched receiver use its actual raw column instead. Let Y Y Y be the sum of these mixed contributions over the two constructions and all outside vertices. The elementary inequality
u ≥ v − e , e ≥ 0 ⟹ min { u , 1 } ≥ min { v , 1 } − e u \ge v-e,\ e \ge0 \quad\Longrightarrow\quad\min\{u,1\} \ge\min\{v,1\}-e u ≥ v − e , e ≥ 0 ⟹ min { u , 1 } ≥ min { v , 1 } − e
follows by comparing with each of the two terms in the minimum. Also, for h > 0 h>0 h > 0 , min { m / h , 1 } = min { m , h } / h \min\{m/h,1\}=\min\{m,h\}/h min { m / h , 1 } = min { m , h } / h . Thus (32) bounds the clipped load below by Y x σ − 300 ε Y_x^\sigma-300\varepsilon Y x σ − 300 ε at a significant live receiver. At a nonlive receiver the target is zero and the same lower bound holds. At a low receiver the clipped load equals the raw load exactly.
On all local events, each center overload in (20) is at most ε \varepsilon ε . Across the two constructions the total error is consequently at most
E l o c ≤ 2 b ε + 2 ( 3 μ ) ( 300 ε ) ≤ 1802 ε μ ≤ 2000 ε μ . (34) E_{\mathrm{loc}} \le2b\varepsilon+ 2(3\mu)(300\varepsilon) \le1802\varepsilon\mu\le2000\varepsilon\mu. \tag*{(34)} E loc ≤ 2 b ε + 2 ( 3 μ ) ( 300 ε ) ≤ 1802 ε μ ≤ 2000 ε μ . (34)
Combining the two actual rank bounds gives
ν ( D 0 ) + ν ( D 1 ) ≥ 2 g + Y − E l o c . (35) \nu(D_0)+\nu(D_1) \ge2g+Y-E_{\mathrm{loc}}. \tag*{(35)} ν ( D 0 ) + ν ( D 1 ) ≥ 2 g + Y − E loc . (35)
This is the reason low leaves are aggregated rather than assigned an error separately: ∣ O l o w ∣ |O_{\mathrm{low}}| ∣ O low ∣ can be arbitrarily large.
The exact aggregate mean and its block ranges
We now express Y Y Y as a sum of functions of individual original clocks. For a significant receiver, the coefficient
γ x σ = min { m x σ , h x σ } h x σ \gamma_x^\sigma=\frac{\min\{m_x^\sigma,h_x^\sigma\}}{h_x^\sigma} γ x σ = h x σ min { m x σ , h x σ }
lies in [ 0 , 1 ] [0,1] [ 0 , 1 ] , with zero used at h x σ = 0 h_x^\sigma=0 h x σ = 0 . Its contribution is γ x σ R x σ \gamma_x^\sigma R_x^\sigma γ x σ R x σ . Its mean is exactly min { m x σ , h x σ } \min\{m_x^\sigma,h_x^\sigma\} min { m x σ , h x σ } , including the zero-capacity case.
For the low receivers put
A c = ∑ x ∈ O l o w w c x , 0 ≤ A c ≤ 1. A_c=\sum_{x\in O_{\mathrm{low}}}w_{cx},\qquad0\le A_c\le1. A c = x ∈ O low ∑ w c x , 0 ≤ A c ≤ 1.
They are always live and have capacity one. Summing their raw support over both constructions and interchanging the finite sums gives the exact identity
∑ ℓ = 0 1 ∑ σ ∑ x ∈ O l o w ∑ c f c x ℓ = ∑ c A c ( S c + + S c − ) . (36) \sum_{\ell=0}^{1}\sum_{\sigma}\sum_{x\in O_{\mathrm{low}}}\sum_c f_{cx}^{\ell}=\sum_c A_c(S_c^+ + S_c^-). \tag*{(36)} ℓ = 0 ∑ 1 σ ∑ x ∈ O low ∑ c ∑ f c x ℓ = c ∑ A c ( S c + + S c − ) . (36)
For each incidence the two constructions correspond to the two flags, so this identity does not require all receivers to lie on the same side of the analytic cut. Each term on the right uses only the sender’s original clock. Moreover m x σ ≤ ∑ c w c x ≤ 1 m_x^\sigma\le\sum_c w_{cx}\le1 m x σ ≤ ∑ c w c x ≤ 1 at a low receiver, so its contribution to (23) is m x + + m x − m_x^+ + m_x^- m x + + m x − . Taking expectations in (36) proves
E Y = Ψ . (37) \mathbb{E}Y=\Psi. \tag*{(37)} E Y = Ψ. (37)
In particular, we never replace the mean of a product of correlated sender and receiver indicators by a product of their means.
Every coefficient in the resulting representation of Y Y Y lies in [ 0 , 1 ] [0,1] [ 0 , 1 ] . The only potentially nonconstant signals are listed below.
Table 6.
Available internal pairs, plain centers, and unmatched receiver signals are deterministic. A zero coefficient only decreases the range. Thus a parent block has range at most 2 κ 2\kappa 2 κ , and the sum of block ranges is at most 2 ( r + ∣ G ∣ + ∣ M ∣ + z J ) ≤ 2 μ 2(r+|G|+|M|+z_J)\le2\mu 2 ( r + ∣ G ∣ + ∣ M ∣ + z J ) ≤ 2 μ . Therefore
∑ e ( U e a g g ) 2 ≤ 4 κ μ . (38) \sum_e (U_e^{\mathrm{agg}})^2 \le4\kappa\mu. \tag*{(38)} e ∑ ( U e agg ) 2 ≤ 4 κ μ . (38)
This calculation counts both endpoints of internal pairs and permits copies of one parent to belong to different types.
Each of g , ℓ R , ℓ M , ℓ J g,\ell_R,\ell_M,\ell_J g , ℓ R , ℓ M , ℓ J is also a sum over copied benchmark pairs. In any one count, a parent block has range at most κ \kappa κ , and the sum of block ranges is at most μ \mu μ . Each count therefore has squared-range sum at most κ μ \kappa\mu κ μ . For any t > 0 t>0 t > 0 , Hoeffding proves the following five inequalities jointly, except with probability at most 5 exp ( − 2 t 2 / ( κ μ ) ) 5\exp(-2t^2/(\kappa\mu)) 5 exp ( − 2 t 2 / ( κ μ )) :
g ≥ α ∣ G ∣ − t , ℓ R ≥ ( 1 − ω ) r − t , ℓ M ≥ ( 1 − ω ) ∣ M ∣ − t , ℓ J ≥ ( 1 − ω ) z J − t , Y ≥ Ψ − 2 t . (39) \begin{aligned}
g &\ge\alpha|G|-t, & \ell_R &\ge(1-\omega)r-t,\\
\ell_M &\ge(1-\omega)|M|-t, & \ell_J &\ge(1-\omega)z_J-t,\\
Y &\ge\Psi-2t. \tag*{(39)}
\end{aligned} g ℓ M Y ≥ α ∣ G ∣ − t , ≥ ( 1 − ω ) ∣ M ∣ − t , ≥ Ψ − 2 t . ℓ R ℓ J ≥ ( 1 − ω ) r − t , ≥ ( 1 − ω ) z J − t , (39)
The fifth bound uses (38) ; the other four use κ μ \kappa\mu κ μ . No independence between these five events is claimed or needed.
The finite fixed-host theorem
Theorem B.3 (Finite typed repair). Suppose the fixed instance above satisfies (17) for every realization, 0 < μ ≤ N 0<\mu\le N 0 < μ ≤ N , N ≥ 1 N\ge1 N ≥ 1 , and b ≤ μ b\le\mu b ≤ μ . For 0 < δ 0 ≤ 1 0<\delta_0\le1 0 < δ 0 ≤ 1 put
θ = δ 0 100 , L = ⌈ log 2 N θ ⌉ . \theta=\frac{\delta_0}{100},\qquad L=\left\lceil\log_2\frac{N}{\theta}\right\rceil. θ = 100 δ 0 , L = ⌈ log 2 θ N ⌉ . If
β ≥ 10 30 κ L 2 , μ ≥ 49 100 β (40) \beta\ge\frac{10^{30}\kappa L}{2},\qquad\mu\ge\frac{49}{100}\beta \tag*{(40)} β ≥ 2 1 0 30 κ L , μ ≥ 100 49 β (40) then
Pr [ V < max { b , F − 10 − 7 μ } ] ≤ δ 0 20 . (41) \Pr\left[V<\max\{b,F-10^{-7}\mu\}\right]\le\frac{\delta_0}{20}. \tag*{(41)} Pr [ V < max { b , F − 1 0 − 7 μ } ] ≤ 20 δ 0 . (41)
Proof. Since log 2 < 1 \log2<1 log 2 < 1 and N / θ ≥ 100 N/\theta\ge100 N / θ ≥ 100 , we have L ≥ log ( N / θ ) > 0 L\ge\log(N/\theta)>0 L ≥ log ( N / θ ) > 0 . Thus q = e − L ≤ θ / N ≤ 1 / 100 q=e^{-L}\le\theta/N\le1/100 q = e − L ≤ θ / N ≤ 1/100 . By (40) and ε = 10 − 12 \varepsilon=10^{-12} ε = 1 0 − 12 ,
ε 2 β 4000 κ ≥ 125 L . \frac{\varepsilon^2\beta}{4000\kappa}\ge125L. 4000 κ ε 2 β ≥ 125 L .
The union of all local failures has probability at most
8 μ e − 125 L ≤ 8 N q 2 ≤ 4 N q ≤ 4 θ . 8\mu e^{-125L} \le8Nq^2 \le4Nq \le4\theta. 8 μ e − 125 L ≤ 8 N q 2 ≤ 4 N q ≤ 4 θ .
Here q ≤ 1 / 2 q \le1/2 q ≤ 1/2 was sufficient for the middle inequality. Set t = κ μ L t=\sqrt{\kappa\mu L} t = κ μL . The five aggregate failures have total probability at most
5 e − 2 L = 5 q 2 ≤ 5 θ 2 ≤ θ . 5e^{-2L}=5q^2 \le5\theta^2 \le\theta. 5 e − 2 L = 5 q 2 ≤ 5 θ 2 ≤ θ .
On the complement of these events, combine (17) , (35) , (26) , and (39) to obtain
2 V ≥ ∣ G ∣ + g + ℓ R + ℓ M + z I + ℓ J + Y − E l o c ≥ ( 1 + α ) ∣ G ∣ + ( 1 − ω ) ( r + ∣ M ∣ + z J ) + z I + Ψ − 6 t − E l o c = 2 F − 6 t − E l o c . \begin{aligned}
2V &\ge|G|+g+\ell_R+\ell_M+z_I+\ell_J+Y-E_{\mathrm{loc}}\\
&\ge(1+\alpha)|G|+(1-\omega)(r+|M|+z_J)+z_I+\Psi-6t-E_{\mathrm{loc}}\\
&=2F-6t-E_{\mathrm{loc}}.
\end{aligned} 2 V ≥ ∣ G ∣ + g + ℓ R + ℓ M + z I + ℓ J + Y − E loc ≥ ( 1 + α ) ∣ G ∣ + ( 1 − ω ) ( r + ∣ M ∣ + z J ) + z I + Ψ − 6 t − E loc = 2 F − 6 t − E loc .
Together with V ≥ b V\ge b V ≥ b and (34) , this gives
V ≥ max { b , F − 1000 ε μ − 3 κ μ L } . (42) V\ge\max\{b,F-1000\varepsilon\mu-3\sqrt{\kappa\mu L}\}. \tag*{(42)} V ≥ max { b , F − 1000 ε μ − 3 κ μL } . (42)
The size conditions imply
μ ≥ 49 ⋅ 10 30 200 κ L ≥ 10 20 κ L , \mu\ge\frac{49\cdot10^{30}}{200}\kappa L\ge10^{20}\kappa L, μ ≥ 200 49 ⋅ 1 0 30 κ L ≥ 1 0 20 κ L ,
so κ μ L ≤ 10 − 10 μ \sqrt{\kappa\mu L}\le10^{-10}\mu κ μL ≤ 1 0 − 10 μ . In particular, even the larger reserve satisfies
2000 ε μ + 40 κ μ L ≤ ( 2 ⋅ 10 − 9 + 4 ⋅ 10 − 9 ) μ < 10 − 7 μ . 2000\varepsilon\mu+40\sqrt{\kappa\mu L}\le(2\cdot10^{-9}+4\cdot10^{-9})\mu<10^{-7}\mu. 2000 ε μ + 40 κ μL ≤ ( 2 ⋅ 1 0 − 9 + 4 ⋅ 1 0 − 9 ) μ < 1 0 − 7 μ .
This bounds the error in (42) . The total failure probability is at most 4 θ + θ = δ 0 / 20 4\theta+\theta=\delta_0/20 4 θ + θ = δ 0 /20 .
The lower-size condition in (40) is available on the nontrivial branch of the final algorithm. Indeed, the benchmark partition gives r ≥ μ − b r\ge\mu-b r ≥ μ − b . If b < 0.714 μ b<0.714\mu b < 0.714 μ , then r > 0.286 μ > 0 r>0.286\mu>0 r > 0.286 μ > 0 . A root edge is missing from the complete reference-plus-underfull graph, because both its endpoints lie outside its cover. The missing-edge degree condition gives the sum of its reference degrees at least ( 1 − 10 − 8 ) β (1-10^{-8})\beta ( 1 − 1 0 − 8 ) β . One endpoint therefore has at least 0.49 β 0.49\beta 0.49 β reference neighbors. All of these neighbors lie in C C C , so b ≥ 0.49 β b\ge0.49\beta b ≥ 0.49 β and hence μ ≥ 0.49 β \mu\ge0.49\beta μ ≥ 0.49 β . On the other branch, the base value V ≥ b V\ge b V ≥ b already supplies the stated approximation target.
The theorem is a conditional fixed-reference calculation: its data are fixed before the suffix-label categories are sampled. The permutation coupling and cutoff bracket proved in the streaming analysis identify these categories with the actual suffix experiment. The acquisition, prefix-preservation, and cutoff failure allowances are added there. Neither the two-stage repair nor the concentration proof assumes independence of copied edges, and neither introduces an error proportional to the number of low unmatched leaves.
The finite profile relaxation and its certificate
This section specifies the linear program used in theorem 5.2 and the map from actual graphs to its variables. Counts are divided by μ \mu μ and reference-edge counts by β μ \beta\mu β μ . We may assume μ > 0 \mu>0 μ > 0 and max ( b , F ) < μ \max(b,F)<\mu max ( b , F ) < μ ; the omitted cases are immediate.
Degree classes and affine choices
Let 0 = g 0 < g 1 < ⋯ < g 152 = 1 0 = g_0 < g_1 < \cdots< g_{152} = 1 0 = g 0 < g 1 < ⋯ < g 152 = 1 be the grid whose numerators, with common denominator 512, are
0 , 2 , 4 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 18 , 20 , 22 , 24 , 28 , 32 , 40 , 48 , 56 , 60 , 64 , 72 , 80 , 84 , 88 , 92 , 96 , 100 , 104 , 108 , 112 , 114 , 116 , 118 , 120 , 122 , 124 , 126 , 128 , 132 , 136 , 140 , 142 , 144 , 148 , 152 , 156 , 160 , 164 , 168 , 176 , 184 , 192 , 196 , 200 , 204 , 208 , 212 , 216 , 220 , 222 , 224 , 228 , 232 , 236 , 240 , 242 , 244 , 248 , 250 , 252 , 254 , 256 , 258 , 260 , 262 , 264 , 268 , 270 , 272 , 276 , 280 , 284 , 288 , 290 , 292 , 296 , 300 , 304 , 308 , 312 , 316 , 320 , 328 , 336 , 344 , 348 , 352 , 356 , 360 , 364 , 368 , 370 , 372 , 376 , 380 , 384 , 386 , 388 , 390 , 392 , 394 , 396 , 398 , 400 , 404 , 408 , 412 , 416 , 420 , 424 , 428 , 432 , 440 , 448 , 452 , 456 , 464 , 472 , 480 , 484 , 488 , 490 , 492 , 494 , 496 , 497 , 498 , 499 , 500 , 501 , 502 , 503 , 504 , 505 , 506 , 508 , 510 , 512. \begin{aligned}
&0, 2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 22, 24, 28, 32,\\
&40, 48, 56, 60, 64, 72, 80, 84, 88, 92, 96, 100, 104, 108, 112, 114, 116, 118,\\
&120, 122, 124, 126, 128, 132, 136, 140, 142, 144, 148, 152, 156, 160, 164, 168,\\
&176, 184, 192, 196, 200, 204, 208, 212, 216, 220, 222, 224, 228, 232, 236, 240,\\
&242, 244, 248, 250, 252, 254, 256, 258, 260, 262, 264, 268, 270, 272, 276, 280,\\
&284, 288, 290, 292, 296, 300, 304, 308, 312, 316, 320, 328, 336, 344, 348, 352,\\
&356, 360, 364, 368, 370, 372, 376, 380, 384, 386, 388, 390, 392, 394, 396, 398,\\
&400, 404, 408, 412, 416, 420, 424, 428, 432, 440, 448, 452, 456, 464, 472, 480,\\
&484, 488, 490, 492, 494, 496, 497, 498, 499, 500, 501, 502, 503, 504, 505, 506,\\
&508, 510, 512.
\end{aligned} 0 , 2 , 4 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 18 , 20 , 22 , 24 , 28 , 32 , 40 , 48 , 56 , 60 , 64 , 72 , 80 , 84 , 88 , 92 , 96 , 100 , 104 , 108 , 112 , 114 , 116 , 118 , 120 , 122 , 124 , 126 , 128 , 132 , 136 , 140 , 142 , 144 , 148 , 152 , 156 , 160 , 164 , 168 , 176 , 184 , 192 , 196 , 200 , 204 , 208 , 212 , 216 , 220 , 222 , 224 , 228 , 232 , 236 , 240 , 242 , 244 , 248 , 250 , 252 , 254 , 256 , 258 , 260 , 262 , 264 , 268 , 270 , 272 , 276 , 280 , 284 , 288 , 290 , 292 , 296 , 300 , 304 , 308 , 312 , 316 , 320 , 328 , 336 , 344 , 348 , 352 , 356 , 360 , 364 , 368 , 370 , 372 , 376 , 380 , 384 , 386 , 388 , 390 , 392 , 394 , 396 , 398 , 400 , 404 , 408 , 412 , 416 , 420 , 424 , 428 , 432 , 440 , 448 , 452 , 456 , 464 , 472 , 480 , 484 , 488 , 490 , 492 , 494 , 496 , 497 , 498 , 499 , 500 , 501 , 502 , 503 , 504 , 505 , 506 , 508 , 510 , 512.
A center class c = ( i , t ) c = (i,t) c = ( i , t ) specifies its degree interval and type t ∈ { G , M , P , I , J } t \in\{G, M, P, I, J\} t ∈ { G , M , P , I , J } . An outside class x = ( i , u , h ) x = (i,u,h) x = ( i , u , h ) specifies its interval, type u ∈ { S , T , A , O } u \in\{S, T, A, O\} u ∈ { S , T , A , O } and a mask h h h selecting the constant or load arm of each minimum. There are two arms for type A A A and four for the other types. For type O O O in intervals with g i + 1 ≤ 1 / 2 g_{i+1} \le1/2 g i + 1 ≤ 1/2 , only the all-load choice is needed.
For an actual vertex in interval i i i , replace its reference reciprocal by q i = 1 / max { 1 / 100 , 1 − g i } q_i = 1/\max\{1/100, 1-g_i\} q i = 1/ max { 1/100 , 1 − g i } . This does not increase any load. Choose its mask to attain each minimum of the resulting loads; ties use a fixed rule. Group vertices by these choices. For a low-interval unmatched vertex, each lowered load is at most a x / ( 1 − g i ) ≤ 1 a_x/(1-g_i) \le1 a x / ( 1 − g i ) ≤ 1 , so the restricted mask is valid.
Variables and constraints
Let C c , O x C_c, O_x C c , O x count the center and outside classes. Let E c x E_{cx} E c x count reference edges between their classes. Let H c d H_{cd} H c d count reference edges within the cover, with unordered endpoints c ≤ d c \le d c ≤ d . Let R x y R_{xy} R x y count root pairs, Q c x Q_{cx} Q c x missing crossing pairs, and P c d P_{cd} P c d internal benchmark pairs. The latter use two I I I classes or two J J J classes. Their total is z z z . Finally let v v v be the value variable. All variables are nonnegative.
An internal edge or pair with both endpoints in one class contributes twice to that class’s endpoint count. Define reference incidences
D c = ∑ x E c x + ∑ a b ( [ a = c ] + [ b = c ] ) H a b , D x = ∑ c E c x . D_c = \sum_x E_{cx} + \sum_{ab}([a=c] + [b=c])H_{ab}, \qquad D_x = \sum_c E_{cx}. D c = x ∑ E c x + ab ∑ ([ a = c ] + [ b = c ]) H ab , D x = c ∑ E c x .
For every class in interval i i i , impose
g i C c ≤ D c ≤ g i + 1 C c , g i O x ≤ D x ≤ g i + 1 O x . g_i C_c \le D_c \le g_{i+1} C_c, \qquad g_i O_x \le D_x \le g_{i+1} O_x. g i C c ≤ D c ≤ g i + 1 C c , g i O x ≤ D x ≤ g i + 1 O x .
The exact endpoint equalities are as follows:
∑ c : t ∈ { G , M } C c + ∑ x y R x y + z = 1 \sum_{c:t\in\{G,M\}} C_c + \sum_{xy} R_{xy} + z = 1 ∑ c : t ∈ { G , M } C c + ∑ x y R x y + z = 1 .
Only admissible edge classes are present: a reference pair has lower interval endpoints summing to at most one; a root or missing benchmark pair, including an internal type-J J J pair, has upper endpoints summing to at least 1 − 10 − 8 1 - 10^{-8} 1 − 1 0 − 8 ; an available internal pair has lower endpoints summing to at most one. This last condition uses the available-pair degree bound, not a lower bound on available gates.
The two additional moment constraints are
∑ x : u = S D x ≥ ( 1 − 10 − 8 ) ∑ x y R x y , ∑ c : t = M D c + ∑ x : u = T D x ≥ ( 1 − 10 − 8 ) ∑ c : t = M C c . \sum_{x:u=S} D_x \ge(1 - 10^{-8})\sum_{xy} R_{xy}, \qquad\sum_{c:t=M} D_c + \sum_{x:u=T} D_x \ge(1 - 10^{-8})\sum_{c:t=M} C_c. x : u = S ∑ D x ≥ ( 1 − 1 0 − 8 ) x y ∑ R x y , c : t = M ∑ D c + x : u = T ∑ D x ≥ ( 1 − 1 0 − 8 ) c : t = M ∑ C c .
When a reference edge has two missing-center endpoints, both incidences are included. Each inequality is obtained by summing actual degree bounds over disjoint benchmark pairs.
For the phase row, put ℓ G = p \ell_G=p ℓ G = p and ℓ t = 1 \ell_t=1 ℓ t = 1 for other center types; put b M = b J = ω b_M=b_J=\omega b M = b J = ω , b P = 1 b_P=1 b P = 1 , and b G = b I = 0 b_G=b_I=0 b G = b I = 0 . For a type-S S S or type-T T T outside class the two load rates are ( ℓ t , b t ) (\ell_t,b_t) ( ℓ t , b t ) and caps ( ω , 1 ) (\omega,1) ( ω , 1 ) ; for type O O O the same rates have caps ( 1 , 1 ) (1,1) ( 1 , 1 ) ; type A A A uses only rate b t b_t b t and cap p p p . A mask-selected constant arm contributes its cap times O x O_x O x . A load arm contributes q i q_i q i times the corresponding rate-weighted sum of E c x E_{cx} E c x . Let F \mathcal{F} F be half the sum of these outside terms, plus
1 + α 2 ∑ c : t = G C c + 1 − ω 2 ∑ c : t = M C c + 1 − ω 2 ∑ x y R x y + 1 2 ∑ c d : t = I P c d + 1 − ω 2 ∑ c d : t = J P c d . \frac{1+\alpha}{2}\sum_{c:t=G} C_c+\frac{1-\omega}{2}\sum_{c:t=M} C_c+\frac{1-\omega}{2}\sum_{xy} R_{xy}+\frac{1}{2}\sum_{cd:t=I} P_{cd}+\frac{1-\omega}{2}\sum_{cd:t=J} P_{cd}. 2 1 + α c : t = G ∑ C c + 2 1 − ω c : t = M ∑ C c + 2 1 − ω x y ∑ R x y + 2 1 c d : t = I ∑ P c d + 2 1 − ω c d : t = J ∑ P c d .
This is exactly the normalized expression in (8) after lowering support weights and selecting its minimizing arms. Impose
v ≥ ∑ c C c , v ≥ F , ∑ c C c ≤ 1 , v ≤ 1. v \ge\sum_c C_c,\qquad v \ge\mathcal{F},\qquad\sum_c C_c \le1,\qquad v \le1. v ≥ c ∑ C c , v ≥ F , c ∑ C c ≤ 1 , v ≤ 1.
The objective is to minimize v v v .
Lemma C.1 (Bounded mass). The total mass of all variables except type-O O O counts in interval zero is at most 267.
Proof. Centers contribute at most one, root endpoints at most two, and missing and available partners at most one each. The total normalized outside degree is at most one: every reference edge incident to an outside vertex also meets a center, and the sum of center degrees is at most β b \beta b β b . Every positive-interval unmatched vertex has degree at least 1 / 256 1/256 1/256 , so their normalized count is at most 256. All reference edges together have mass at most one, because each meets a center and ∑ c d H ( c ) ≤ β b \sum_c d_H(c) \le\beta b ∑ c d H ( c ) ≤ β b . Root pairs, missing pairs, internal pairs, z z z , and v v v each have mass at most one. The sum is 1 + 2 + 1 + 1 + 256 + 1 + 1 + 1 + 1 + 1 + 1 = 267 1+2+1+1+256+1+1+1+1+1+1=267 1 + 2 + 1 + 1 + 256 + 1 + 1 + 1 + 1 + 1 + 1 = 267 . No bound is placed on the number of unmatched vertices in interval zero. □
The program also imposes this bounded-mass inequality as a row, with right-hand side 267 and coefficient zero on the excluded unmatched interval-zero count.
Lemma C.2 (Actual graph feasibility). The counts of every actual graph profile in § 5 , with the interval and mask choices above, satisfy all these constraints. Taking v = max { b , F } / μ v=\max\{b,\mathcal{F}\}/\mu v = max { b , F } / μ gives a feasible objective value.
Proof. Each endpoint equality counts the two endpoints of the corresponding actual benchmark pairs. The reference incidence definitions count every actual edge exactly once and both endpoints of an internal edge, giving the degree rows. The reference and benchmark degree conditions imply admissibility and the two moment inequalities. The mass row is theorem C.1. Lowering the nonnegative support weights cannot increase any minimum, so F ≤ F / μ \mathcal{F}\le F/\mu F ≤ F / μ . The remaining value rows follow from the assumed branch max ( b , F ) < μ \max(b,F)<\mu max ( b , F ) < μ . □
Exact dual verification
Write this explicit program as minimizing c T x c^{T}x c T x subject to A x = a Ax = a A x = a , B x ≤ b Bx \le b B x ≤ b , and x ≥ 0 x \ge0 x ≥ 0 . A dual pair ( y , z ) (y, z) ( y , z ) with z ≤ 0 z \le0 z ≤ 0 and A T y + B T z ≤ c A^{T}y + B^{T}z \le c A T y + B T z ≤ c proves c T x ≥ a T y + b T z c^{T}x \ge a^{T}y + b^{T}z c T x ≥ a T y + b T z by multiplying and summing the inequalities. This is the only optimization fact needed for the certificate.
The accompanying file certificates/degree_profile/certificate.json contains the rational dual coordinates in the row order specified by the independent checker certificates/degree_profile/verify.py. The checker reconstructs the preceding row families and all admissible columns directly, without importing the optimizer’s matrix builder. Every coefficient is an integer or a rational number. It checks dual signs, all 996,325 column inequalities and the exact objective
a T y + b T z = 2896371675910694789 4062500000000000000 . a^{T}y + b^{T}z = \frac{2896371675910694789}{4062500000000000000}. a T y + b T z = 4062500000000000000 2896371675910694789 .
The unbounded unmatched interval-zero column has exactly zero slack. Rational rounding of the discovered dual is repaired using the mass row: the maximum pre-repair bounded-column deficit is 1712699 / 12187500000000000000 1712699/12187500000000000000 1712699/12187500000000000000 . Charging this amount against the 267 mass bound makes every bounded column feasible. This allowance is never applied to the unbounded column.
The Lean theorem exact_profile_certificate, in the namespace RandomOrderMatching.Certificates.DegreeProfile.Concrete, independently proves all semantic column inequalities using integer envelopes of the dual coordinates, then applies finite weak duality. The certificate data are proof data; numerical search is not a premise of either verification. Together with theorem C.2, the exact dual bound proves theorem 5.2.
Acquisition and the complete bounded-weight algorithm
We give the operational construction for integer weights in [ W ] [W] [ W ] . If n ≤ 1 n \le1 n ≤ 1 , return the empty matching. Otherwise assume n ≥ 2 n \ge2 n ≥ 2 , W ≥ 1 W \ge1 W ≥ 1 and 0 < δ 0 < 1 0 < \delta_0 < 1 0 < δ 0 < 1 . Write N = n W N = nW N = nW and κ = W \kappa= W κ = W . Original edges are the stream labels; the copies of one original form a batch of size at most κ \kappa κ . All counters and cutoff positions below count original labels. The unweighted case is W = κ = 1 W = \kappa= 1 W = κ = 1 .
For local failure allowance δ 0 \delta_0 δ 0 , set
L = ⌈ log 2 ( 100 N / δ 0 ) ⌉ , β 0 = 10 3 κ L , λ 0 = 10 − 9 , η = 10 − 10 , ρ = 10 − 8 , Q = N β 0 2 + 1. L = \lceil\log_2(100N/\delta_0) \rceil,\quad\beta_0 = 10^{3}\kappa L,\quad\lambda_0 = 10^{-9},\quad\eta= 10^{-10},\quad\rho= 10^{-8},\quad Q = N\beta_0^2 + 1. L = ⌈ log 2 ( 100 N / δ 0 )⌉ , β 0 = 1 0 3 κ L , λ 0 = 1 0 − 9 , η = 1 0 − 10 , ρ = 1 0 − 8 , Q = N β 0 2 + 1.
Use δ U = δ L = δ 0 / 3 \delta_U = \delta_L = \delta_0/3 δ U = δ L = δ 0 /3 and
L U = ⌈ log 2 ( Q / δ U ) ⌉ , Γ B = ⌈ 4 Q L U / ρ ⌉ , Γ E = κ Γ B , L 0 = ⌈ log 2 ( 1 / δ L ) ⌉ . L_U = \lceil\log_2(Q/\delta_U) \rceil,\quad\Gamma_B = \lceil4QL_U/\rho\rceil,\quad\Gamma_E = \kappa\Gamma_B,\quad L_0 = \lceil\log_2(1/\delta_L) \rceil. L U = ⌈ log 2 ( Q / δ U )⌉ , Γ B = ⌈ 4 Q L U / ρ ⌉ , Γ E = κ Γ B , L 0 = ⌈ log 2 ( 1/ δ L )⌉ .
Failure inputs can be rounded down to dyadic numbers within a factor of two. This affects none of the guarantees or asymptotic bounds.
Reference updates and hard caps
For every dyadic integer D ≤ n 2 D \le n^2 D ≤ n 2 with ρ D ≥ 2 Q \rho D \ge2Q ρ D ≥ 2 Q , start a reference instance at the first original edge. Its epochs have a D = ⌊ ρ D / Q ⌋ a_D = \lfloor\rho D/Q \rfloor a D = ⌊ ρ D / Q ⌋ original labels. Process the copies within each label in a fixed order. Initially H = ∅ H = \varnothing H = ∅ . Insert a copied edge u v uv uv when
d H ( u ) + d H ( v ) < ( 1 − λ 0 ) β 0 . d_H(u) + d_H(v) < (1-\lambda_0)\beta_0. d H ( u ) + d H ( v ) < ( 1 − λ 0 ) β 0 .
After each insertion, repeatedly delete an edge whose current endpoint-degree sum exceeds β 0 \beta_0 β 0 , using a fixed tie rule. Freeze at the end of the first complete epoch with no insertion. After freezing, store all subsequent copies underfull at the frozen threshold in U U U , together with their original parents and arrival positions. Subtracting the stored freeze position gives the suffix timestamps. Abort this instance and clear U U U before ∣ U ∣ |U| ∣ U ∣ exceeds Γ E \Gamma_E Γ E . This is a hard cap on every execution.
Lemma D.1 (Acquisition termination). Every cleanup terminates. An instance maintains degree at most β 0 \beta_0 β 0 and has at most N β 0 2 N\beta_0^2 N β 0 2 nonempty epochs before freezing. It therefore freezes by original position Q a D Q_{aD} Q a D , provided that many labels arrive.
Proof. Use
Ψ ( H ) = ( β 0 − 1 2 ) ∑ v d H ( v ) − ∑ v d H ( v ) 2 . \Psi(H) = \left(\beta_0 - \frac{1}{2}\right)\sum_v d_H(v) - \sum_v d_H(v)^2. Ψ ( H ) = ( β 0 − 2 1 ) v ∑ d H ( v ) − v ∑ d H ( v ) 2 . An insertion at old integer endpoint sum s ≤ β 0 − 2 s \le\beta_0 - 2 s ≤ β 0 − 2 increases Ψ \Psi Ψ by 2 β 0 − 2 s − 3 ≥ 1 2\beta_0 - 2s - 3 \ge1 2 β 0 − 2 s − 3 ≥ 1 . A deletion at sum s ≥ β 0 + 1 s \ge\beta_0 + 1 s ≥ β 0 + 1 increases it by 2 s − 2 β 0 − 1 ≥ 1 2s - 2\beta_0 - 1 \ge1 2 s − 2 β 0 − 1 ≥ 1 . An insertion raises each endpoint degree to at most β 0 − 1 \beta_0 - 1 β 0 − 1 ; deletions only decrease degrees. Hence Ψ ≤ N β 0 2 \Psi\le N\beta_0^2 Ψ ≤ N β 0 2 . It starts at zero, and every update increases it, so cleanup terminates. Every epoch before the first empty one contains an insertion, so at most N β 0 2 < Q N\beta_0^2 < Q N β 0 2 < Q epochs can be nonempty. Cleanup gives the upper edge-degree constraint. □
Lemma D.2 (Underfull-cap success). If the input has m 0 m_0 m 0 original labels and D ≤ m 0 < 2 D D \le m_0 < 2D D ≤ m 0 < 2 D , this instance freezes by position ρ m 0 \rho m_0 ρ m 0 and exceeds its underfull cap with probability at most δ U \delta_U δ U .
Proof. The freeze bound follows from Q a D ≤ ρ D Q_{aD} \le\rho D Q a D ≤ ρ D . At an epoch start, condition on its full ordered history. Let T T T be the remaining labels containing a currently underfull copy. Until the first insertion the reference cannot change, so an empty epoch occurs exactly when the next a D a_D a D labels avoid T T T . If ∣ T ∣ > Γ B |T| > \Gamma_B ∣ T ∣ > Γ B , its conditional probability is at most
( 1 − ∣ T ∣ m 0 ) a D ≤ exp ( − a D Γ B 2 D ) ≤ e − L U ≤ δ U Q . \left(1-\frac{|T|}{m_0}\right)^{a_D} \le\exp\left(-\frac{a_D\Gamma_B}{2D}\right) \le e^{-L_U} \le\frac{\delta_U}{Q}. ( 1 − m 0 ∣ T ∣ ) a D ≤ exp ( − 2 D a D Γ B ) ≤ e − L U ≤ Q δ U . Here a D ≥ ρ D / ( 2 Q ) a_D \ge\rho D/(2Q) a D ≥ ρ D / ( 2 Q ) , because ρ D / Q ≥ 2 \rho D/Q \ge2 ρ D / Q ≥ 2 . Integrate over the possible histories and union-bound the at most Q Q Q epoch positions. During the chosen empty epoch H H H is fixed. More than κ Γ B \kappa\Gamma_B κ Γ B underfull suffix copies would therefore require more than Γ B \Gamma_B Γ B remaining labels in T T T , the event just bounded. □
Unknown length and preservation of the benchmark
Maintain a complete original-edge buffer through
T f u l l = max { ⌈ 4 Q / ρ ⌉ , ⌈ 6 n κ L 0 / ρ ⌉ } T_{\mathrm{full}} = \max\{\lceil4Q/\rho\rceil,\lceil6n\kappa L_0/\rho\rceil\} T full = max {⌈ 4 Q / ρ ⌉ , ⌈ 6 nκ L 0 / ρ ⌉}
labels, a label counter, and a greedy fallback matching. Discard the complete buffer before processing label T f u l l + 1 T_{\mathrm{full}}+1 T full + 1 . If it survives to the end, return an exact maximum-weight matching. Otherwise, at the end select the unique dyadic scale D ≤ m 0 < 2 D D \le m_0 < 2D D ≤ m 0 < 2 D . It was active from the first label, since D > m 0 / 2 > T f u l l / 2 ≥ 2 Q / ρ D > m_0/2 > T_{\mathrm{full}}/2 \ge2Q/\rho D > m 0 /2 > T full /2 ≥ 2 Q / ρ . The selected scale depends on the fixed input size, not its order; no union bound over scales is needed.
Fix one maximum-weight original matching M ∗ M^* M ∗ before exposing the permutation, and put μ 0 = w ( M ∗ ) \mu_0 = w(M^*) μ 0 = w ( M ∗ ) . Give each original label its M ∗ M^* M ∗ -weight, either zero or at most κ \kappa κ . Let X X X be the total such weight in the first ⌈ ρ m 0 ⌉ \lceil\rho m_0\rceil ⌈ ρ m 0 ⌉ labels. For a fixed set of s s s labels, the probability all occur in this prefix is at most ρ s \rho^s ρ s . Expanding the product moment, then using 2 x − 1 ≤ x 2^x - 1 \le x 2 x − 1 ≤ x for 0 ≤ x ≤ 1 0 \le x \le1 0 ≤ x ≤ 1 , gives
E 2 X / κ ≤ e ρ μ 0 / κ , Pr [ X > 2 ρ μ 0 ] ≤ e − ρ μ 0 / ( 3 κ ) . \mathbb{E}2^{X/\kappa} \le e^{\rho\mu_0/\kappa}, \qquad\Pr[X > 2\rho\mu_0] \le e^{-\rho\mu_0/(3\kappa)}. E 2 X / κ ≤ e ρ μ 0 / κ , Pr [ X > 2 ρ μ 0 ] ≤ e − ρ μ 0 / ( 3 κ ) .
The second inequality follows by Markov’s inequality and 2 ln 2 − 1 > 1 / 3 2\ln2-1 > 1/3 2 ln 2 − 1 > 1/3 . A positive-weight maximum matching is maximal, so its endpoints cover every original edge. Thus m 0 ≤ 2 n ∣ M ∗ ∣ ≤ 2 n μ 0 m_0 \le2n|M^*| \le2n\mu_0 m 0 ≤ 2 n ∣ M ∗ ∣ ≤ 2 n μ 0 . On the nonexact branch, m 0 > T f u l l m_0 > T_{\mathrm{full}} m 0 > T full implies μ 0 > 3 κ L 0 / ρ \mu_0 > 3\kappa L_0/\rho μ 0 > 3 κ L 0 / ρ ; the displayed failure probability is at most δ L \delta_L δ L .
Let M M M consist of the edges of M ⋆ M^\star M ⋆ outside the actual acquisition prefix. Since the selected freeze lies inside the deterministic prefix used above, on the same good event
μ : = w ( M ) ≥ ( 1 − 2 ρ ) μ 0 . (43) \mu:= w(M) \ge(1 - 2\rho)\mu_0. \tag*{(43)} μ := w ( M ) ≥ ( 1 − 2 ρ ) μ 0 . (43)
Every parent of M M M is a physical suffix label. In particular, no reference edge has a benchmark parent, and no auxiliary clock for a prefix edge is needed.
Condition on any concrete ordered freeze history with positive probability. Every permutation of its remaining original labels extends that history and the stopping decision in exactly one way. Consequently the conditional suffix order is uniform. This fixes the reference, the benchmark, the unordered suffix, the underfull classifier and all analytic graph choices. It does not condition on cap survival, a future phase, a repair event or the output. Fixed-host bounds can therefore be integrated over these histories.
The original-consistent analytic cut
Orient the two original endpoints of each edge of M M M across a random cut, independently for different pairs. Assign unmatched original vertices independent fair sides. Every copy of an original vertex receives its parent’s side, so all ϕ ( M ) \phi(M) ϕ ( M ) edges cross. Fix a copied vertex v i v_i v i . It has at most one reference neighbor with any given original parent: this follows directly from the antidiagonal definition of an unfolded edge and simplicity of the original graph. Condition on the side of v v v . A benchmark pair with two neighbors contributes exactly one crossing edge; one with one neighbor contributes one independent fair Bernoulli variable. An original mate contributes at most one forced edge. Thus for integers b v b_v b v , s v s_v s v and m v ∈ { 0 , 1 } m_v \in\{0,1\} m v ∈ { 0 , 1 } ,
d H ( v i ) = 2 b v + s v + m v , d H ′ ( v i ) = b v + m v + ∑ j = 1 s v X j . d_H(v_i) = 2b_v + s_v + m_v,\qquad d_{H'}(v_i) = b_v + m_v + \sum_{j=1}^{s_v} X_j. d H ( v i ) = 2 b v + s v + m v , d H ′ ( v i ) = b v + m v + j = 1 ∑ s v X j .
Here s v ≤ d H ( v i ) ≤ β 0 s_v \le d_H(v_i) \le\beta_0 s v ≤ d H ( v i ) ≤ β 0 . Hoeffding and a union bound over the N N N copies show that some original-consistent cut satisfies
d H ( v i ) / 2 − η β 0 ≤ d H ′ ( v i ) ≤ d H ( v i ) / 2 + η β 0 + 1 2 for every v i , d_H(v_i)/2 - \eta\beta_0 \le d_{H'}(v_i) \le d_H(v_i)/2 + \eta\beta_0 + \frac{1}{2}\quad\text{for every }v_i, d H ( v i ) /2 − η β 0 ≤ d H ′ ( v i ) ≤ d H ( v i ) /2 + η β 0 + 2 1 for every v i ,
The unconditional proof may union-bound both possible sides of the focal original vertex; the sufficient bound 4 N exp ( − 2 η 2 β 0 ) < 1 4N\exp(-2\eta^2\beta_0) < 1 4 N exp ( − 2 η 2 β 0 ) < 1 still holds. Choose the first such cut in a fixed ordering. It depends only on the frozen unordered data. This is an existence argument, not an additional failure event for the streaming algorithm.
Put β = β 0 / 2 + 2 η β 0 + 1 \beta= \beta_0/2 + 2\eta\beta_0 + 1 β = β 0 /2 + 2 η β 0 + 1 . Restrict H H H , U U U and the remaining non-underfull copies to the chosen cut. Every reference edge and every underfull edge has cut-degree sum at most β \beta β . Every non-underfull crossing edge has sum at least ( 1 − 10 − 8 ) β (1 - 10^{-8})\beta ( 1 − 1 0 − 8 ) β , since
( 1 − λ 0 ) β 0 / 2 − 2 η β 0 − ( 1 − 10 − 8 ) ( β 0 / 2 + 2 η β 0 + 1 ) = 4.100000002 ⋅ 10 − 9 β 0 − ( 1 − 10 − 8 ) > 0. (1-\lambda_0)\beta_0/2 - 2\eta\beta_0 - (1-10^{-8})(\beta_0/2 + 2\eta\beta_0 + 1) = 4.100000002\cdot10^{-9}\beta_0 - (1-10^{-8}) > 0. ( 1 − λ 0 ) β 0 /2 − 2 η β 0 − ( 1 − 1 0 − 8 ) ( β 0 /2 + 2 η β 0 + 1 ) = 4.100000002 ⋅ 1 0 − 9 β 0 − ( 1 − 1 0 − 8 ) > 0.
These are exactly the reference and pair-degree conditions used in the repair profile. The benchmark has μ \mu μ copies, all crossing this same original-vertex cut.
Causal cutoffs and the designated phase
After freezing, keep a complete suffix buffer for the first 10 7 10^{7} 1 0 7 original labels, and launch phases at reached cutoffs
c 1 = 1 , c j + 1 = ⌈ ( 1 + γ ) c j ⌉ , γ = 10 − 7 . c_1 = 1,\qquad c_{j+1} = \lceil(1+\gamma)c_j\rceil,\qquad\gamma= 10^{-7}. c 1 = 1 , c j + 1 = ⌈( 1 + γ ) c j ⌉ , γ = 1 0 − 7 .
Initialize and update each phase as in § 3 . Its initial base is copied from the shared parent records with timestamps at most c c c ; it is never initialized retroactively. Discard the suffix buffer before processing its ( 10 7 + 1 ) (10^{7}+1) ( 1 0 7 + 1 ) st original label. If it survives to the end, compute an exact maximum-weight matching in its union with the reference parents. This stored graph contains the entire suffix benchmark M M M , so the branch returns value at least μ \mu μ ; it need not contain a full input optimum. Otherwise the suffix has m ≥ 10 7 m \ge10^{7} m ≥ 1 0 7 labels.
Let τ = ( α + ω ) / 2 \tau=(\alpha+\omega)/2 τ = ( α + ω ) /2 and ζ = 1 / ( 4 ⋅ 10 6 ) \zeta=1/(4\cdot10^{6}) ζ = 1/ ( 4 ⋅ 1 0 6 ) . The largest grid cutoff c ≤ τ m c\le\tau m c ≤ τ m satisfies
0 ≤ τ m − c < γ τ m + 1 < ζ m , α + ζ ≤ c / m ≤ ω − ζ . 0 \le\tau m-c < \gamma\tau m+1 < \zeta m,\qquad\alpha+\zeta\le c/m \le\omega-\zeta. 0 ≤ τ m − c < γ τ m + 1 < ζ m , α + ζ ≤ c / m ≤ ω − ζ .
This designated cutoff is a deterministic function of the final suffix size. It has already been reached and launched; selecting it for analysis incurs no union bound over phases.
Represent the uniform suffix permutation by independent continuous uniform clocks on its original labels. The numbers of labels with clock at most α \alpha α and ω \omega ω are binomial. Except with probability 2 e − 2 ζ 2 m 2e^{-2\zeta^{2}m} 2 e − 2 ζ 2 m , all α \alpha α -early labels precede the phase cutoff and all ω \omega ω -late labels follow it. Categorizing these clocks gives exactly the finite three-category product experiment used for the repair, including all dependence among copies. An equivalent finite construction sorts independent categories and breaks ties with an independent uniform permutation. The resulting order is uniform by invariance under relabeling, while the categories retain their independent product distribution.
For every categorical outcome z z z , let J ( z ) J(z) J ( z ) be the selected copied benchmark matching from § 5 . Let A 0 ( z ) A_0(z) A 0 ( z ) consist of the crossing reference H ′ H' H ′ and the active available crossing benchmark copies. These additional copies belong to the physical suffix list U ′ U' U ′ , since every benchmark parent lies outside the acquisition history. Define the analytic certificate
Q ( z ) = max { b , ν ( A 0 ( z ) − I L ( J ( z ) ) ) + ν ( A 0 ( z ) − I R ( J ( z ) ) ) + ∣ J ( z ) ∣ 2 } . Q(z)=\max\left\{b,\frac{\nu(A_0(z)-I_L(J(z)))+\nu(A_0(z)-I_R(J(z)))+\lvert J(z)\rvert}{2}\right\}. Q ( z ) = max { b , 2 ν ( A 0 ( z ) − I L ( J ( z ))) + ν ( A 0 ( z ) − I R ( J ( z ))) + ∣ J ( z )∣ } .
This quantity is defined for every categorical outcome. The two deletion-graph bounds and the base bound needed by the fixed-host repair theorem hold for Q Q Q by its definition. Thus the repair probability theorem is applied to Q Q Q , without conditioning on the bracket and without assuming a phase guarantee on outcomes where the bracket fails.
On the bracket event, every active parent in A 0 ( z ) A_0(z) A 0 ( z ) is present at phase initialization. Every selected benchmark parent is either already present or tested subsequently: available parents are in the initial underfull list or arrive later, while all selected missing and root parents are late. The deterministic historical transfer and full-base bounds of § 3 therefore give V ≥ Q ( z ) V\ge Q(z) V ≥ Q ( z ) for the actual returned matching. No independence between the repair event and the bracket is required.
Composition and worst-case resources
If the full base has b ≥ 0.714 μ b\ge0.714\mu b ≥ 0.714 μ , it already proves the target. Otherwise r ≥ μ − b > 0.286 μ r\ge\mu-b>0.286\mu r ≥ μ − b > 0.286 μ . A root endpoint has at least 0.49 β 0.49\beta 0.49 β distinct reference neighbors in the cover, so μ > b ≥ 0.49 β \mu>b\ge0.49\beta μ > b ≥ 0.49 β . Hence r > 0.14 β r>0.14\beta r > 0.14 β and m ≥ r / κ m\ge r/\kappa m ≥ r / κ . The finite repair theorem, with allowance θ = δ 0 / 100 \theta=\delta_0/100 θ = δ 0 /100 , gives
Pr [ Q < max { b , F − 10 − 7 μ } ] ≤ 5 θ = δ 0 / 20. (44) \Pr\left[Q<\max\{b,F-10^{-7}\mu\}\right]\le5\theta=\delta_0/20. \tag*{(44)} Pr [ Q < max { b , F − 1 0 − 7 μ } ] ≤ 5 θ = δ 0 /20. (44)
Its hypotheses hold because b < μ ≤ N b < \mu\le N b < μ ≤ N , β ≥ 10 30 κ L / 2 \beta\ge10^{30}\kappa L/2 β ≥ 1 0 30 κ L /2 and μ ≥ 0.49 β \mu\ge0.49\beta μ ≥ 0.49 β . Moreover,
m > 0.14 β / κ ≥ 7 ⋅ 10 28 L , 2 e − 2 ζ 2 m = 2 e − m / ( 8 ⋅ 10 12 ) ≤ 2 e − L ≤ δ 0 / 50. m > 0.14\beta/\kappa\ge7 \cdot10^{28}L,\qquad2e^{-2\zeta^{2}m}=2e^{-m/(8\cdot10^{12})}\le2e^{-L}\le\delta_{0}/50. m > 0.14 β / κ ≥ 7 ⋅ 1 0 28 L , 2 e − 2 ζ 2 m = 2 e − m / ( 8 ⋅ 1 0 12 ) ≤ 2 e − L ≤ δ 0 /50.
The last step uses e − L ≤ δ 0 / ( 100 N ) e^{-L}\le\delta_{0}/(100N) e − L ≤ δ 0 / ( 100 N ) and N ≥ 1 N\ge1 N ≥ 1 . The profile certificate and a union bound thus give V ≥ ( R ∗ − 10 − 7 ) μ V\ge(R_{*}-10^{-7})\mu V ≥ ( R ∗ − 1 0 − 7 ) μ with fixed-host failure at most 7 δ 0 / 100 7\delta_{0}/100 7 δ 0 /100 . Integrating over the stopping histories and adding the acquisition and prefix failures gives
Pr [ f a i l u r e ] ≤ δ 0 / 3 + δ 0 / 3 + 7 δ 0 / 100 = 221 δ 0 / 300 < δ 0 . \Pr[\mathrm{failure}]\le\delta_{0}/3+\delta_{0}/3+7\delta_{0}/100=221\delta_{0}/300<\delta_{0}. Pr [ failure ] ≤ δ 0 /3 + δ 0 /3 + 7 δ 0 /100 = 221 δ 0 /300 < δ 0 .
(43) proves the ratio a ∗ a_{*} a ∗ . An aborted selected instance returns a valid fallback; the approximation guarantee is asserted only outside its charged failure event.
Space and finite encodings. We store each phase graph explicitly. Write n n n for the number of original vertices, N N N for the number of copied vertices, κ \kappa κ for the maximum number of copies in one original-edge batch, and W W W for the largest integer weight in a bounded-weight instance. Put
Q = N β 0 2 + 1 , Γ E = 4 ⋅ 10 8 κ Q L U , T f u l l = max { 4 ⋅ 10 8 Q , 6 ⋅ 10 8 n κ L 0 } . Q=N\beta_{0}^{2}+1,\qquad\Gamma_{E}=4\cdot10^{8}\kappa QL_{U},\qquad T_{\mathrm{full}}=\max\{4\cdot10^{8}Q,6\cdot10^{8}n\kappa L_{0}\}. Q = N β 0 2 + 1 , Γ E = 4 ⋅ 1 0 8 κ Q L U , T full = max { 4 ⋅ 1 0 8 Q , 6 ⋅ 1 0 8 nκ L 0 } .
At every prefix, acquisition stores at most N β 0 / 2 N\beta_{0}/2 N β 0 /2 reference edges and Γ E \Gamma_{E} Γ E timestamped copied edges. Overflow clears the latter store and aborts that local copy. A surviving phase starts with at most N β 0 + Γ E N\beta_{0}+\Gamma_{E} N β 0 + Γ E original edges. Every accepted edge increases its integral matching value by at least one, so the phase stores at most W ⌊ n / 2 ⌋ W\lfloor n/2\rfloor W ⌊ n /2 ⌋ additional edges. There are at most P ( m ) = 10 7 ( ⌊ log 2 m ⌋ + 1 ) P(m)=10^{7}(\lfloor\log_{2}m\rfloor+1) P ( m ) = 1 0 7 (⌊ log 2 m ⌋ + 1 ) launched phases after m m m suffix labels, with the convention log 2 0 = 0 \log_{2}0=0 log 2 0 = 0 in this bound. Consequently a local state uses at most
R l o c ( m ) = 3 N β 0 + 2 Γ E + P ( m ) ( N β 0 + Γ E + W ⌊ n / 2 ⌋ ) + 10 7 R_{\mathrm{loc}}(m)=3N\beta_{0}+2\Gamma_{E}+P(m)(N\beta_{0}+\Gamma_{E}+W\lfloor n/2\rfloor)+10^{7} R loc ( m ) = 3 N β 0 + 2 Γ E + P ( m ) ( N β 0 + Γ E + W ⌊ n /2 ⌋) + 1 0 7
edge records. This deliberately counts the frozen reference and all phase copies separately. The full wrapper therefore uses at most
R = T f u l l + ⌊ n / 2 ⌋ + ( ⌊ log 2 ( n 2 ) ⌋ + 1 ) R l o c ( n 2 ) . R=T_{\mathrm{full}}+\lfloor n/2\rfloor+(\lfloor\log_{2}(n^{2})\rfloor+1)R_{\mathrm{loc}}(n^{2}). R = T full + ⌊ n /2 ⌋ + (⌊ log 2 ( n 2 )⌋ + 1 ) R loc ( n 2 ) .
These are deterministic bounds for every execution, including failed acquisition, cap overflow, and all prefixes. In particular, they are not conditioned on the approximation event. Choose a common logarithmic parameter Λ ≥ 1 \Lambda\ge1 Λ ≥ 1 dominating L L L , L U L_{U} L U , L 0 L_{0} L 0 and 1 + log 2 ( n 2 ) 1+\log_{2}(n^{2}) 1 + log 2 ( n 2 ) , and write β 0 ≤ B 0 κ Λ \beta_{0}\le B_{0}\kappa\Lambda β 0 ≤ B 0 κ Λ for the fixed acquisition constant B 0 B_{0} B 0 . Since N ≤ n κ N\le n\kappa N ≤ nκ and W ≤ κ W\le\kappa W ≤ κ , the displayed formula is at most 10 17 B 0 2 n κ 4 Λ 5 10^{17}B_{0}^{2}n\kappa^{4}\Lambda^{5} 1 0 17 B 0 2 n κ 4 Λ 5 . Vertex labels, integer weights, timestamps and counters have finite binary encodings. A record needs O ( log ( n κ Λ ) ) O(\log(n\kappa\Lambda)) O ( log ( nκ Λ )) bits; the phase and dyadic descriptors are lower-order terms. One may keep both the old and new stores during a transition and one incoming copied batch, increasing this bound only by a constant factor. For unit weights, taking Λ = O ( 1 + log ( n / δ ) ) \Lambda=O(1+\log(n/\delta)) Λ = O ( 1 + log ( n / δ )) gives O ( n ( 1 + log ( n / δ ) ) 6 ) O(n(1+\log(n/\delta))^{6}) O ( n ( 1 + log ( n / δ ) ) 6 ) bits.
For arbitrary positive rational weights, the reduction maintains at most
κ + ⌈ log B ( n / η ) ⌉ + 1 \kappa+\lceil\log_{B}(n/\eta)\rceil+1 κ + ⌈ log B ( n / η )⌉ + 1
live windows. Every retained window state is exactly the complete bounded-integer execution on its filtered input, even though retirement is adaptive. For fixed accuracy the integer range, κ \kappa κ , B B B and η \eta η are constants, so this introduces one further logarithmic factor in the record bound. If B w t B_{\mathrm{wt}} B wt bounds the bits in each input numerator and denominator, the resulting space is
O ε ( n Λ 6 ( B w t + Λ ) ) , Λ = 1 + log ( n / δ ) . O_{\varepsilon}\bigl(n\Lambda^{6}(B_{\mathrm{wt}}+\Lambda)\bigr),\qquad\Lambda=1+\log(n/\delta). O ε ( n Λ 6 ( B wt + Λ ) ) , Λ = 1 + log ( n / δ ) .
In particular, O ( log n ) O(\log n) O ( log n ) -bit input weights and inverse-polynomial failure probability give O ε ( n log 7 n ) O_{\varepsilon}(n\log^{7}n) O ε ( n log 7 n ) bits. Signed window keys use O ε ( log ( B w t + 2 ) ) O_{\varepsilon}(\log(B_{\mathrm{wt}}+2)) O ε ( log ( B wt + 2 )) bits; exact normalization uses integers with O ε ( B w t + 1 ) O_{\varepsilon}(B_{\mathrm{wt}}+1) O ε ( B wt + 1 ) bits. Comparing the final shift solutions uses O ( n B w t ) O(nB_{\mathrm{wt}}) O ( n B wt ) scratch bits for exact rational sums, absorbed by the displayed bound. No unit-cost real arithmetic is required.
Implementation. Each stored edge record carries its input weight; a copied record also identifies its original parent. Eligibility is recomputed from the frozen copied reference and the arriving edge’s canonical batch. A phase test computes the optimum on its stored weighted graph, with and without the arriving edge. All these operations use weights of stored records and the current arrival. Within a bounded-integer instance, an exact maximum-weight matching algorithm on the retained support realizes the EOF decoder’s validity and value specifications; a fixed tie rule may be used. The arbitrary-weight decoder combines these local outputs greedily and compares their original rational weights.
The integer matching calls use Gabow’s algorithm [9 ] . On a nonempty stored host with m H m_H m H edges and n H n_H n H nonisolated vertices, it uses O ( n H ( m H + n H log n H ) ) O(n_H(m_H+n_H\log n_H)) O ( n H ( m H + n H log n H )) arithmetic operations. For weights in [ W ] [W] [ W ] , its workspace occupies O ( m H log ( n H W ) ) O(m_H\log(n_HW)) O ( m H log ( n H W )) bits: half-integrality and the bounds on numerical magnitudes give O ( log ( n H W ) ) O(\log(n_HW)) O ( log ( n H W )) bits per field [10 Appendix B] . Calls run sequentially and reuse one workspace, so the solver and a temporary EOF union support increase the stated space only by a constant factor.
Apply theorem E.1 to the bounded-weight guarantee above. The reduction preserves one original-edge pass and yields ( 0.71295 − ε ) OPT w ( G ) (0.71295-\varepsilon)\operatorname{OPT}_{w}(G) ( 0.71295 − ε ) OPT w ( G ) with failure at most δ \delta δ . For fixed ε \varepsilon ε , the normalized range W W W is constant, so the complete algorithm has polynomial running time in the encoded input size. The bounded-integer subroutine by itself is polynomial in W W W , rather than in its binary encoding length. This completes the proof of theorem 1.1.
Removing the global weight range
We give a weight-range reduction that preserves one-pass random-order algorithms. The separated-bucket construction and greedy combination are due to Gupta and Peng [11 ] ; the black-box streaming and communication formulations appear in Bernstein, Dudeja, and Langley [4 Section 6 and Appendix C] . Tracking the largest observed weight and discarding sufficiently light classes is also standard [7 Section 2] ; see also [12 ] . The implementation below applies this rule to whole local instances. Its purpose is to remove the global weight ratio from the number of simultaneously stored records. The bits needed to represent an input weight remain part of the space bound.
Theorem E.1 (Range reduction with whole-instance retirement). Let 0 ≤ α ≤ 1 0\leq\alpha\leq1 0 ≤ α ≤ 1 and 0 < ε , δ < 1 0<\varepsilon,\delta<1 0 < ε , δ < 1 . Suppose that, for every integer bound W ≥ 1 W\geq1 W ≥ 1 and confidence parameter 0 < δ 0 < 1 0<\delta_{0}<1 0 < δ 0 < 1 , a deterministic one-pass algorithm on simple n n n -vertex graphs with integer edge weights in [ W ] [W] [ W ] always returns an input matching, and that this matching is α \alpha α -approximate with probability at least 1 − δ 0 1-\delta_{0} 1 − δ 0 in uniformly random original-edge order. The algorithm does not require the stream length in advance, and its resource bound must hold on every execution. Then there is a one-pass algorithm for arbitrary positive rational weights that returns an ( α − ε ) (\alpha-\varepsilon) ( α − ε ) -approximate matching with failure probability at most δ \delta δ . It preserves bipartiteness and requires neither the stream length nor its weight range in advance.
For n ≤ 1 n\leq1 n ≤ 1 , return the empty matching. Otherwise, choose a fixed rational θ ∈ ( ε / 2 , ε ] \theta\in(\varepsilon/2,\varepsilon] θ ∈ ( ε /2 , ε ] before the stream and set
B = ⌈ 32 / θ ⌉ , k = ⌈ 8 / θ ⌉ , η = θ / 4 , W = ⌈ B k / η ⌉ , δ 0 = δ / ( k n 2 ) . B=\lceil32/\theta\rceil,\qquad k=\lceil8/\theta\rceil,\qquad\eta=\theta/4,\qquad W=\lceil B^k/\eta\rceil,\qquad\delta_{0}=\delta/(kn^2). B = ⌈ 32/ θ ⌉ , k = ⌈ 8/ θ ⌉ , η = θ /4 , W = ⌈ B k / η ⌉ , δ 0 = δ / ( k n 2 ) .
At all times at most
T l i v e = k + ⌈ log B ( n / η ) ⌉ + 1 T_{\mathrm{live}} = k + \lceil\log_B(n/\eta) \rceil+ 1 T live = k + ⌈ log B ( n / η )⌉ + 1
local instances are stored. Thus the space is the local-instance space multiplied by T l i v e T_{\mathrm{live}} T live , together with O ( n T l i v e ) O(nT_{\mathrm{live}}) O ( n T live ) edge records for decoding and one record for the largest observed weight. Each retained original-edge record is charged its original weight precision. In particular W = ε − O ( 1 / ε ) W = \varepsilon^{-O(1/\varepsilon)} W = ε − O ( 1/ ε ) , and a near-linear record bound for each fixed W W W gives a near-linear record bound for arbitrary weight range.
The theorem is a reduction: its premise is the stated bounded-weight algorithm. It does not assert that arbitrary weighted general matching reduces without loss to arbitrary unweighted matching.
Algorithm. For every integer t t t , consider the fixed half-open window I t = [ B t , B t + k ) I_t = [B^t, B^{t+k}) I t = [ B t , B t + k ) . Edge weights in this window are rounded to
w ^ t ( e ) = ⌊ w ( e ) η B t ⌋ ∈ [ W ] . \widehat{w}_t(e) = \left\lfloor\frac{w(e)}{\eta B^t} \right\rfloor\in[W]. w t ( e ) = ⌊ η B t w ( e ) ⌋ ∈ [ W ] .
Every original edge belongs to exactly k k k windows. Let m s m_s m s be the largest weight among the first s s s original edges. On an arrival, first update m s m_s m s and discard the entire state of every window satisfying B t + k ≤ η m s / n B^{t+k} \le\eta m_s/n B t + k ≤ η m s / n . Then create any newly encountered live windows containing the edge and process it in each of its live windows. Each instance uses its own local counter and fixed normalization. A discarded window is never restarted: the retirement threshold only increases. Individual light edges are not removed from a surviving instance. The integer-weight guarantee is needed only for edges in that instance’s filtered input; values of the normalization outside its window are irrelevant.
At the end, obtain an actual matching M t M_t M t from each surviving instance. For each residue a a a modulo k + 1 k+1 k + 1 , combine the matchings whose starts satisfy t ≡ a ( m o d k + 1 ) t \equiv a \pmod{k+1} t ≡ a ( mod k + 1 ) , in decreasing order of t t t : retain an edge exactly when both endpoints are free. Return the heaviest of these k + 1 k+1 k + 1 matchings, measured with the original weights. This final procedure uses only retained records and elementary greedy matching. Empty windows are skipped, so a large gap between weight scales creates no extra instances.
Lemma E.2 (Complete history of every survivor). Fix an arbitrary original stream. At every time s s s , each stored window has exactly the state obtained by running its local algorithm on the entire original prefix restricted to I t I_t I t , without retirement.
Proof. The threshold η m s / n \eta m_s/n η m s / n is nondecreasing. A stored window was live at every earlier time and was created at its first relevant arrival. Every relevant arrival used the same normalization, transition, and local counter as the hypothetical unretired execution. Induction over the original arrivals proves equality. This is a pointwise state identity; no probability is conditioned on survival. □
Lemma E.3 (Hard bound on live instances). At every nonempty prefix, the number of live nonempty windows is at most T l i v e T_{\mathrm{live}} T live .
Proof. Put m = m s > 0 m = m_s > 0 m = m s > 0 and c = η / n c = \eta/n c = η / n . A live nonempty window satisfies B t ≤ m B^t \le m B t ≤ m and c m < B t + k cm < B^{t+k} c m < B t + k . Choose the nonnegative integer h = ⌈ log B ( 1 / c ) ⌉ h = \lceil\log_B(1/c) \rceil h = ⌈ log B ( 1/ c )⌉ , so B − h ≤ c B^{-h} \le c B − h ≤ c . For two live starts i < j i < j i < j , the inequality j − i > k + h j-i > k+h j − i > k + h would imply
B i + k ≤ B j − h = B − h B j ≤ c m , B^{i+k} \le B^{j-h} = B^{-h}B^j \le cm, B i + k ≤ B j − h = B − h B j ≤ c m ,
contradicting liveness of i i i . The integer starts lie in an interval of diameter at most k + h k+h k + h , hence there are at most k + h + 1 k+h+1 k + h + 1 of them. This argument does not assume that any local algorithm succeeds. □
Lemma E.4 (Greedy combination of separated bands). Let M t M_t M t be matchings with edge weights in [ B t , B t + k ) [B^t,B^{t+k}) [ B t , B t + k ) , and fix a residue of t t t modulo k + 1 k+1 k + 1 . If M M M is their greedy combination in decreasing order, then
∑ t w ( M t ) ≤ ( 1 + C ) w ( M ) , C = 2 B ( 1 − B − ( k + 1 ) ) . \sum_t w(M_t) \le(1+C)w(M), \qquad C = \frac{2}{B(1-B^{-(k+1)})}. t ∑ w ( M t ) ≤ ( 1 + C ) w ( M ) , C = B ( 1 − B − ( k + 1 ) ) 2 . Proof. Each rejected edge meets an edge already retained from a strictly higher band. Charge it to one such blocker, and charge a retained edge to itself. An edge of M M M meets at most two edges of any one M t M_t M t , because M t M_t M t is a matching. A retained edge in the band starting at t t t has weight at least B t B^t B t . The upper endpoints of lower bands in this residue are B t − 1 , B t − 1 − ( k + 1 ) , … B^{t-1}, B^{t-1-(k+1)}, \ldots B t − 1 , B t − 1 − ( k + 1 ) , … . Its total incoming charge is therefore at most
w ( e ) + 2 ∑ j ≥ 0 B t − 1 − j ( k + 1 ) ≤ ( 1 + 2 B ( 1 − B − ( k + 1 ) ) ) w ( e ) . w(e) + 2\sum_{j\ge0} B^{t-1-j(k+1)} \le\left(1+\frac{2}{B(1-B^{-(k+1)})}\right)w(e). w ( e ) + 2 j ≥ 0 ∑ B t − 1 − j ( k + 1 ) ≤ ( 1 + B ( 1 − B − ( k + 1 ) ) 2 ) w ( e ) . The actual sum is finite; the geometric series only bounds it. Summing the charges proves the claim for general as well as bipartite graphs.
Proof of Theorem E.1 . The empty graph is immediate, and n ≥ 2 n \ge2 n ≥ 2 otherwise. Fix an optimum matching M ⋆ M^\star M ⋆ before exposing the stream. Write m = max e w ( e ) m = \max_e w(e) m = max e w ( e ) and τ = η m / n \tau= \eta m/n τ = η m / n . Deleting edges of M ⋆ M^\star M ⋆ lighter than τ \tau τ loses at most ⌊ n / 2 ⌋ τ ≤ η OPT / 2 \lfloor n/2\rfloor\tau\le\eta\operatorname{OPT}/2 ⌊ n /2 ⌋ τ ≤ η OPT /2 . Let M H M_H M H be the remaining matching. Every window containing an edge of M H M_H M H survives: its excluded upper endpoint is strictly larger than that edge’s weight, which is at least τ \tau τ .
Consider hypothetical complete executions of all graph-nonempty fixed windows. There are at most k ∣ E ∣ ≤ k n 2 k|E| \le kn^2 k ∣ E ∣ ≤ k n 2 such windows. The restriction of a uniform original-edge permutation to each fixed edge subset is uniform; copies produced inside a local algorithm are not asserted to be independently ordered. A union bound gives probability at least 1 − δ 1-\delta 1 − δ that every complete local execution succeeds. Lemma E.2 transfers these successes to all final survivors. The local success events need not be independent.
Work on this simultaneous success event. For every e ∈ I t e \in I_t e ∈ I t ,
( 1 − η ) w ( e ) ≤ η B t w ^ t ( e ) ≤ w ( e ) . (1-\eta)w(e) \le\eta B^t \widehat{w}_t(e) \le w(e). ( 1 − η ) w ( e ) ≤ η B t w t ( e ) ≤ w ( e ) .
Consequently w ( M t ) ≥ α ( 1 − η ) w ( M H ∩ I t ) w(M_t) \ge\alpha(1-\eta)w(M_H \cap I_t) w ( M t ) ≥ α ( 1 − η ) w ( M H ∩ I t ) . The k k k consecutive starts containing a fixed edge occupy k k k distinct residues modulo k + 1 k+1 k + 1 . Thus some residue contains at least k / ( k + 1 ) k/(k+1) k / ( k + 1 ) of the weight of M H M_H M H . Applying Lemma E.4 to that residue proves the ratio
α ( 1 − η ) ( 1 − η / 2 ) 1 + C k k + 1 . \frac{\alpha(1-\eta)(1-\eta/2)}{1+C}\frac{k}{k+1}. 1 + C α ( 1 − η ) ( 1 − η /2 ) k + 1 k .
Here B − ( k + 1 ) ≤ 1 / 2 B^{-(k+1)} \le1/2 B − ( k + 1 ) ≤ 1/2 , so C ≤ 4 / B ≤ θ / 8 C \le4/B \le\theta/8 C ≤ 4/ B ≤ θ /8 , and 1 / ( k + 1 ) ≤ θ / 8 1/(k+1) \le\theta/8 1/ ( k + 1 ) ≤ θ /8 . Using 1 / ( 1 + x ) ≥ 1 − x 1/(1+x) \ge1-x 1/ ( 1 + x ) ≥ 1 − x for x ≥ 0 x \ge0 x ≥ 0 and ∏ i ( 1 − x i ) ≥ 1 − ∑ i x i \prod_i(1-x_i) \ge1-\sum_i x_i ∏ i ( 1 − x i ) ≥ 1 − ∑ i x i for x i ∈ [ 0 , 1 ] x_i \in[0,1] x i ∈ [ 0 , 1 ] , the displayed ratio is at least α ( 1 − 5 θ / 8 ) ≥ α − ϵ \alpha(1-5\theta/8) \ge\alpha-\epsilon α ( 1 − 5 θ /8 ) ≥ α − ϵ .
The live-state bound is Lemma E.3 . The final greedy decoder stores the local output matchings and their vertex occupancy sets, within the stated O ( n T l i v e ) O(nT_{\mathrm{live}}) O ( n T live ) records. Comparisons and normalization use exact rational arithmetic. Their bit complexity is polynomial in the input encoding for fixed accuracy; weight precision is not treated as a constant.
Verification and reproducibility
The numerical optimization is used to find a dual certificate. The proof uses the resulting rational numbers and exact inequality checks. In particular, neither a floating-point objective nor a search over small graphs establishes the approximation guarantee.
The Lean sources and independent rational checker are available at https://github.com/farhadi94/matching-random-stream (verified revision 55853c3a1f58). The submission package also includes the exact certificate and checker under certificates/degree_profile/.
The approximation guarantees and the new structural results are formally verified in Lean. The formal development includes the historical deletion and copied transfer theorems, the actual graph-to-profile map, the rational certificate, acquisition and stopping histories, and the complete streaming and weight-window composition. The public approximation theorems instantiate the algorithms and their confidence parameters; they do not assume an algorithm-success event or a feasible profile. The artifact identifies the corresponding theorem statements and pins their source dependencies. Its axiom audit follows raw kernel dependencies, including cycles through inductive and recursor declarations. It permits only Lean’s standard axioms of propositional extensionality, choice, and quotient soundness.
The formal resource analysis counts the actual stored records and metadata and proves finite encodings for their components. It does not extract a packed implementation or formalize a heap allocator. The matching solver’s running time and workspace use the cited implementation results.
AI methodology
OpenAI Codex, using the Astra model, materially supported literature discovery and comparison, conjecture and proof development, proof checks, exact experiments, Lean formalization, and drafting. Fable 5.2 also contributed conjectures, proof ideas, and mathematical feedback. The accompanying artifact records the formal verification coverage and reproducible certificate checks.