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

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

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

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

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

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

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

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

Proof. Every captive row allocates all \(L\) units inside \(X\), so \(\operatorname{load}^a(X)\ge L|A(X)|\) and \(y^a(X)\le Lh(X)\). Zero bottom debt and \(c_a=1\) give \(y^a(X)\ge w(X)\). Weights are positive integers, proving the assertions. ◻

Proof. A surviving row’s assigned bin is outside \(R\). The added allocation and debt cancel in \(y+p-cw\); removing rows only increases exterior slack.

Exactly \(|R|-f\) rows are removed. Their allocation into \(R\) is \(L(|R|-f)-I\), giving \[y(R)=L|R|-\bigl(L(|R|-f)-I+O\bigr)=Lf+I-O.\] Every captive row is removed, as its assigned bin lies in \(R\). Only the other \(h(R)-f\) removed rows contribute to \(I\). Deleting debt \(p(R)\) and adding \(O\) gives the exact net debt change, and (4) gives the inequality. At a gain, \(R\) has two bins and \(h(R)\le2\).

There is one unmatched vertex per free bin or blocker. Expansion adds one bin and one assigned row. Contraction replaces \(|X|\) bins and \(|X|-1\) assigned captive rows by one bin, preserving any exterior assignment. A peel transfers free bins’ unmatched vertices to blockers. A gain matches two free exposures. This proves the unmatched-count assertions. ◻

Proof. A new positive allocation receives \(4\delta\) from a large donor in its row. Reading its at most three entries finds such a donor, since their sum is \(L\). Add \(4\delta\) debt at the destination bin. Its increased load is canceled by the debt; the donor bin’s slack increases by \(4\delta\). If both bins coincide, their load is unchanged and their slack still increases by that amount. The two specified large entries of a newly expanded row may be installed first and used as donors for its remaining incidences.

Use the same transfer whenever an existing allocation has cached value at most \(3\delta\). If a cached slack is at most \(3\delta\), increase that slack and its debt by \(4\delta\). Read touched values exactly and re-anchor explicit settings. Check touched slacks after exact re-anchoring too, including values at the small-value threshold.

Between motions or structural changes, each row has at most three entries to repair. A donor initially at least \(L/3\) remains large after these tiny transfers. Both changed allocations are re-anchored at nonsmall values. Transfers never decrease a slack, and a slack repair changes no other barrier coordinate. Engine notifications arising during settlement are queued and served, but price and forest maintenance itself causes no primal motion. Without a new motion or structural change, an already repaired coordinate cannot require another repair. Thus there is no uncharged repair chain.

For a single positive logarithm the register bound gives \[|f-\widehat f|\le(q/100)\widehat f.\] After service, an unrepaired coordinate has cached value above \(3\delta\), while a repaired one has been increased and re-anchored by \(4\delta\). This bound and the step-size bound leave the stated margins before a step and at refreshes after it. Contraction aggregates positive slacks; deletion increases surviving slacks; expansion has the positive margins specified above. New descriptors are inserted only after their positive final values are computed. All settings are exact \(\varepsilon\)-grid operations.

Only the large donor’s logarithm can decrease during a transfer, by \(O(\delta)\); recipient allocation and donor slack increase. A slack repair increases its logarithm. There are \(O(S)\) coordinates at any state, with constantly many repairs per coordinate or changed physical incidence between motions or structural batches. The \(S^{20}\) phase-action cap and the no-motion observation give, very crudely, at most \(S^{30}\) such fixes on a guarded prefix, including the last completed edit batch. Consequently their \(4\delta\) debt additions total less than \(S^{-800}\). This precision estimate does not permit scanning all coordinates after each step: only touched entries and dirty notifications are serviced.

Maintain bin-to-\(U\) contact lists and a cached-slack eligibility index. The relative register inequality, with \(q<1\), gives \(s_d\ge3C\) when \(\widehat s_d\ge4C\); if no eligible contact exists, its cached slack is below \(4C\) and its true slack below \(5C\). ◻

Proof. For an integral maximum flow \(F\), set \[x'_e=x_e-F_{d,r}(e)+F_{r,d}(e).\] Every row has total incoming exchange capacity \(L\), so its outgoing exchange flow is at most \(L\). Thus \(x'\ge0\), its row sums are \(L\), and no row-to-bin arc of capacity \(L+1\) is saturated. If \(F_{\mathrm{src},d}\) and \(F_{d,\mathrm{snk}}\) denote source and sink arc flows, then \[y'_d=y_d+F_{\mathrm{src},d}-F_{d,\mathrm{snk}}.\] At value \(\beta\), all deficits are filled while a spare loses at most \(u(d)\), proving \(y'\ge cw\).

Otherwise let \(R\) be all residual-reachable bins. For an incidence \(e=(r,d)\), residual capacity from \(d\) to \(r\), combining the original arc and the reverse of its companion, is \[x_e-F_{d,r}(e)+F_{r,d}(e)=x'_e.\] A positive allocation into a reachable bin makes its row reachable. All that row’s neighbors are reachable because its row-to-bin arcs are unsaturated. The rows allocating into \(R\) are therefore exactly its captives, which allocate their full \(L\) there. Hence \(y'(R)=Lh(R)\). Every reachable spare sink arc is saturated, whereas some reachable source deficit remains unsaturated. Summing the residual changes over \(R\) gives (13).

Every deficit outside \(R\) is saturated, as otherwise its source arc would make it reachable; so \(y'\ge cw\) there. A surviving row has no allocation into \(R\), since such a row would be captive and removed. Removing the assigned rows of \(R\) only increases exterior residuals. Restricted \(x'\) is the requested ledger.

For a coarser level \(\ell<j\), one has \(c_\ell\ge c_j+1\). Lemma 8 gives net debt change at most \[Lh(R)-c_\ell w(R)<-w(R).\] Thus at least \(w(R)\) is paid. Every captive is among the removed assigned rows, giving \(f\le h(R)\); now (13) and \(c_j\le C\) give the blocker bound. ◻

Proof. An injection avoiding forbidden bins \(F\) exists precisely when \[|A(Z)|\le |Z\setminus F| \qquad(Z\subseteq\mathcal D).\] Necessity is immediate. For sufficiency, apply Hall’s condition (Hall 1935, Theorem 1) to any row subset: if \(Z\) is its full neighbor set, those rows belong to \(A(Z)\), and \(Z\setminus F\) is large enough. For \(F=\{i,j\}\), the criterion becomes \[ h(Z)\ge |Z\cap\{i,j\}|. \tag{15}\] By the bottom surplus, failure means exactly a tight set containing both bins.

Each neighborhood-inclusion indicator in \(|A(Z)|\) is supermodular; thus \(h\) is submodular. Two tight sets containing \(i,j\) have nonempty intersection and union, both of deficiency at least one. Submodularity forces their intersection to be tight. Intersecting all such sets gives the unique minimal \(X\). Its weight bound follows from Lemma 7.

To expose a physical vertex \(v\) in child bin \(d\in X\), match all captive rows into \(X\setminus\{d\}\). The Hall inequalities are \(h(Z)\ge1\) when \(d\in Z\) and \(h(Z)\ge0\) otherwise, for \(Z\subseteq X\). Expose \(v\) inside \(d\) and each assigned edge’s physical contact inside every other child.

To expose a captive row \(r\), match \(i,j\) along the joining edge, and match the other captives into \(X\setminus\{i,j\}\). The needed Hall inequalities are \[ h(Z)+\boldsymbol1_{\{r\in A(Z)\}}\ge |Z\cap\{i,j\}| \qquad(Z\subseteq X). \tag{16}\] A proper subset containing both \(i,j\) has \(h(Z)\ge2\) by minimality and integrality. Other nonempty proper subsets use \(h(Z)\ge1\), and the empty set is harmless. For \(Z=X\), the deficiency is one and \(r\) is captive. Thus (16) holds. Each child exposes its actual prescribed physical contact, so the child witnesses lift these injections and the joining edge to the desired internal matchings. ◻

Proof. At a contraction store the child-bin records, captive rows and their physical incidences, joining edge, and captive assignment at contraction time. This gives a contraction tree whose leaves include both child-bin vertices and swallowed row vertices. The stored captive assignment covers all but one child.

If the desired exposure \(v\) is in child \(d\), forbid \(d\) and remove its captive assignment if present. At most one row becomes unmatched. Lemma 11 guarantees an injection of all captives avoiding \(d\), so at most one ordinary row augmentation suffices. If \(d\) was the unused child, none is needed. Expose \(v\) inside \(d\), and the physical assigned-edge contact in every other child. A preserved exterior assignment merely prescribes \(v\) to be its contact endpoint.

If the desired exposure is swallowed row \(r\), delete \(r\) and its assigned edge, reserve \(i,j\) for the stored joining edge, and remove any remaining assignments into those children. At most two remaining rows become unmatched. Inequality (16) guarantees a matching of the remaining rows into \(X\setminus\{i,j\}\), so at most two augmentations suffice. The joining edge prescribes exposures in \(i,j\); every other child gets its row-edge contact.

In either case each child receives exactly one prescribed exposure and is recursively materialized once. The searches scan only this node’s stored abstract incidence graph, of size linear in its arity because rows have degree at most three, rather than its children’s physical interiors.

At the start of dissolving a root, one traversal assigns subtree leaf intervals. The interval containing a prescribed physical vertex identifies its direct child, with logarithmic search overhead if needed. No contraction is unary, and each record has size linear in its arity. The sum of record sizes and leaves is therefore linear in the dissolved root’s physical size. Summing the local searches, endpoint lookups, and single child visits proves the bound. Disjoint roots at an erasure or phase boundary can be handled in the same total physical-size time. ◻

Proof. Before the terminal \(g_*\)-th gain there are at most \(g_*-1\) gains whose ledgers are repaired. Top contractions preserve total debt, top expansions consume available slack without other debt, and the positivity service of Lemma 9 adds less than \(S^{-800}\) debt. By Lemma 8, each repaired gain adds at most \(2L\) net debt. By Lemma 10, every projection peel consumes at least its weight from the top ledger. Nonnegative remaining debt gives the first bound in (32).

The number of new blockers at a peel is at most \(h(R_0)<Cw(R_0)/L\). Summing this strict inequality and using integrality gives the second bound in (32); the tiny positive remainder is less than one. In particular, before the first gain of a phase with \(g_*=1\), no positive-weight peel can occur.

The bottom certificate of Lemma 7 bounds the weight removed by a gain by \(2L\). A removed bin has \(2w_d-1\) physical vertices, and at most one assigned row per removed bin is materialized with it. Thus the number of vertices returned to the paired remainder is bounded by a constant times the total erased weight. Every expansion consumes a pair from that remainder. Its initial population is at most \(N\), so expansions number \(O(N+Lg_*)\). Initially there are at most \(N\) bins and each expansion creates one new bin. A contraction decreases their number by \(|X|-1\), and \(|X|\ge2\); hence the sum of \(|X|\) over contractions is also \(O(N+Lg_*)\). Expansions and contractions contribute one tick each, and a repaired gain contributes \(L\), giving \(\tau=O(N+Lg_*)\).

Finally \(Lg_*=O_a(N)\). If \(K<100C\), then \(g_*=1\) and \(L=O_a(N)\). Otherwise \[Lg_*\le \left(\frac{10000CN}{K}+1\right)\frac{K}{100C} =O(N).\] This proves the tick bound. ◻

Proof. Let \(i_*\le g_*-1\) be the gains so far. For this argument only, realize the matching represented by the partition. This is an existence comparison, not an instruction to materialize the graph at every pricing step. Taking the symmetric difference with a perfect matching gives \(K-i_*\) vertex-disjoint augmenting paths (Berge 1957). At most the blocker count meet a blocker.

Orient each remaining path from an unmatched endpoint. Its first bin is free and is entered at its exposed base. That bin has no other unmatched vertex and no crossing matching edge. At a stall there is no edge to a distinct bin. If the path exits to a row by a nonmatching edge, its next matching edge is that row’s assigned edge, entering another bin at its base. This new bin is assigned; its only possible crossing matching edge is the one just used on entry. A simple path must therefore next exit it by a nonmatching edge. Continuing this argument, the path must eventually reach \(U\): it avoids blockers, cannot end inside an assigned bin, and cannot enter another free bin through an assigned row edge.

Every such entry uses the unique physical base of its bin. Simplicity and vertex-disjointness consequently imply that the prefixes through their first \(U\)-contacts use distinct bins and rows, both within a prefix and across different prefixes. Reassign each prefix row to the preceding bin in its chain. This is simultaneously injective and frees the last bin of every prefix. If \(Z\) denotes all bins with a \(U\)-contact, one can thus leave simultaneously free a subset of \(Z\) of size \[ r\ge K-i_*-2C(g_*-1)\ge K/2 . \tag{33}\]

Scale this conceptual assignment by \(L\). The desired top column capacities are \[L+p_d^0-Cw_d ,\] which are nonnegative because the current top allocation and positive slack realize them. Clip overloaded columns by removing mass. An assigned column initially carries \(L\), so its removed mass is at most \(Cw_d\); the total removed is at most \(Cw(\mathcal D)\le CN\). The current top allocation proves that all rows can be filled under these capacities. Complete the clipped partial transportation flow by residual source-to-sink augmentations; one can scale the dyadic data and use integral path decomposition for this existence argument. Simple augmenting paths do not leave the sink, so column sink flows do not decrease. The \(r\) initially empty specified columns receive in total at most the removed mass. The resulting allocation \(x'\) has nonnegative slacks \(s'\) and satisfies \[ s'(Z)\ge Lr-2CN . \tag{34}\]

At a stall, the cache-based eligibility guarantee of Lemma 9 gives \(s_d\le5C\) on \(Z\). Take the difference from the current allocation and slack as a direction. Row sums and column equations are unchanged, so it is a circulation in the top engine graph. Every negative individual logarithmic directional contribution has magnitude at most one, since \(x',s'\ge0\). Their total is at most \(|E(\mathcal B)|+|\mathcal D|\le4N\). The positive sum is at least \[\frac{s'(Z)}{5C}-|Z| \ge \frac{Lr-2CN}{5C}-N .\] By (33) and \(L\ge10000CN/K\), this is greater than three times \(4N\). As \(\lambda\) counts the absolute individual contributions, the claimed ratio is greater than one half. Lemma 21 excludes \(\mathrm{LOW}\) unless it explicitly reports failure or suspension. Its positive objective increase, with the bounded objective accounting below, also excludes indefinite pricing without another structural action. ◻

Proof. Consider the prefix through a putative first deterministic interruption. The elementary initial checks, such as \[S\ge2^{100},\qquad 100000C,\ B\le S^{1/20},\qquad q\ge S^{-1},\] are eventually satisfied at each fixed sufficiently large \(a\). The loose \(S^{20}\) iteration caps and the \(S^{100}\) external-operation cap suffice first to bound tiny positivity debt and local pads. A small argument increased and exactly re-anchored does not require another increase without motion or a reset of its bounds. A top donor is chosen exactly from a bounded-degree row with sum \(L\); local repair does not create an unbounded chain of new small donors. Thus these numerical error estimates do not assume the sharper running-time bounds that they are used to prove.

All completed structural actions and peels preserve the deterministic ledger and matching invariants. Their debt payoffs and the bottom certificates prove Lemma 17 independently of objective progress. Include the present structural action if any. For a coarse numerical bound, one has \[L\le10000CS+1,\qquad g_*\le S,\qquad \text{erased weight}\le4Lg_*+1,\] and at most \(N+4Lg_*+2\) expansions, allowing the next one as well. Every retained integral ledger has acquired at most \[ C(N+4Lg_*+2)+2Lg_* \tag{40}\] debt between its resets, even without using (38). Column loads are at most \(L|\mathcal A|\). Together with \(100000C\le S^{1/20}\), these estimates put all top data, exchange capacities, local return weights and scaled capacities, and argument upper bounds well inside \(S^{20}\). Thus numerical adequacy does not depend on parameter-dependent rounding constants in the period bound.

At a local threshold test, the current sink consumption already bounds every lock-trigger expansion by (30), before that expansion is performed. Ready arguments and post-motion refreshes have the required lower margin, and explicit edit batches use positive old and final settings. At the top, (35), with one extra physical-size edit allowance, verifies the nominal lifetime bound \(SB\) at a possible first overflow. At a local test, (38) and its \(8192(P+1)\) nominal size give the engine condition \(R+B\le S^{1+2/a}\) eventually. The same is true for the top nominal size.

The structural and objective estimates (31) and (37) bound all completed iterations. Add at most one final \(\mathrm{LOW}\), failed, or interrupted attempt. Because \(q^{-2}=O_a(S^{200/a})\), these bounds remain below \(S^{20}\) for fixed sufficiently large \(a\) and large \(S\). Up to a hypothetical first external-operation cap, the engine’s notification bound charges dirty coordinates to priced motion. Client repairs add only constantly many point operations per dirty trigger, besides the structural edits, and have no no-motion repair chain. Consequently even this cap-reaching prefix has only \(S^{1+O(1/a)+o_a(1)}\) external work, eventually smaller than \(S^{100}\). The priced-step lemma’s own eventual prerequisite adequacy applies within these hypotheses.

These arguments are uniform over successful verified states and rejected stochastic attempts. The engine lemma bounds attempted operations on every path; its construction uses verified structures and capped failed attempts, not a good-event-only time estimate. The pair primitive likewise either returns a valid action within its charged bound or terminates negatively. A detected stochastic failure promptly ends the PM test, whereas an inadequate deterministic prerequisite suspends the branch. The latter has just been excluded in the fixed-parameter asymptotic range. All local scans and updates, including a final pair abort or incomplete attempt, are charged by their represented work. This proves the claim. ◻

Proof. Settle trivial cases directly; an odd number of vertices has no perfect matching. Start with the empty matching and run the phase construction. When \(K\ge200C\), a completed phase gains at least \(K/(200C)\). Below that threshold, at most \(200C\) further phases are needed, each gaining at least one. Thus there are \(O_a(\log S)\) completed phases, and at most one final negative or suspended phase. Each has the bound established above. Initialization, phase-boundary materialization, and the final edge-identifier and vertex-coverage check cost only the already allowed near-linear work. Lemma 19 makes (42) an every-path bound and excludes suspension in the stated asymptotic range. On arbitrary checked sizes, the explicit iteration, operation, representation, and sampling caps still give halting, with suspension permitted.

On a PM instance, in the absence of a stochastic failed guarantee or suspension, valid pair actions and projections preserve the invariants. Lemma 18 prevents a \(\mathrm{LOW}\) negative answer before the phase target. The objective step bound prevents an infinite sequence of priced steps, so each phase reaches its gains and the algorithm eventually constructs a perfect matching. Checking the proposed edge copies and coverage excludes false positives on every input, including no-instances.

For the probability bound, count invocations using the loose guards rather than conditioning on later noninterruption. There are fewer than \(S\) nontrivial phases, at most \(S^{20}\) main actions per phase, and only logarithmically many threshold tests and retrieval tests per projection. On these prefixes, \[\beta\le CN+L|\mathcal A|,\] so its search range has logarithmic bit length. The total number of pair queries and priced-step instances is, conservatively, less than \(S^{50}\). Each reached pair query has the conditional error allowance in Lemma 12; each reached engine instance has the conditional allowance of Lemma 21. Both are at most \(2^{-\sigma}S^{-60}\). Union over the reached invocations gives at most \(2^{-\sigma}S^{-10}\), which is smaller than (41).

The conditional bounds are applied when the invocation’s input and prerequisites are fixed by its past history, and its new bits are fresh. They are not conditioned on whether the branch later suspends or wins a scheduling race. An additional deterministic suspension produces no negative answer by itself. This proves (41) also at checked sizes where suspension remains possible, and completes the theorem. ◻

Proof. Use auxiliary splay trees in down-path order for preferred paths (Sleator and Tarjan 1985, sec. 6). Their roots keep path-parent pointers to the represented parents of their path tops. Access at \(v\) starts at \(v\) and repeatedly splays the current node \(y\), replaces its right subtree by the path exposed so far, and advances to its previous path parent. The demoted path receives path parent \(y\). A final splay of \(v\) exposes the represented-root-to-\(v\) path. Evert reverses that path. A cut from parent accesses its endpoint and detaches the left ancestor subtree. A link accesses its endpoints and installs a path-parent pointer for a represented root. The stated tags require only bounded work during each pointer or aggregate change.

For the amortization, give a node weight one plus the sum of represented subtree sizes of its nonpreferred children. Let \(s(x)\) be its auxiliary subtree weight and \(r(x)=\log_2 s(x)\), and use \(\Phi=\sum_x r(x)\). Node weights stay fixed during a splay. The usual rotation inequalities from the access lemma (Sleator and Tarjan 1985, Lemma 1) can be recalled briefly. In a double rotation with node \(x\), parent \(y\), and grandparent \(z\), we have \(r'(x)=r(z)\) and \(r(y)\ge r(x)\). For zig-zag, \(r'(y)+r'(z)\le2r'(x)-2\) by disjoint child weights. For zig-zig, \(r(x)+r'(z)\le2r'(x)-2\) by the disjoint old-\(x\) and new-\(z\) subtrees, and \(r'(y)\le r'(x)\). Thus two rotations plus their change in potential cost at most \(3(r'(x)-r(x))\); a final single rotation adds at most one.

At a preferred-path switch, the total weight of a detached or attached auxiliary path equals the represented subtree size of the demoted or promoted child. The change in the splayed root’s own weight compensates exactly, so the switch does not change \(\Phi\). Along an upward access, the next node’s initial auxiliary weight contains the preceding exposed path through its dashed-child weight. The rank differences therefore telescope to \(O(\log N_f)\), apart from a constant per access iteration.

To pay for those iterations, call a represented edge heavy if its child’s subtree has more than half its parent’s size, and add a sufficiently scaled count of dashed heavy edges to the potential. A represented root path has at most \(\log_2 N_f\) light edges. Access promotes every dashed edge it traverses. A heavy off-path edge is demoted only opposite a light preferred child on the accessed path, or at its endpoint. The iteration count plus the change in this additional potential is consequently \(O(\log N_f)\).

It remains to check represented-tree changes. After access, write the weight of a path vertex as one plus the sizes of its off-path dashed subtrees. These weights are unchanged by reversing the complete exposed path. Recursive left-right swapping in its auxiliary splay tree preserves each auxiliary subtree’s vertex set and total weight, hence preserves \(\Phi\). If an off-path child becomes heavy after reversal, the next edge down the reversed path must be light, or the vertex is the path endpoint. There are only \(O(\log N_f)\) such events. Cutting an accessed parent edge similarly leaves the path weights unchanged, does not increase \(\Phi\), and charges newly heavy off-path children to light edges of the shortened path. Linking a root below an accessed vertex increases only that auxiliary root’s weight sum; its rank grows by at most \(\log N_f\). Existing off-path children of its ancestors cannot newly become heavy as ancestor subtrees grow, and the new dashed edge contributes at most one. All potentials are nonnegative and the initial singleton state has zero potential. This proves the bound, also under recycling of a fixed node pool.

For threshold reporting, expose the updated path, read a witnessed nonpositive minimum, access that node, and disable it at a point. Repeating these operations costs the claimed amount per actual disable. ◻

Proof. The signed displacement since the most recent anchor is bounded by the sum of current absolute copy counters and the bucket. This is true initially, preserved by path updates and explicit traversals, and preserved by transfer on copy death. Dormant retained copies keep their counters. At a settled state there are at most \(D\) copies and one bucket, each below threshold. Since \(\lambda_e(\widehat f_e)\le\ell_e/H\), we obtain \[\lambda_e(\widehat f_e)|f_e-\widehat f_e| \le \frac{\ell_e}{H}(D+1)\theta_e \le \frac{q(D+1)}{400D}\le q/200.\] This is stronger than (48).

For the cost bound, partition raw real-edge motion into intervals between successive anchors of each coordinate. Its price is fixed on such an interval. An engine report consumes at least \[\theta_e\ell_e/H\ge q/(800D)\] of that interval’s raw priced absolute motion. The consumed intervals are disjoint for one coordinate, and different coordinates consume different real-edge motion. Absolute mass moves between copies and the bucket without duplication. It is reset before price-replacement logs, so it cannot be charged again at a new price. A client anchor may discard old drift credit, but does not create new credit and is charged as an external operation.

Similarly, a disable event can charge the motion of its copy since creation or its latest reset. A copy is disabled at most once during that uninterrupted accumulation; reenabling at an anchor resets it. These disable charges are disjoint within this second charge category. Counting both report charges and disable charges only introduces a constant factor. By (59), a successful step creates at most \(q/200\) of raw priced absolute motion. The claimed \(O(D)\) amortized bound follows.

Finally, a no-motion refresh cascade is finite. A queued variable can consume its extant absolute mass once; after its reset, all its absolute locations are zero and remain so until new motion. Its own replacement logs cannot recreate that mass. Other variables may expose previously accumulated mass, but their reports have the disjoint charges just described. Pending flags are per variable, so copy deletion loses neither the required service nor its charge. This proves both termination of settlement and the notification bound. ◻

Proof of Lemma 21. Apply Lemma 22 to the port graph with prices (53). Exact point operations and forest updates preserve (63). The refresh procedure proves (48), and therefore validates (55) before each pricing call. The lifting, quality margin, and acceptance test prove part (i). Equations (58)–(59), the partial-motion bound, and the grid check prove part (ii), including exact circulation and positivity. The objective estimate following the statement proves its progress assertion. Lemma 24 proves part (iii), and the preceding cost accounting proves part (iv).

Backend failures are explicitly propagated. Its conditional instance budget gives \(2^{-\sigma}S^{-60}\) for the whole engine instance; the remaining operations are deterministic. Representation, anchor-range, and precision prerequisites are checked on their local inputs, with counts maintained incrementally. During a whole step, the already proved raw-motion bound supplies the required relative margins; no global scan is needed to certify them. The operation and record guards are applied to prefixes, and the preceding bounds hold through a putative first guard-reaching operation. For each sufficiently large fixed \(a\) and each fixed \(\sigma\ge0\), these bounds fall below the loose polynomial caps, and the size and quality inequalities hold for all sufficiently large \(S\). Together with the backend’s guarded-prefix guarantees in Section 8, this proves eventual adequacy on every path, independently of whether a stochastic routine ultimately reports failure. Such a failure is propagated promptly and is never reclassified as a deterministic suspension. ◻

Proof. Put \(D=\operatorname{diag}(d_i)\) on the nonisolates and set \[A_e=D^{-1/2}(\mathbf e_i-\mathbf e_j) (\mathbf e_i-\mathbf e_j)^\mathsf{T}D^{-1/2}.\] These are positive semidefinite rank-one matrices, \(\|A_e\|=1/d_i+1/d_j\), and \(\|\sum_e A_e\|\le2\). If \(\xi_e\) is the retention indicator, write \(Y_e=(\xi_e/p_e-1)A_e\). Deterministically retained edges contribute zero. For any other edge, \(p_e\ge K_s\|A_e\|\), whence \[\|Y_e\|\le K_s^{-1},\qquad \mathbb EY_e^2=(p_e^{-1}-1)A_e^2\preceq K_s^{-1}A_e.\] Thus the variance parameter is at most \(2/K_s\). The self-adjoint matrix Bernstein inequality, applied to both signs (Tropp 2012, Theorem 6.1(ii)), states that independent centered self-adjoint summands of norm at most \(J\) and total variance norm at most \(V\) satisfy \[\Pr\left\{\left\|\sum_eY_e\right\|\ge z\right\} \le2d\exp\left(-\frac{z^2}{2(V+Jz/3)}\right),\] where \(d\) is the matrix dimension. Here \(d\le2s'\), \(J=1/K_s\), \(V\le2/K_s\), and \(z=1/(4\chi)\) give the claimed probability bound. Testing the quadratic form on \(D^{1/2}\mathbf1_X\) gives additive error \(\mathop{\mathrm{vol}}(X)/(4\chi)\) in its cut weight. Testing the complement gives the other bound in (72). Testing a singleton bounds its weighted degree by \((1+1/(4\chi))d_i\); summing degrees proves the weight check.

Dyadic rounding gives \[\sum_ep_e\le2K_s\sum_{ij=e}(1/d_i+1/d_j) =2K_s\#\{i:d_i>0\}.\] The scalar Chernoff inequality therefore proves the sample-count check with failure at most \(\exp(-K_s\#\{i:d_i>0\}/3)\). If the threshold exceeds the total possible edge count, failure is of course impossible.

For (73), condition on all lists at this depth. They are disjoint sublists of the input, so the expected sum for \(x\) is at most \(C_0\). A nondeterministic summand \(\xi_e m_{xe}/p_e\) lies in \([0,10C_0/K_s]\), since piece degrees are at most \(C_0\) and \(1/p_e\le C_0/K_s\). After centering, its absolute value has the same upper bound. The sum of variances is at most \(10C_0^2/K_s\), by bounding each second moment by its maximum value times its expectation. Deterministic summands have zero variance. For an upward deviation of \(C_0\), scalar Bernstein consequently gives \[\Pr\{\text{sum}>2C_0\} \le\exp\left( -\frac{C_0^2}{2(10C_0^2/K_s+10C_0^2/(3K_s))}\right) \le e^{-K_s/30}.\] ◻

Proof. For a perfect matching let \(A\) be its averaging matrix: on each matched pair it replaces two coordinates by their average. Start with \(P_0=I\), and after round \(j\) set \(P_j=A_jP_{j-1}\). All these matrices are doubly stochastic. At a round’s start, let \(p_i\) be the current rows and choose a fresh vector \(\zeta\) of independent uniform signs. Order the real numbers \(\langle p_i,\zeta\rangle\), resolving ties by stub identifiers, and put their first and last halves on opposite sides.

Write \(\bar p=\mathbf1/N_p\) and \(\Psi=\sum_i\|p_i-\bar p\|_2^2\). The centered projected values \(z_i=\langle p_i-\bar p,\zeta\rangle\) have mean zero over \(i\), and \(Z=\sum_i z_i^2\) satisfies \[\mathbb EZ=\Psi,\qquad \mathbb EZ^2\le3\Psi^2.\] For the second inequality, sign fourth moments give \(\mathbb E\langle v,\zeta\rangle^4\le3\|v\|_2^4\), and Cauchy–Schwarz bounds each cross term in \(Z^2\). The elementary second-moment inequality now gives \(\Pr\{Z\ge\Psi/2\}\ge1/12\) when \(\Psi>0\). The sign tail estimate and a union bound over pairs give, with failure probability at most \(2N_p^2e^{-\Lambda/2}\), \[|\langle p_i-p_j,\zeta\rangle|^2 \le\Lambda\|p_i-p_j\|_2^2\quad\text{for every $i,j$}.\]

Choose a median value \(m\) between the two central centered values \(z_i\). For any pair \(i,j\) on opposite sides, \((z_i-z_j)^2\ge(z_i-m)^2+(z_j-m)^2\). Every stub occurs once in the matching, and the sum of squared distances is minimized at the mean, zero. Consequently, for every matching across the halves, \[\sum_{ij\text{ matched}}(z_i-z_j)^2 \ge\sum_i(z_i-m)^2\ge Z.\] The exact decrease under averaging is \(\frac12\sum_{ij\text{ matched}}\|p_i-p_j\|_2^2\). With conditional probability at least \(1/20\) this is at least \(\Psi/(4\Lambda)\). The parameter values ensure that the sign-tail failure above is smaller than \(1/12-1/20\). If \(\Psi=0\), it stays zero. Thus \[\mathbb E\Psi_{r_m}\le N_p\exp[-r_m/(80\Lambda)].\] For this analysis one can continue with arbitrary median-crossing matchings after a piece has been cut; hence stopping a piece early does not introduce conditioning on successful mixing. If any entry of \(P_{r_m}\) is below \(1/(2N_p)\), then \(\Psi_{r_m}\ge1/(4N_p^2)\). Markov’s inequality proves the stated failure bound.

It remains to identify which walk this product describes. Since \(P_{r_m}=A_{r_m}\cdots A_1\), its row starting at stub \(i\) describes averaging steps in the order \(r_m,r_m-1,\ldots,1\). Place one unit of mass at each stub of a set \(X\) with \(|X|\le N_p/2\), and run this reverse-round walk. All product entries are at least \(1/(2N_p)\), so at least \(|X|/4\) mass finishes outside \(X\). At every intermediate time, double stochasticity keeps mass at each stub at most one. A matching edge \(\{v,w\}\) at its single time step therefore carries total mass at most \((\mathrm{mass}(v)+\mathrm{mass}(w))/2\le1\). The number of overlay edge occurrences crossing \(X\) is at least \(|X|/4\). Every stub has degree \(r_m\), which proves conductance at least \(1/(4r_m)\).

The construction does not form dense products. To compute a new projection, apply the earlier matching averages in chronological order to \(\zeta\), obtaining \(P_{j-1}\zeta\). This costs \(O(jN_p)\) elementary averages. All entries are dyadic rationals with denominator dividing \(2^{j-1}\), so exact projections, comparisons, and tie resolution use \(O(r_m+\log N_p)\) bits per number. ◻

Proof. For any nonnegative vector \(f\) supported on at most half the degree volume, integrate the boundary sizes of the sets \(\{i:f_i^2>\xi\}\) over \(\xi\ge0\). The result is \[\sum_{ij\text{ edge}}|f_i^2-f_j^2| \ge\phi\sum_i d_i f_i^2.\] Cauchy–Schwarz, together with \(\sum_{ij\text{ edge}}(f_i+f_j)^2\le2\sum_i d_i f_i^2\), implies \[ \sum_{ij\text{ edge}}(f_i-f_j)^2 \ge\frac{\phi^2}{2}\sum_i d_i f_i^2. \tag{79}\] Both formulas remain valid with loops counted by their two incidences. For an arbitrary vector \(g\) of degree-weighted mean zero, subtract a degree-weighted median \(m\). The positive and negative parts of \(g-m\) each have support volume at most half. Their edge energies sum to at most that of \(g\), while their squared degree norms sum to \[\sum_i d_i(g_i-m)^2 =\sum_i d_i g_i^2+m^2\sum_i d_i \ge\sum_i d_i g_i^2.\] Applying (79) to both parts proves the nonlazy gap bound \(\phi^2/2\), by the Dirichlet quotient, and hence the lazy bound \(\phi^2/4\). The nonlazy reversible operator is a contraction in the degree-weighted Euclidean norm; making it lazy places its spectrum in \([0,1]\).

Apply its contraction on mean-zero densities to a point mass. Cauchy–Schwarz in the stationary inner product gives relative pointwise error at most \[\frac{\exp(-h\phi^2/4)}{\sqrt{\pi(x)\pi(y)}} \le\frac{\exp(-h\phi^2/4)}{\pi_{\min}}.\] Here \(\pi_{\min}\ge1/(D_cN_p)\), \(N_p\le M^2\), \(\phi\ge1/(4\Lambda^3)\), and \(t=\Lambda^{10}\). Thus the last expression is at most \(D_cM^2\exp(-\Lambda^4/64)<1/2\), establishing (78). ◻

Proof. First analyze ideal unlimited rejection, stopping the analysis when an inductive good event fails. The current degree ratio is allowed to be \(D_c\), initially one, with the allowance multiplied by \(20\) per level. Thus \[D_c\le20^{2a^2}\le\Lambda^{1/20}.\] The inductive conductance lower bound is \(1/(4r_m)\), so Lemma 28 applies. A group \(A\) occupies at least \(1/(2b)\) of the labels; hence \(\pi(A)\ge1/(2D_cb)\). An ordinary trial succeeds with probability at least \(1/(4D_cb)\). The endpoint of a successful trial has distribution \[ \frac{P^{2t}(x,y)}{P^{2t}(x,A)} \in\left[\frac14,4\right]\frac{\pi(y)}{\pi(A)} \subseteq\left[\frac{1}{4D_c|A|},\frac{4D_c}{|A|}\right] \quad(y\in A). \tag{80}\] Distinct final targets mean that at most \(|A|\) packets seek group \(A\). Packet arrivals at a specified child vertex therefore have expectation at most \(4D_c\), and Chernoff gives an upper bound of \(q_v\) with overwhelmingly high probability.

Exactly \(q_v|A|\) virtual jobs seek \(A\). If \(I_z\) counts their endpoints at \(z\), then \(\mathbb EI_z\le4D_cq_v\), and with overwhelmingly high probability \(I_z\le16D_cq_v\) for every \(z\). The child degree is exactly \(q_v+I_z\): a loop contributes its start incidence and its endpoint incidence. Thus every child degree is at least \(q_v\) and at most \((1+16D_c)q_v\le20D_cq_v\), proving the claimed next degree ratio.

For any \(X\subseteq A\) with \(1\le|X|\le|A|/2\), each of the \(q_v|X|\) jobs starting in \(X\) leaves \(X\) with probability at least \(1/(8D_c)\), by (80). Chernoff yields \[ \#\{\text{virtual edges from $X$ to $A\setminus X$}\} \ge\frac{q_v|X|}{16D_c} \tag{81}\] except with probability \(\exp[-q_v|X|/(64D_c)]\). Union over subsets by cardinality costs at most \[ \sum_{j\ge1}N_p^j\exp[-q_vj/(64D_c)]. \tag{82}\] For an arbitrary nontrivial cut, apply (81) to its smaller-cardinality side \(X\). Its volume is at most \(20D_cq_v|X|\), and the smaller of the two cut volumes is no larger than this volume. The child conductance is at least \(1/(320D_c^2)\ge1/(4r_m)\). This establishes all graph and packet invariants required at the next level.

We next bound loads of all jobs at one call before any substitution. Set \(Q=q_v\), \(W=\sum_i d_i\), and \(d_{\min}=\min_i d_i\). At most \(2Q\) jobs start at any vertex: there are \(Q\) virtual jobs and at most \(Q\) packets. At most \((Q+1)|A|\) jobs seek group \(A\), because virtual jobs seeking \(A\) start in \(A\) and packet final targets are distinct.

Fix an oriented incidence \(x\to y\) of a specific edge. At a step in the first half, the remaining suffix has at least \(t\) steps. Conditioning a job on its prescribed terminal group increases the probability of this step’s traversal by at most four: the ratio is \(P^h(y,A)/P^{2t}(z,A)\le2\pi(A)/(\pi(A)/2)\), where \(z\) is its start. Without conditioning, the aggregate initial density is at most \(2Q/\pi_{\min}=2QW/d_{\min}\) relative to stationarity, and the walk preserves this bound. A stationary lazy step traverses this oriented incidence with probability \(1/(2W)\). Therefore its expected conditioned load is at most \[ 4\frac{2QW}{d_{\min}}\frac{1}{2W} =\frac{4Q}{d_{\min}}. \tag{83}\]

In a second-half step, the prefix before traversal has at least \(t\) steps. If \(j\) steps remain after this incidence and the job seeks \(A\), its conditional traversal probability is at most \[\frac{2\pi(x)\,(1/(2d_x))\,P^j(y,A)}{\pi(A)/2} =\frac{2P^j(y,A)}{W\pi(A)}.\] Summing first over jobs seeking \(A\) and then over the groups gives \[\begin{align*} \sum_A\frac{2(Q+1)|A|}{W\pi(A)}P^j(y,A) &=2(Q+1)\sum_A\frac{|A|}{\mathop{\mathrm{vol}}(A)}P^j(y,A)\\ &\le\frac{2(Q+1)}{d_{\min}}\sum_AP^j(y,A) =\frac{2(Q+1)}{d_{\min}}. \tag{84}\end{align*}\] This calculation cancels the rare-conditioning factor group by group. In particular it introduces neither the number of groups nor a degree-ratio factor. Adding the two oriented incidences of an undirected edge, including the two incidences of a loop, bounds its expected traversal load at any step by \(24q_v\).

Conditional on the current input, different job streams are independent. At one fixed step, their indicators of traversing a fixed edge are independent Bernoulli variables, regardless of dependence between different steps of one job. Scalar Chernoff therefore bounds this load by \(\Lambda^6\) with overwhelmingly high probability. A union bound over edges and the \(2t\) steps gives total local edge load at most \(2t\Lambda^6\le\Lambda^{20}\); local walk lengths are also at most \(\Lambda^{20}\).

To account for substitution, suppose child routes have maximum length and edge congestion at most \(Z\). Initial packet walks contribute at most \(\Lambda^{20}\) load to a current edge. Each virtual-edge embedding is then used at most \(Z\) times, so all substitutions contribute at most \(Z\Lambda^{20}\). The same inequality bounds length, using the maximum embedding length. Starting at the leaves and iterating through at most \(2a^2\) levels bounds both quantities by \[ (2\Lambda^{20})^{2a^2}\le H_*. \tag{85}\]

For completeness, all probabilities just used are conditional on the actual recursively specified input. Endpoints chosen at a parent create the child graph, but at that child the new streams are fresh independent streams. This permits induction up to the first failed graph or packet invariant and avoids any assumption that the child graph is independent of its packet starts. The group-cut bound (82), all point-count and edge-step tails, and all cap tails are below \(M^{-40}\) with the parameters above. A conditioned job exceeds its trial cap with probability at most \[\left(1-\frac{1}{4D_cb}\right)^{\Lambda^3b} \le\exp[-\Lambda^3/(4D_c)],\] and a uniform incidence choice exceeds its string cap with probability at most \(2^{-\Lambda}\). Coupling capped rejection to unlimited rejection until the first cap justifies using these bounds with the ideal distributions.

Finally, the bounds on the work of a failed run require no good event. Packets never duplicate; each vertex always initiates exactly \(q_v\) virtual jobs; group sizes shrink by the fixed rule; and every trial and walk has an explicit cap. Across a router depth there are at most \(q_vN_p\) virtual edges, with incidence arrays for constant-index access. Even if congestion bounds fail, let \(\mathcal L_h\) bound a fully expanded packet route with \(h\) levels remaining. The newly sampled prefix has at most \(2t\) steps, and each edge of the child route expands to at most \(2t\) steps. Thus \[\mathcal L_0=0,\qquad \mathcal L_h\le2t(1+\mathcal L_{h-1}) \le\sum_{j=1}^{h}(2t)^j\le2(2t)^h \qquad(1\le h\le2a^2).\] This is a fixed power of \(\Lambda\). These deterministic size bounds also bound all elementary choice counts. Under \(P_*\le b\), a crude total of pieces, calls, edges, steps, and capped choices in an entire attempt is less than \(M^{20}\). A union bound thus proves the asserted router probability, with ample margin. ◻

Proof of Lemma 25. At a fixed cut depth, condition on its input lists before making its fresh samples. Lemma 26 applies to these lists even though earlier cuts were random. Likewise the median potential and the recursive routing estimates are conditional on their respective inputs. The sum of all bad-event probabilities in one attempt is less than \(1/2\) in the checked parameter range. Here are quantitative counts for this assertion. There are at most \(M^2(D_p+1)\) pieces and at most \(M^2\) resources having nonzero input data. The matrix and sample-count tails, resource tails, and product-mixing tails displayed above are each below \(M^{-40}\), including their per-piece factors. For the router, the group-cut union is bounded by (82); the point-count and edge-step tails use \(q_v=\Lambda^3\) and threshold \(\Lambda^6\); the rejection tails are the ones proved in Lemma 29. Each is below \(M^{-40}\). Their total number, including capped random-choice positions, is less than \(M^{20}\). These comparisons follow directly from \(\Lambda=2^{1000a^2}(1+u)\), \(a\ge10\), and \(P_*\le b\): every polynomial count in the listed powers of \(\Lambda\) is absorbed by the latter inequality, while every displayed tail has an exponent dominating a constant multiple of \(u\). All good events imply that the stage passes its verification.

After each unsuccessful attempt, the unchanged residual graph is tried again with fresh bits. Conditional failure probability is at most \(1/2\) per attempt; hence failure of all \(T\) attempts has probability at most \(2^{-T}\). Taking a union bound over at most \(2u+2\) stages, using \(u\le2\log_2 S\), gives \[(2u+2)2^{-T}\le2^{-\sigma}S^{-800}.\] This also proves the stated conditional guarantee for adaptive inputs. Taking the union of selected supports over accepted stages and retaining each demand’s first accepted walk yields (67), because \[(2u+2)\Lambda^{350a^2}\le P_*.\] Support and resource loads add over stages; maximum hop count does not increase when supports are united.

We finish with the cost on every path, including rejected attempts. At any fixed cut depth, piece edge counts sum to at most the starting edge count. Sampling scans their lists once. For each piece there are at most \(r_m\) flow calls, each on padded size \(P=O((1+\chi)s')\). Lemmas 2 and 4 bound their exact finite-word cost by padded size times \(M^{o_a(1)}\), uniformly over these local sizes. In particular, \(P\le O((1+\chi)M^2)\) and the flow primitive’s subpolynomial overhead at these sizes is \(M^{o_a(1)}\). The total padding over a depth is linear in its edge count times a fixed power of \(\Lambda\). The weight check (71) bounds flow throughput by (77) even for a sample with inaccurate cuts. Constructing all integral paths is therefore charged explicitly. Projecting sign vectors requires only repeated matching averages, \(O(r_m^2N_p)\) operations per piece, and never requires a dense matrix. Sorting projected values to choose each median costs \(O(N_p\log N_p)\) comparisons and is absorbed in the same logarithmic-power allowance.

At a completed piece, the initial overlay has \(r_mN_p/2\) edges. At each routing depth there are at most \(q_vN_p\) virtual edges and \(O(q_vN_p)\) jobs across its calls. Store all incident-edge arrays explicitly, so a walk step does not scan a neighborhood. A job uses at most \(\Lambda^3b\) trials, each of \(2t\) steps, and each incident choice has at most \(\Lambda\) bit-string trials. These caps supply the sole additional nonlogarithmic factor \(b\). The deterministic recursion-depth and substitution bounds from Lemma 29 control intermediate walk-list sizes even on bad random outcomes. Long real embeddings are filtered before substitution; all remaining expansions have a further factor of at most \(L_0\). Thus explicit output construction is also linear in the input size times \(b\) and a fixed power of \(\Lambda\).

Finally, sparse dictionaries translate original labels, edge identifiers, and resource names to local indices and back. Verification first counts traversals by selected edge and then scans its resource list, so a large resource list is not recopied at every traversal. All comparisons, capacity operations, resource-load products, and dyadic averages use bounded multiword integers. In particular, the projection denominator has at most \(r_m\) binary digits; local path lengths and load counters have the deterministic size bounds just proved; and all input bit strings have the assumed logarithmic-power width. The normalized matrices, potentials, and stationary probabilities are used only for analysis; the algorithm never computes their square roots or eigenvectors. The sampling probabilities are found by exact integer comparisons, and an event of probability \(2^{-j}\) is drawn using \(j\) fair bits. Here \(j\le2u\), since the positive piece degrees are at most \(M^2\). Each random sign uses one fair bit. The ordinary multiword implementations of all arithmetic operations add only logarithmic powers for fixed \(a\). Individual generated bits, initialization of arrays, allocation, and movement of these records are included in the same charges. Multiplication by the capped numbers of cut depths, routing depths, stages, and attempts leaves precisely (68). Since all caps are enforced independently of the good events, this is a bound on every computation path. ◻

Proof. Replace each undirected edge by its two possible traversals. For each dyadic threshold \(\rho=2^j\) with \[-(G_d+2)u\le j\le (G_d+1)u,\] give these two arcs costs \(\rho\ell_e-\gamma_e\) and \(\rho\ell_e+\gamma_e\), respectively. For every start vertex, tabulate minimum costs of walks with each number of arcs from zero through the number of vertices, retaining predecessor pointers. This detects a negative closed walk whenever one exists, because a negative closed walk contains a negative simple directed cycle. Keep a witness for the largest successful threshold, and return its exact absolute-gradient to raw-length ratio.

To justify the approximation, negate a nonzero signed circulation if necessary to make its gradient nonnegative. Orient its used edges along their coefficient signs and decompose the resulting nonnegative directed circulation into simple directed cycles. Gradient and length add in this decomposition, so one cycle has ratio at least that of the circulation. Conversely, any positive-ratio directed cycle projects to a nonzero signed circulation; its projected length norm is at most its raw length. It follows that \(\mathop{\mathrm{OPT}}_d\) is attained by a directed cycle. Integer gradients and positive integer lengths give \[\frac{1}{n_d M^{G_d}}\le\mathop{\mathrm{OPT}}_d\le M^{G_d} \qquad\text{if }\mathop{\mathrm{OPT}}_d>0.\] The tested thresholds cover this interval with room on both sides. The largest successful threshold is at least \(\mathop{\mathrm{OPT}}_d/2\), and its negative walk has still larger ratio. The witness has at most the number of vertices in the graph.

There are \(O_a(1+u)\) thresholds. The elementary tables take at most \(O(n_d^3)\) arithmetic operations per threshold, since both the vertex and arc counts are \(O(n_d)\). All costs have \(O_a(1+u)\) bits after a common dyadic scaling. This proves the stated bound, including charged multiword arithmetic, without a forest at the bottom level. ◻

Proof. Independently for each partition, give every vertex \(c\) an integer delay \(X_c\) with \(\Pr[X_c\ge t]=2^{-t}\) for nonnegative integers \(t\). At \(v\), choose the center maximizing \[ R_jX_c-\mathop{\mathrm{dist}}_{\bar G}(c,v), \tag{94}\] breaking ties by center identifier. Reject the attempt if any delay exceeds \(\Gamma\). A vertex’s own center has nonnegative score, so its winning center is at distance at most \(\Gamma R_j\). Dominance of a center persists along a shortest path towards it: the triangle inequality preserves every score comparison, including the common identifier tie rule. Hence a shortest-path tree to the center lies inside the winning cell.

For each vertex also compute the runner-up among distinct centers. Verify that at each layer every vertex has, in some partition, winning margin greater than \(2R_j\). The difference between the scores of two centers changes by at most twice the distance moved. Thus this check implies containment of the whole closed \(R_j\)-ball. A runner-up in another connected component has score minus infinity and causes no difficulty.

For unlimited geometric draws, fix a vertex and all delays except that of a proposed winner \(c\). The event that \(c\) wins is a lower integer threshold on \(X_c\), truncated below at zero. Exceeding that threshold by three raises its score by \(3R_j\) and gives margin greater than \(2R_j\). The geometric tail assigns probability at least \(1/8\) of the winning-event probability to this overshoot. Summing over the disjoint winning events gives margin probability at least \(1/8\). Independence of the partitions and a union bound therefore bound the probability that the delay or coverage checks fail by \[ rK_hn_i2^{-\Gamma}+rn_i(1-1/8)^{K_h}<\frac12. \tag{95}\] The displayed inequality follows from the chosen scales in the checked parameter range. Repeat with fresh draws at most \(2(\sigma+1000\log_2 S+10)\) times. Exhaustion is a detected failure; its probability is at most \(2^{-\sigma}S^{-800}\).

Generate a geometric delay by fair bits, stopping and rejecting when its cap is exceeded. Shifted distances and the best two distinct center labels are computed by multi-source Dijkstra with initial offsets \(-R_jX_c\), finalizing at most two distinct origins at each vertex. An origin among the best two at a vertex has prefixes among the best two along a shortest path; otherwise two strictly preferred origins at a prefix would remain preferred at the endpoint. Thus this truncation loses neither of the required origins nor a winning tree pointer. Initial offsets can be negative because edge lengths are positive. Each partition needs only near-linear integer graph work. The layer, partition, delay, and repetition counts are fixed powers of \(1+u\) for fixed \(a,\sigma\), and their integer data have fixed-parameter logarithmic bit length. This proves the every-path cost bound. ◻

Proof. At a given layer choose a bit position of the slot index and two partition options, using the chosen option as a function of that bit. Include constant functions as well. Two distinct indices differ in some bit, so any two prescribed options can be realized. Choose these functions independently at the \(r\) layers and include every choice in the family. There are at most \(2K_h^2(u+1)\) choices per layer, giving the claimed bound.

Orient each cell tree towards its root, and the links towards higher layers. Every vertex has outdegree at most one and there is no directed cycle. Such an underlying undirected graph is a forest: an undirected cycle would, by its edge count and outdegree bound, force a directed cycle. This also proves the asserted structure of each \(T^0\). ◻

Proof. The functions in (97) are one-Lipschitz on a connected component. At two vertices, at most \(2K_h\) cell weights can be nonzero, since a positive weight requires membership in the cell. Comparing normalized weights along \(e=vw\) yields \[ \mathop{\mathrm{TV}}(\mathcal L_j(v),\mathcal L_j(w)) \le\frac{4K_h\ell_e}{R_j}. \tag{98}\] Indeed the sum of absolute unnormalized changes is at most \(2K_h\ell_e\), and total variation of the normalized laws is at most that sum divided by the smaller normalizer.

Starting at \(V_0(v)\), use the chosen cell at layer one, then its tree path to its center and the IN link to the corresponding \(V_1\) vertex. Continue likewise. At layer \(j\ge2\) the previous representative is the center of a cell containing \(v\), so its distance from \(v\) is at most \(\Gamma R_{j-1}\). The second check in (92) implies \(b>2\Gamma\), and therefore \[\Gamma R_{j-1}<R_j/2.\] Every positive next-layer choice contains that representative, so its OUT option exists. This defines \(P(v)\) using independent choices across layers and a marginal law fixed by \(v\) alone.

For the endpoints of \(e\), couple their cell choices maximally at each layer, independently between layers. At the top, \(R_r/2\) exceeds every finite component diameter: such a diameter is at most \(n_iM^{G_i}\), whereas \(R_r=M^{1210a+3}\). A top-layer cell with positive weight at a vertex must consequently contain its whole connected component. All such cells have weight \(R_r/2\) at every vertex of that component. The two endpoint laws therefore coincide at the last layer and can be coupled to agree, including the partition identity.

Retain the two arms through one layer after their last cell disagreement; if there is no disagreement, retain layer one. From then on their representative and choices coincide, so their suffixes are identical and cancel. Two arms at layer \(j\), including their OUT and IN links, cost at most \(4\Gamma R_j\). For \(j\ge2\) this layer is retained only if a disagreement occurred at some layer \(l\ge j-1\). Equation (98) and a geometric sum bound that probability by \[\sum_{l\ge j-1}\frac{4K_h\ell_e}{R_l} \le\frac{8K_h\ell_e}{R_{j-1}}.\] Including the original edge and the first layer, the expected length is consequently at most \[\ell_e+4\Gamma b+ \sum_{j=2}^r32\Gamma K_hb\ell_e \le64r\Gamma K_hb\ell_e=A_*\ell_e.\] The coupling changes none of the prescribed per-vertex marginals. ◻

Proof. Apply the preceding coupled-walk decomposition separately to each surviving frozen edge, weighted by its signed coefficient in \(\Delta_s\), and take expectations. There are finitely many choices in these conceptual distributions. Collecting coefficients of the oriented family chords gives \(\alpha_f\); collecting the signed route parts on the raw copies gives \(z\). Only surviving input edges and null pair chords are used as chords, so every indexed chord is live. The triangle inequality and Lemma 33 give (100) and (101), as well as the exact identity (99).

Although the couplings may differ between incident edges, the law of each endpoint path is fixed. Summing the route term \(P(w)-P(v)\) over oriented edges therefore gives (102). Cancellation of identical final suffixes does not change this signed vector. Because \(\Delta\) is a circulation, the displayed imbalance of \(\Delta_s\) is the negative of that of \(\Delta_n\) and vanishes away from new-edge endpoints.

Finally delete every coordinate of every tree copy mapped to a dead frozen edge. Projection after this deletion is the same as restriction of the projected physical vector. Restricting (99) therefore proves (103), even when coefficients on a dead edge had canceled between different copies. No circulation property is asserted for an individual clipped cycle. ◻

Proof. Root each tree arbitrarily. Accumulate the number of still-connected unmarked vertices in the subtrees of a vertex, including the vertex itself. If the accumulated count is at least \(k\), mark that vertex as a portal and pass count zero to its parent. Every mark charges a disjoint group of at least \(k\) vertices. In any component off the marks, the residual count at its highest vertex is exactly its size and is below \(k\). ◻

Proof. Deleting an edge outside a terminal Steiner subtree leaves a side containing no terminal. The sum of divergences on that side is zero, so the edge coefficient is zero. At an internal degree-two nonterminal of a remaining segment, zero divergence forces the two consistently oriented coefficients to agree. Replacing that segment by an edge with summed length and signed gradient consequently preserves both its gradient contribution and its length norm. ◻

Proof. Use the coefficients and raw vector of Lemma 34, and form on the child edges \[ \Xi_0=\sum_f\alpha_fJ_f-\widehat z_L+\Delta_n, \tag{110}\] with \(\Delta_n\) carried by the hub-to-hub new edges. Its physical projection is \[\pi\Xi_0=\Delta-\sum_f\alpha_f\pi B_f,\] a physical circulation. Since \(W_f\le2w_f\), the norm estimates give \[\begin{align*} \|\ell^J\Xi_0\|_1 &\le 2Z_*A_*\|\ell\Delta_s\|_1 +A_*\|\ell\Delta_s\|_1+\|\ell\Delta_n\|_1\\ &\le4Z_*A_*\|\ell\Delta\|_1. \tag{111}\end{align*}\] The vector \(\Xi_0\) need not balance at each compressed copy of a physical vertex. Route its imbalance there along the null edge to that vertex’s hub. The hub then balances because the sum of divergences over all copies with its physical image is zero. The total absolute imbalance at the compressed vertices is at most twice the sum of absolute coefficients of \(\Xi_0\), and hence at most twice its length norm, since every child edge has length at least one. The resulting child circulation \(\Xi\) therefore satisfies \[ \pi\Xi=\pi\Xi_0,\qquad \|\ell^J\Xi\|_1\le12Z_*A_*\|\ell\Delta\|_1. \tag{112}\] Its gradient equals that of its projection because all connectors have zero gradient.

For the local part, (107) and (100) give \[\left|\sum_f\alpha_f\gamma^{\mathsf T}\pi B_f\right| \le L_{\mathrm{best}}Z_*\sum_f|\alpha_f|W_f \le2Z_*A_*L_{\mathrm{best}}\|\ell\Delta\|_1.\] The child circulation contributes at most its norm times \(\mathop{\mathrm{OPT}}(J)\), with the same conclusion if it is zero. Adding these inequalities proves the first bound in (109). The second follows from \(14Z_*A_*\le20Z_*A_*\le b^2\).

Every distribution, coupling, coefficient, and comparison vector in this proof is existential. The algorithm constructs only integral graphs, terminal sets, path assignments, and rational scores. Once the covers and assignments have their verified properties, the argument applies to any state and any circulation chosen afterwards. This proves the asserted adaptive scope. ◻

Proof. At the bottom use Lemma 30. At a higher level compare the local correction scores, exact current-loop scores, and the recursive child score. Lemma 43 preserves the child gradient under lifting and does not increase raw actual length, so the child’s certified score remains valid. If its approximation factor is \(\eta\le1\), the maximum of its score and \(L_{\mathrm{best}}\) is at least \(\eta\max\{L_{\mathrm{best}},\mathop{\mathrm{OPT}}(J)\}\). Apply Lemma 37 to lose at most \(b^2\) at this level. Exact loop candidates give the same conclusion for the full graph. This proves (113) by induction.

Since \(d=2a-4\), the outer factor is \(\tfrac12M^{-(4a-8)/a^2}\), which exceeds \(M^{-10/a}\) in the checked range. A zero optimum does not require a positive answer. The representation size, explicit forest logs, and total operation cost are established next; the quality argument itself has incurred only one recursive child call at each level. ◻

Proof. Call a chord regular when its frozen fundamental tree path meets the initial portal grid. The nearest-portal regions are connected: along a shortest tree path toward the chosen portal, the distance comparison with every competing portal persists, as does the global index tie rule. A region consists of its portal and parts of the adjacent pockets, and therefore has at most \(1+kD_T\) vertices.

The target of a regular incidence is the first hole on its fixed path toward its original portal, stopped on the incidence side, or the portal if there is no such hole. For a fixed bucket, all current legs crossing a newly cut edge belong to one old class. Indeed that edge lies in one nearest-portal region, and their earlier truncation, if present, is the first hole on their common suffix toward the portal. Split this class by moving the crossing incidences to the incidence-side endpoint of the new cut. This target is determined by the newly cut parent edge toward the portal, so no merging is needed. Give both children fresh labels, even when one is empty or one retains the old target.

For a nonregular chord, use the two depth-band clusterings described in Section 7. The first interior cut activates the cluster and creates two fresh fragment classes. Every newly active chord has both incidences in these new classes, including chords whose two incidences lie on the same side. Thereafter cuts split fragment classes, again with fresh labels on both sides. Classes in different clusters remain distinct even if their targets are the same tree node. Each cluster is contained in an initial pocket. Its number of incidences, and that of any regular region, is bounded by (114). The two incidences of a logical loop are counted separately.

An old actual-edge deletion creates only a logarithmic factor many holes and chord deaths in all copies. In one width bucket, a hole is interior to at most one cluster in each of the two shifted band partitions, and it causes at most the regular split just described. A newly inserted physical edge creates no frozen chord. These facts give the asserted number of units.

Here is an explicit way to list and process them. At freezing time, compute tree ancestor tables, length and oriented-gradient prefix sums, portal mark counts, nearest portals, pockets, and cluster membership. The band index at a pocket vertex is an integer quotient of its weighted depth; connected components of equal band index give the clusters. No record is allocated for an empty band. These computations take near-linear tree work up to logarithmic factors and determine the relevant path sums without scanning each fundamental path. Initial regular legs have at most \(k+1\) tree edges, so their membership lists on tree edges can also be built explicitly. On a hole, inspect the region-bounded lists, discard dead incidences and legs already stopped before this hole, and update the remaining class lists. A cluster cut can inspect the whole small cluster and its chord incidences.

Before activation, keep each direct fundamental-cycle score in a heap using its frozen sums. Delete its entry when the chord dies or its cluster activates. For an input death, physical chord removals can be processed before the splits and activations that it causes. Afterwards every surviving active leg is the unique live tree path to its stored target. A leg whose class has not split retains that path and its gradient. This also proves the last assertion. ◻

Proof. Mark labels of the snapshot at \(t_0\) as follows. Every split marks its ancestor at \(t_0\), if one exists; every chord death marks the ancestors of both endpoint classes. Let \(Y\) be the marked set. Then \(|Y|\le2E_0\). The anchors are all current descendants of \(Y\) and all current classes born from activations after \(t_0\), including their later descendants. There are \(O(E_0)\) anchors: initially marked labels contribute at most \(2E_0\), and every subsequent split or activation adds only constantly many class labels. Ancestors absent at \(t_0\) belong to the latter activation families.

Mark every old assigned path that visits \(Y\), including at an endpoint. In particular the path of a deleted demand is marked, as is any path using a deleted support edge. Every unmarked path still uses the same live oriented chords on unchanged labels. Moreover its demand and all support edges on the path retain the same legs and leg gradients, by Lemma 39. Thus its correction \(B_f=L_f-L_{\Pi_f}\) has exactly the stored gradient. A hole outside these legs can change the clipped comparison vector, but does not change this correction. Inactive direct-cycle candidates are handled separately by their activation lists.

Consider a marked old path whose demand \(e\) survives. Follow its prefix from the tail to the first marked label. Every preceding label is unsplit. Every edge of this prefix is live: if one had died, its earlier endpoint’s old label would also have been marked. The final edge now ends at a current descendant of the first marked label. Interpreting the same oriented edges therefore gives a current path \(A_e\) from the current tail to an anchor. If the old path starts marked, \(A_e\) is the empty path at the current tail. Reversing this argument gives a suffix \(Z_e\) from a current anchor to the current head at the last marked label. Repeated splits cause no ambiguity, since the current incidence of the last prefix edge specifies its current descendant. For newly activated demands use empty \(A_e,Z_e\); both endpoints are anchors by the activation rule.

For each such demand put an edge in a core graph on the anchors, associated with the direct logical walk \[ -A_e+e-Z_e. \tag{119}\] Its orientation is from the end of \(A_e\) to the beginning of \(Z_e\); a minus reverses a path. For every current base class use its number of visits on this direct walk as a resource count. Each count is at most two. Indeed the prefix and suffix each come from a simple old path, with at most their final marked label replaced by a descendant; the two resulting vertex lists concatenate across \(e\). This also covers empty prefixes, suffixes, and a loop demand. The total resource count at a class, over all direct walks, is at most \[ C_0=2C(j-1)+D_\ell. \tag{120}\] Prefix visits and suffix visits of old demands charge separately to visits at that class’s old ancestor; newly activated endpoint incidences charge to its current degree. The same bound controls the core demand degree, because its endpoint incidences are among these resource visits.

Apply Lemma 25 to the core with the resources just defined. Lift its assigned walks by substituting (119), and for demand \(e\) prepend \(A_e\) and append \(Z_e\). Simplify the resulting walk to a simple path, erasing the whole walk if its endpoints coincide. Cycle erasure never increases hops or resource visits. The hop count before simplification is at most \[ 2p(j-1)+P_*\bigl(2p(j-1)+1\bigr)\le p(j). \tag{121}\] The substituted helper walks cost at most \(P_*C_0\) visits at each class. The added prefixes and suffixes cost at most \(2C(j-1)+D_\ell\), including the empty paths; the unchanged assignments add at most \(C(j-1)\). Thus a valid upper bound is \[P_*\bigl(2C(j-1)+D_\ell\bigr)+3C(j-1)+D_\ell \le100P_*C(j-1)=C(j).\] All edges in the prefixes and suffixes were already live support edges. Only the central chords of the selected core edges must be added to support. The core has \(O(E_0)\) incident labels, regardless of how many old paths met \(Y\), so the helper selects at most \(O(P_*E_0)\) such chords. When \(E_0=0\) the old snapshot can simply be retained.

For completeness, the implementation does not copy whole snapshots. Each held snapshot consists of immutable balanced-dictionary roots for paths keyed by demand, an index from class to its visiting paths, and an ordered collection of correction-score keys. Path copying changes only the search paths of modified dictionary entries. Begin with the parent roots and replace marked or dead records and add the newly active records. The class index enumerates at most \(C(j-1)|Y|\) old path occurrences before their lists are read; a dictionary removes duplicates. Activation lists enumerate new demands. Every such path has logarithmic-factor length, and the number of newly activated demands is at most \(O(D_\ell E_0)\).

Store split-parent pointers with class birth ticks and jump pointers. To find the ancestor at \(t_0\), follow this history to the class alive at the end of tick \(t_0\). All splits within one tick belong to that tick and snapshots are taken only after settlement, so equal birth ticks do not create a partially settled ancestor. Physical chord identifiers, the two current incidence classes, and their targets are explicit records. They determine the oriented lifted prefixes and suffixes. Frozen tree prefix data gives each live leg’s gradient and length; summing over the new short logical paths recomputes their correction-score keys. Unmodified keys remain valid by the unmarked path argument.

Building the direct lists and the helper’s resource lists, simplifying its output, and changing the indices costs \(O(1+D_\ell E_0)bM^{o_a(1)}\) by Lemma 25. Comparing the maintained best keys over the logarithmic-factor many tree–width graphs has only logarithmic overhead. The helper’s input prerequisites can be checked: twice the demand count and the nonzero resource-list length must each be at most \(M^2\). They hold for all sufficiently large \(M\) at fixed parameters, since even all frozen chords number at most \(O(n_i)\) times a logarithmic factor, and every direct walk has logarithmic-factor length. This proves the work assertion and both snapshot invariants. ◻

Proof. Initially the number of portal classes, summed over all tree–width graphs, is at most \((n_i/k)\) times a logarithmic factor. The helper selects at most \(P_*\) times this many chords. At inner level \(j\) there are at most \(\lfloor t'/s_j\rfloor\) rebuilds, each using an interval of at most \(bs_j\) ticks. By Lemma 39, the sum of their interval edit counts across all tree–width graphs is at most \(bs_j\) times a logarithmic factor per rebuild. Consequently the cumulative support additions at that level are at most \(bt'\) times a logarithmic factor by Lemma 40. There are at most \(a^2\) inner levels. Summing (118) similarly bounds the local work by \(t'D_\ell b^2\) times a logarithmic factor, in addition to smaller constant-per-rebuild and log-scanning costs. Since \(D_\ell=(k+1)\log^{O_a(1)}(2+M)\), this has the asserted exponent with an absolute coefficient. Initial tree preparation, the explicit short regular-leg lists, and initial helper calls fit the stated initialization bound. A physical removal lists the deaths of selected copies in logarithmic-factor work. Keeping earlier live selections therefore requires no additional support budget. ◻

Proof. Initial terminal promotions number at most \(h_i\) times a logarithmic factor. Subsequent promotions come from hole endpoints, new class targets, endpoints of selected support chords, and the raw-hierarchy route endpoints needed for new physical incidences. The first three counts follow from Lemmas 39 and 41. For the fourth, enumerate the \(K_h^{O(r)}\) possible sequences of partition options from the given physical slot. At each step look up the entering copy and its frozen cell root in stored tables. This lists the needed endpoints without traversing the raw legs. It costs a logarithmic factor per incidence. Thus the cumulative additional promotions on a prefix number at most \(bt'\) times a logarithmic factor. Retain all promoted terminals until the epoch ends.

Build each initial Steiner subtree in bulk, using subtree terminal counts. To promote one additional tree node, split its current compressed segment if it is already in the represented subtree. If it is outside, explore its hanging component to the unique attachment and add the joining path, splitting the segment at that attachment if needed. If the live component has no represented subtree, create an isolated terminal. The explored exterior component contains no initial portal, and hence lies within one original pocket of fewer than \(k\) vertices. Existing segments have at most \(k+1\) constituent edges. Membership and segment pointers on these nodes, together with local forest adjacency, therefore suffice for \(O(k+1)\) times degree and logarithmic-factor work. Only \(O(1)\) compressed vertices and edges change per promotion. No whole live component must be relabeled.

Before cutting a frozen tree edge, promote both endpoints. The edge is now itself a compressed segment and can be deleted. On either side, every other represented edge still separates terminals: a terminal formerly reached across the deleted edge is replaced for this purpose by its now-terminal endpoint. Thus there is no pruning or merging cascade. Keep each segment’s full constituent list with orientations. A changed segment or changed realization is removed and replaced by a fresh edge, with deletion first.

Assign each represented frozen tree or raw-forest node its own child slot, without reuse in this invocation, and assign at most one hub per physical label. A selected chord remains attached at its original tree-node endpoints. Its logical leg targets can therefore change in bulk without migrating its child edge. New actual nonloops are inserted directly between hubs and removed at their deaths; actual loops have already been handled by the loop heap. These rules establish the claimed size and edit counts.

Reserve \(\lfloor n_{i+1}/2\rfloor\) child slots, with unused slots isolated, and check both assignment overflow and total slots plus current edges against the child’s capacity. For fixed parameters these checks hold eventually, because \[ n_{i+1}=h_iM^{1/(2a)},\qquad b=M^{1/a^2},\qquad \frac1{a^2}<\frac1{2a}. \tag{122}\] The active-slot and edge bounds above are consequently smaller than either reserved half for all sufficiently large \(M\).

At a compressed node, segment degree is at most its frozen tree degree; add its chord degree and one hub connector. At a hub, the connector degree is bounded by the number of frozen tree and raw-forest copies of its physical label, plus the current new actual incidences. Both are logarithmic factors. Deleting old segments before adding replacements preserves these degree bounds even during the child edit sequence. This proves the degree hypothesis inductively from the degree-three outer input.

A segment sums prices over at most \(k+1\) edges, so its positive integral length and absolute gradient are at most \((k+1)M^{G_i}\le M^{G_i+2}=M^{G_{i+1}}\) for adequate parameters. Other child prices are inherited or are \((\ell,\gamma)=(1,0)\). The local work includes an \(O(k+1)\) factor per promotion or changed segment and the assignment work already bounded. Its exponent is therefore \(O(1/a)\) with an absolute coefficient. Only the smaller edit count proved above is passed into the recursive time bound. ◻

Proof. Contract every arm-slot tree to its center. On assigned slots the connector quotient is exactly the active subforest of \(F^J\). Dormant slots have no connectors. A cycle in the expanded graph would give a cycle in this quotient, since each contracted part is itself a tree. Together with the disjoint full copies, the result is a forest.

Expand each edge on an oriented child path using the prescribed arm and connector, or its nonsegment connector. The concatenation has the expanded signed projection of that child path. Segment length is the sum of its constituent parent lengths; null child edges contribute zero parent raw length, and other child null realizations can only decrease it. Thus the concatenation’s parent raw length is at most the sum of child-edge lengths counted with their traversal multiplicities.

This concatenation may backtrack, even when the child path is simple, because several connectors can use the same arm in one slot. In a forest, deleting a consecutive edge and its reverse preserves the signed count of every oriented edge and decreases nonnegative raw length. Repeating this deletion leaves the unique forest path between the assigned endpoint centers. It therefore has exactly the needed projection and no larger raw length. We return its endpoints; we do not perform these cancellations by expanding the walk. If the child path has an inactive endpoint, its whole component is one of the ignored null components, so the piece can be omitted.

For a piece given as a single child segment, use its endpoints in the appropriate full live forest copy. For a nonsegment piece, return its actual edge or omit its null realization. Each edge expansion has divergence equal to its mapped endpoint divergence. Summing a child circulation therefore gives zero physical divergence and preserves its gradient. In particular a positive child score gives positive gradient magnitude after lifting and therefore positive parent raw length. Its score remains a valid lower bound for the lifted ratio.

Only endpoint and slot lookups are needed in these conversions; no long lifted path is traversed or priced anew. A local correction uses \(O(p_*)\) pieces in full copies and individual actual chords, with opposite traversals explicitly reversed and null chords omitted. An actual loop uses one piece. A child answer gives at most as many parent pieces as it had child pieces. At each level we return one best candidate, rather than concatenating candidates from several levels. The bottom answer has at most \(n_d=M^{2/a}\) pieces. Taking the maximum of these bounds proves the last assertion. Every listed piece has unit multiplicity; repetitions, if present, are listed and charged. ◻

Proof. Full copies contribute a logarithmic factor. For one compressed frozen forest, segment interiors are disjoint. Thus a node in such an interior occurs in at most two arms per pool index, one from each endpoint of its segment. At a compressed endpoint, its own centers and the far tips of arms from adjacent endpoints contribute at most one plus its tree degree per pool index. These bounds include dormant slots. A physical input label has only a logarithmic factor many frozen-tree and raw-forest copies, and at most one hub. Consequently its total multiplicity is at most \[ (1+D_{i+1})\log^{O_a(1)}(2+M). \tag{124}\] There is no factor of the segment length in this bound. The \(b^2\) gap between \(D_i\) and \(D_{i+1}\) absorbs the logarithmic factor for sufficiently large \(M\). Induction starts with the empty bottom forest. Finally \[D_0=M^{(4a-8)/a^2}\le M^{10/a}/4\] eventually. Both the inductive multiplicities and the last inequality may be checked as deterministic prerequisites. ◻

Proof. First compute the batch of individual \(J\) edits for this parent operation, without a child query, and determine \(Q\). Its size is bounded by a constant times the exogenous child edit and assignment counts of Lemma 42. Retain access to the old occurrence assignments and old child forest records. Run the child edit sequence while maintaining a passive copy of its logs, indexed by lifetime identifier and label, with individual incidence lists. Track which records were added or removed. Each log changes only its own dictionary and incidence-list entries and costs logarithmic overhead. In particular deleting an occurrence does not trigger an uncharged degree scan: its incident edge deletions have their own records. Persistent roots or saved old records retain the old information until the parent transaction is complete.

At labels in \(Q\), remove all old arm pools and construct the final active pools with final occurrence assignments. Sweep their old and final incident child edges as well, to remove and reconstruct the corresponding connectors. To bound these sweeps, fix a label \(q\) in either the old or the final state and let \(N_J(q)\) be its set of distinct other neighbors. Every child forest edge incident to an occurrence over \(q\) belongs to the forest induced on the occurrence sets over \(\{q\}\cup N_J(q)\). That forest has at most \[ D_{i+1}\bigl(1+|N_J(q)|\bigr) \le D_{i+1}\bigl(1+\deg_J(q)\bigr) \tag{126}\] vertices, and hence no more than this many edges. Parallel child-graph edges only increase the safe degree bound. A child-null edge has both ends over \(q\) and is already included. This proves the bound separately for the old and final sweeps; old lists can be saved before applying the child batch. Constructing each arm takes at most \(k+1\) constituent steps. The degree bound on \(J\) now gives the first term of (125).

At every unaffected active label, retain the arm pools and the assignments of retained occurrences. First free assignments of deleted old occurrences, then assign each final new occurrence from a free-slot stack. There is sufficient space because the final occurrence count is at most \(D_{i+1}\). Remove the old connectors for changed child edge records and add the necessary final ones; also handle the connectors found in the affected sweeps. Additions can wait until all final assignments exist. Deduplicate swept records by identifier. Transient child records that are neither old nor final need not be published by the parent, although their individual processing is charged.

If a child edge and both its assignments survive unchanged at unaffected labels, its connector retains the same map. Every other change at these labels has an explicit child edge record: an occurrence replacement logs its incident edge removals and new edges, and an edge endpoint or map change is itself a replacement. Thus the remaining work is logarithmic per child record, giving the second term in (125). A high-degree child occurrence can have many incident records, but each is processed once; it does not add a degree sweep to each record. Child lists over inactive slots are likewise kept passively until activation, which places their label in \(Q\).

Full-copy hole edits are performed separately. Every public map to a dying parent input edge is removed: it lies in a full copy that receives the cut, in an arm of a changed or removed segment whose endpoints are in \(Q\), or in a connector realizing a removed nonsegment child edge. Remove connectors before their old pool vertices, and all old edges before their vertex deaths. After these removals the retained public graph is a subforest of the final graph, so its final pools, vertices, and connectors can be inserted in a valid order.

During this computation the child sees only its abstract slots, edges, and integral prices. An intermediate child state may still contain the old realization of a parent segment whose physical edge is about to die. Its abstract graph remains an in-range input, and it never asks for parent physical data. Only the final child state must be the reduction of the new parent input. The parent therefore publishes one old-to-final transaction, using retained old data for all removals, rather than a lifted public state for every intermediate child edit.

Finally, a dormant arm slot at an unaffected label retains all its internal edges when assigned to another occurrence. Their identity is determined by the child label, pool index, and incident segment realization, not by the assigned occurrence identifier. Existing signed and absolute accumulations in the client’s path tracker consequently remain attached to the same mapped edges. No \(D_{i+1}\) or \(k\) factor multiplies the processing of general child-internal occurrence changes. ◻

Proof. Give the child its arbitrary nonempty initial graph directly. The parent’s own initialization costs \(n_iM^{O(1/a)+o_a(1)}\). This includes tree preparation, initial assignments and compression, full forest copies, and initial arm pools. Initially there are only \(h_i\) times a logarithmic factor many active child labels; each has \(D_{i+1}\) pools and arms of at most \(k+1\) steps. Since \(D_{i+1}\le M^{4/a}\), this cost has the required absolute exponent. Epoch teardown and its public logs obey the same allowance. Allocations and eventual deallocation are charged; a discarded arena can be reclaimed against its earlier allocations.

By Lemmas 41, 42, and 45, all local incremental work costs \(M^{O(1/a)+o_a(1)}\) amortized per input operation. In particular the cumulative affected-label count in an epoch prefix is only \(b\) times a logarithmic factor per parent edit. Queries use the maintained best keys and lift one answer, with logarithmic overhead per child piece. They need not alter the public forest.

Let \(L=M^{C/a+o_a(1)}\), for an absolute constant \(C\), dominate these local factors and the bottom-level costs. Such an absolute \(C\) exists: all nonlogarithmic local factors above are fixed powers of \(b\), \(k\), and \(D_{i+1}\); at the bottom the elementary negative-cycle computation is a fixed-degree polynomial in \(n_d=M^{2/a}\). Factors involving \(r,a^2,P_*,p_*\) and degree bounds are fixed-parameter logarithmic factors.

Initialization of the child contributes \(n_{i+1}A_{i+1}\), with logarithmic overhead on its logs, and \(n_{i+1}/n_i=M^{-1/(2a)}\). At most \(1+s/h_i\) parent epochs start. After initialization the child receives at most \(bM^{o_a(1)}\) times the parent operation count, including the one recursive query used for a parent query. Only a logarithmic factor multiplies child log-processing work, by Lemma 45. Consequently it suffices to choose dominating upper estimates satisfying \[\begin{align*} A_i&=L+M^{-1/(2a)+o_a(1)}A_{i+1},\tag{127}\\ U_i&=L+kA_i+M^{1/a^2+o_a(1)}U_{i+1}, \tag{128}\end{align*}\] with \(A_d,U_d\le L\). The term \(kA_i\) pays rebuilding every \(h_i=n_i/k\) edits, including its child initialization.

For fixed \(a\), the multiplier in the first recurrence tends to zero, so \(A_i\le2L\) eventually after enlarging \(L\) if necessary. Unrolling the second recurrence through at most \(d\le2a\) levels gives \[U_i\le (d+1)(L+2kL) M^{d/a^2+o_a(1)} =M^{(C+3)/a+o_a(1)}.\] This explicitly shows why no coefficient depending on \(a\) appears in the \(1/a\) exponent. Logarithmic overhead accumulated over the fixed number of levels remains \(M^{o_a(1)}\).

Each attempted cover or helper reconstruction has its own every-path bound, whether it succeeds or is rejected. Charge such a reconstruction to the attempted operation, including if failure or a guard stops it before publication. All previously published states satisfy their verified bounds. The same recurrences therefore hold for these prefixes and unsuccessful computations. ◻

Proof. Use the recursive switching construction underlying permutation networks (Beneš 1964). For \(s=1\), take a single position and its length-zero route. For \(s>1\), take \(s\) new input positions, \(s\) new output positions, and disjoint upper and lower networks on \(s/2\) positions. Connect each input in pair \(2i-1,2i\) to input \(i\) of both copies. Connect output \(j\) of either copy to both positions in output pair \(2j-1,2j\). The size recurrence is \(Q(s)=2Q(s/2)+O(s)\), and all arcs respect the resulting input-to-output order.

Given a permutation, form a bipartite multigraph between its input pairs and output pairs, with one edge per assigned input–output pair. Every vertex has degree two, so the components are even cycles, allowing a cycle of two parallel edges. Color each cycle alternately upper and lower. Every input pair and output pair has one edge of each color. The upper edges specify a permutation through the upper network, and the lower edges one through the lower network. Route inductively and attach the corresponding outer arcs. The two copies are disjoint and each outer position occurs once, giving vertex-disjoint routes. The construction of the network itself uses only the stated recursive lists and port identifiers. ◻

Proof. Put \(b=n-2k\) and choose the least power of two \(s\ge n\). Use the network of Lemma 48 and select \(b\) distinct output positions. Retain all original vertices and edges. Split every network position \(v\) into vertices \(v_{\mathrm{in}},v_{\mathrm{out}}\) joined by an idle edge. An arc \(u\to v\) becomes the edge \(u_{\mathrm{out}}v_{\mathrm{in}}\). Join original vertex \(i\) to the input endpoint of network input \(i\). Finally, add one mandatory sink vertex adjacent to the output endpoint of each selected output. Every constructed vertex is required to be covered by a perfect matching.

In any perfect matching, a network pair either uses its idle edge or has both endpoints matched externally. The numbers of externally matched input and output endpoints are therefore equal. Selected transition edges contribute once to each number and cancel. Original-to-network edges contribute one input endpoint, and edges to mandatory sinks contribute one output endpoint. All \(b\) sinks must be covered, so exactly \(b\) original vertices use network edges. The remaining \(n-b=2k\) original vertices are covered by original edges, which give the decoded matching.

Conversely, let a size-\(k\) matching leave \(b\) original vertices uncovered. Map them bijectively to the selected outputs and extend to a permutation of all \(s\) positions. Route the permutation and keep just those \(b\) paths. On each retained path, select its original-to-input edge, all transition edges, and the edge to its sink. Each active split position is covered once at each endpoint. Use idle edges on all other positions and the original matching on its covered vertices. This is a perfect matching of \(H_k\). For a length-zero route, the two outer edges cover the one split position. For \(b=0\), every network pair is idle.

The number of added positions and edges is \(O(n\log(n+2))\). Store each edge’s type and original identifier. Decoding simply selects the original edges from the returned perfect matching. No list ordering is assumed. ◻

Proof. Replace a vertex of degree \(r\ge1\) by a path on \(2r-1\) vertices, attaching its \(r\) old incidences to successive odd positions. Retain the original edge identifiers at both ends. There are \(r\) odd and \(r-1\) even positions. Every even position must be matched internally to an odd one. Exactly one odd position therefore remains for an external edge. Hence each gadget selects exactly one old incidence, and any perfect matching projects to one in the original graph.

Conversely, the odd attachment of a selected original matching edge leaves two even-length paths on its sides. Match those internally. This also covers \(r=1\), whose gadget is a single vertex. Each odd position has at most two path neighbors and one external edge, and each even position has degree two. The number of gadget vertices is \[\sum_u(2\deg(u)-1)=4e-v.\] A degree scan, incidence-port assignment, and path construction give the time bound and the explicit conversions. Check for isolates first. ◻

Proof. Each test satisfies Equation (130). The guarded-prefix estimates in Theorem 20 and Lemma 22 show eventual adequacy at fixed sufficiently large \(a,\sigma\), independently of matchability and of which verified constructions or sampling failures occurred. Every accepted sampled structure satisfies its checked deterministic invariants, and rejected attempts obey their own unconditional caps. The estimates therefore apply through a purported first deterministic interruption. They do not require a favorable random stream. An exhausted sampling routine terminates the test rather than suspending it.

The fixed-parameter time bound, the logarithmic number of thresholds, and the reductions give the displayed exponent. Logarithmic and fixed-parameter subpolynomial factors absorb the substitution \(S=O(p\log(p+2))\).

All parameters and adequacy checks are computed by finite integer loops: bit lengths, rounded powers of two, products, quotients, and comparisons of scaled dyadics or ratios. Inadequate giant parameters need not pass their checks. The assertion that fixed-parameter logarithmic factors eventually fit size, multiplicity or quality margins requires no encoded table of thresholds. Fixed-parameter bit lengths and arithmetic/dictionary simulation costs are logarithmic powers, or are already charged in the static flow primitive. Individual random-bit costs are included. ◻

Proof. First ignore physical-address overflow, and fix the fallback’s finite digit-array and touched-cell simulation. Its logical clock, bit lengths, and dictionary costs give a fixed polynomial bound \(F(n)\) on its actual work and records. This estimate can use unit-bit data and physical pointer operations; it makes no assumption that the varying parameters of other branches fit a word.

Unless the schedule has already stopped, the fallback receives \(2^j\) steps in round \(j\). It therefore finishes within \(J=O(\log(n+2))\) rounds, with a fixed constant. Total branch allowances through round \(J\) are \[\sum_{j=0}^J\sum_{t=0}^j2^{j-t}<2^{J+2}.\] Starting and switching branches, status checks, and loop control add only polynomial logarithmic overhead; input/setup and output are polynomial as well. Since every allocation is charged, all actually touched physical records before halt are bounded by a fixed polynomial in \(n+2\), even if every arena retains spent cells.

Use independent logical indexing in each branch and actual physical addresses only as pointers, for example with sequential allocation. Interleaving cannot change a simulated algorithm. Choose \(c_0\) once, large enough that this polynomial bound covers physical addresses, quota counters, program control, and input indices in the prescribed \(w\)-bit words. No overflow then occurs on any path. Long logical integers remain digit arrays. Smaller logical words can be masked or simulated; long shifts, divisions and other operations use the corresponding charged loops. Thus the choice of \(c_0\) follows the fixed polynomial bound rather than being a premise about unbounded logical arithmetic. ◻

Proof of Theorem 1. Halting and the computation model follow from Lemma 52; explicit output and success follow from the reductions, threshold search, and Equation (133).

Fix a sufficiently large branch index \(t\). If it needs \(T\) steps, round \(j=t+\lceil\log_2\max(1,T)\rceil\) alone gives it enough quota, unless another answer has already terminated the schedule. The total budget through that round is at most a constant times \(2^t(T+1)\), in addition to input and logarithmic control overhead. Thus the single schedule competes with every fixed branch with a fixed-index factor. For every \(\xi>0\), choose \(t\) large enough in the analysis that the absolute \(O(1/a)\) exponent in Lemma 51 is smaller than a suitable fraction of \(\xi\). For all sufficiently large \(p\), its \(o_a(1)\) term, constant factor and logarithmic overhead fit the remaining slack. Consequently the same program has every-path time at most \(p^{1+\xi}\) for all sufficiently large inputs. No choice of \(t\) based on the input is made by the program.

To exhibit one envelope, let \(T(G,\omega)\) be the actual total instruction count of the schedule on input \(G\) and random path \(\omega\). For \(x\ge2\) define \[e(x)=\sup_{\substack{G,\omega:\,n(G)+m(G)\ge x}} \max\left\{0, \log_{n(G)+m(G)}\bigl(\max\{1,T(G,\omega)\}\bigr)-1\right\}.\] The polynomial fallback bounds this supremum, and the preceding every-path estimates imply \(e(x)\to0\). Put \(\eta(q)=e(\max\{2,q\})\) for integers \(q\ge1\). This function is nonnegative and nonincreasing, and it tends to zero. If \(p\ge2\), the term for \((G,\omega)\) in the supremum defining \(e(p)\) gives \[T(G,\omega)\le p^{1+\eta(p)}.\] The only input with \(p=1\) is the one-vertex empty graph, which is handled directly. Choose a fixed \(C\ge1\) large enough to cover its instruction count. The all-input bound in Theorem 1 follows.

For the sparse specialization, let \(E=\sup_{q\ge1}\eta(q)<\infty\). If \(m\le\kappa n\), then \(n\le p\le(1+\kappa)n\) and monotonicity gives \[T(G,\omega)\le C p^{1+\eta(p)} \le C(1+\kappa)^{1+E}n^{1+\eta(n)}.\] Thus the same algorithm and envelope apply for every fixed \(\kappa\). When \(m=\Theta(n^2)\), one instead has \(p=\Theta(n^2)\), giving the stated \(n^{2+o(1)}\) dense specialization.

Every operation, random bit, intermediate construction and output copy is part of \(T\), so no further uncharged term remains. The input conversion did not assume connectedness, nonisolation, or a particular list order. This proves all assertions of Theorem 1. ◻