Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense Graphs

1 Introduction

• The paper addresses whether exact minimum-cost flow can beat the classical ~O(mn) bound while staying in the residual-graph paradigm.Faster algorithms reached almost-linear time through interior-point methods, while the fastest residual-graph-based exact algorithm remained Goldberg and Tarjan’s.Source: §1 · p. 3
• A combinatorial algorithm computes a minimum-cost flow in n^(2+o(1)) time; it is almost optimal in dense graphs and is randomized and correct with high probability.Source: §1 · p. 3
• The flow-cost-preserving DAG projection replaces a general directed graph with a DAG while approximately preserving both flow congestion and cost.It generalizes DAG projections that preserved only congestion or only costs.Source: §1 · p. 4
• A simple augmenting-path-based algorithm computes approximate primal-dual minimum-cost flow on DAGs in n^(2+o(1)) time.It generalizes a weighted push-relabel algorithm for maximum flow [BBST24].Source: §1 · p. 4
• A black-box reduction turns exact minimum-cost flow on general graphs into n^o(1) calls for weak approximate primal-dual flow.Theorem 1.2 bounds cumulative oracle input size and vertex count by m^(1+o(1)) and n^(1+o(1)), respectively.Source: §1 · pp. 3–4
• The reduction isolates the difficulty of exact general-graph flow in weak approximation on DAGs, a setting the authors describe as substantially simpler.They suggest future combinatorial work can focus on DAG approximation; deterministic or parallel extensions are plausible but not pursued here.Source: §1 · p. 4

2 Overview

• The overview identifies three ingredients: exact-to-approximate reduction, general-graph-to-DAG reduction, and an augmenting-path algorithm for approximate PD-MCF on DAGs.Source: §2 · pp. 4–5

2.1 Exact-to-Approximation Reduction

• Exact minimum-cost flow can be solved with n^{o(1)} calls to a (κ, 1 + ϵ)-approximate primal-dual oracle when κ = n^{o(1)} and ϵ = 1/n^{o(1)}.The reduction is black-box, unlike successive approximation, and shows that several natural approximate MCF formulations are equivalent for computing an exact solution. Repeated rounds reduce residual optimum cost; for general κ, each call routes at least a 1/κ fraction of remaining demand.Source: §2.1 · pp. 5–7

2.2 Flow-Cost-Preserving DAG Projection

• A flow-cost-preserving DAG projection transfers routable demands and their costs between a general graph and a DAG, with congestion slack κ and length slack λ.The definition requires that DAG-routable demands project back with congestion κ and unchanged cost, while graph-routable demands lift to the DAG at cost at most λ times the original; approximately preserving relevant flows and costs makes a DAG oracle useful for the general-graph problem.Source: §2.2 · p. 8

2.2.1 Existence

• An MWU-inspired path-cover construction controls width to n^{o(1)}, with dcov = n^{o(1)}·ddiam, supporting the DAG projection.The construction uses a length-constrained expander hierarchy and a bounded-width path cover; the hierarchy has length slack n^{o(1)} and expansion parameter 1/n^{o(1)}.Source: §2.2.1 · pp. 8–9
• At each cost scale, the projection recurses on light SCCs, replaces heavy SCCs with star gadgets, and adds bridges between heavy-component hubs.Forward and backward mappings preserve feasibility and incur only a (1 + O(ϵ)) cost loss; bounded-width path covers and cumulative SCC covering along paths address a challenge absent from the undirected shortcut construction.Source: §2.2.1 · pp. 10–11

2.2.2 Fast construction

• The fast construction resolves its apparent MCF-oracle circularity by reducing between h-length projection, hierarchy, and approximate MCF problems, then shrinking the scale from h to h/z.Repeated concatenation alone would cause polynomial DAG-size blow-up, whereas the four-step recursion puts the z-dependence in running time rather than final projection size.Source: §2.2.2 · pp. 11–12
• The directed LC-expander hierarchy algorithm supplies two previously missing ingredients: fat low-diameter decomposition and a directed cut-matching game with length constraints.The decomposition is obtained by reduction to its undirected variant; the full cut-matching construction is deferred to Section 6.Source: §2.2.2 · p. 12

2.3 Weighted Push-Relabel Algorithm for MCF on DAGs

• The DAG augmenting-path algorithm returns a (3, 1 + ϵ)-approximate PD-MCF solution and uses weighted admissibility to limit how often edges are saturated.It extends weighted push-relabel for maximum flow on DAGs; the paper notes the algorithm in fact returns a strongly approximate solution. The min-cost setting also requires handling non-monotone admissible paths and certifying solution quality using DAG structure.Source: §2.3 · pp. 12–13

3 Preliminaries

• A flow is represented by path amounts or edge amounts, and its cost sums edge flow times edge length while its congestion divides edge flow by capacity.The notation uses n and m for the original graph’s vertex and edge counts, respectively.Source: §3 · pp. 13–14

3.1 Minimum cost flow.

• A minimum-cost flow routes a demand at minimum cost, with flow cost computed from edge flow and lengths and feasibility requiring congestion at most one.The paper assumes positive capacities and integer lengths and capacities bounded in magnitude by a polynomial in n.Source: §3 · pp. 13–14, §3.1 · p. 15
• A (κ, λ)-approximate PD-MCF has congestion at most κ and flow cost at most λ times the dual value; the paper targets this oracle on DAGs.The dual views ϕ as a distance function and ℓ̃ as a length increase used to enlarge source-to-sink distance.Source: §3.1 · p. 15

3.2 Projection map.

• A path cover maps a graph G′ to G while preserving edge lengths, covering every path of length at most hcov, and bounding each G′ component’s diameter by hdiam.The projection map π also supports inducedness and width definitions; gives bounded size but unbounded width, while this paper extends the idea to bounded width.Source: §3.2 · p. 16

4 Boosting Approximate Minimum Cost Flow

• For ϵ = o(1/log^9 n), Theorem 2.1 reduces exact minimum-cost flow to calls to a (κ, 1 + ϵ)-approximate PD-MCF oracle.The theorem’s call-efficiency expression is split across the supplied passages, so its precise bound is not stated here.Source: §4 · p. 17

4.1 Exact Flow with Approximate Cost

• A feasible primal-dual pair with value gap ∆ bounds the residual problem’s optimal cost by ∆, and combining an optimal residual flow with the pair’s flow gives an exact optimum.The residual instance is formed from the flow and potentials; its negative-length residual edges are reversed to obtain non-negative lengths.Source: §4.1 · pp. 17–18
• An oracle routing at least |D|/κ of the demand with a (1 ± ϵ) primal-dual pair yields an exact flow using at most eO(κ)-efficient calls.The guarantee applies for κ ≥ 1 and 0 ≤ ϵ ≤ 0.1.Source: §4.1 · pp. 18, 20

4.2 Flow Boosting

• The MBCF LP admits a (1 + ϵ)-approximate primal-dual pair using eO-efficient calls to a (κ, o(ϵ))-approximate PD-MCF oracle.The construction uses flow boosting via multiplicative weight updates; the MBCF LP is a weaker formalization than the MCF LP.Source: §4.2 · pp. 20–21

4.3 Converting MCF solution: From MBCF to MCF

• An MBCF solver with approximation ratio 1 + ϵ, for ϵ < 1 / log^9 n, yields an exact minimum-cost-flow algorithm when a feasible routing exists.Lemma 4.8 bounds the number of solver calls by 2 O(log1/ϵ1/3 n).Source: §4.3 · p. 22
• The oracle runs the MBCF solver on a geometric sequence of budgets, selecting a budget whose flow exceeds half the demand while controlling its cost.Its constructed primal flow has value q_a+1 > |D|/2 and cost at most B_a+1.Source: §4.3 · pp. 23–24
• A shortest-path potential in the graph with modified lengths supplies a feasible MCF dual, with the resulting primal-dual gap bounded by a factor of 1.1.The proof derives a multiplicative factor 1 + O(ϵ1/3), which is at most 1.1 for sufficiently large n under the stated ϵ bound.Source: §4.3 · p. 24
• General demand vectors are handled by adding a super-source and super-sink with zero-length edges, then restricting the resulting primal and dual objects to the original graph.Source: §4.3 · p. 24

5 Flow-Cost-Preserving DAG Projections

• A flow-cost-preserving DAG projection extends the DAG-projection definition from to preserve both distance and congestion.The paper describes preserving flow costs and congestion up to small losses.Source: §5 · p. 25
• The projection preserves flow costs while allowing congestion slack κ and length slack λ between a graph and its DAG representation.Flows from the DAG can be mapped back with congestion at most κ and the same cost; flows on the original graph can be represented on the DAG with congestion 1 and cost at most λ times as much.Source: §5 · p. 25
• Applying a DAG projection and the transfer lemma reduces exact minimum-cost flow on general graphs to approximate computation on DAGs.The theorem states the exact-flow algorithm's complexity in terms of efficient calls to an approximate PD-MCF oracle on DAGs.Source: §5 · p. 26
• The corollary bounds the cumulative size of DAG-oracle instances by m^{1+o(1)} and their cumulative vertex count by n^{1+o(1)}.The stated exact-flow algorithm makes calls to the DAG oracle with these near-linear cumulative bounds.Source: §5 · p. 26

5.1 Reducing PD-MCF on General Graphs to DAGs

• Projection algorithms transfer primal flows from the DAG to the original graph and dual certificates in the reverse direction.The primal transfer preserves cost exactly while allowing congestion κ; the dual transfer yields a feasible certificate for the original instance.Source: §5.1 · p. 27

6 Length Constrained Expander Hierarchy Construction

• The construction outputs a ≤h-length (ϕ,s)-expanding t-layer weak LC-expander hierarchy with efficient routing algorithms, where s=(log n)^O(1/ϵ).Source: §6 · p. 31

6.1 FatLDD for Round-Trip Distance

• FatLDD computes a randomized neighborhood cover for directed round-trip distance with separation witnesses in Õ(m) time when hdiam/hcov and width are n^o(1).Source: §6.1 · p. 32

6.2 LC-Expander Decomposition

• The LC-ED algorithm outputs a moving cut and sub-weighting A′ that is (h,s)-length cut-constraint ϕ-expanding, with s=(log n)^O(1/ϵ) and Δ=κκ′n^O(ϵ).Source: §6.2 · pp. 33–34

The algorithm.

• The algorithm accumulates edge-length increases; paths of length at most hSσ between vertices in a cluster remain inside its separation witness after cuts supported there.Source: The algorithm · pp. 34–35

The algorithm

• The algorithm certifies that A′ is (h, s)-length C-constraint ϕ-expanding by routing demands through expanders and lifting those routes to the original graph.Within each cluster, the expander routing has O(1) congestion and uses O(log n) expander edges; the resulting routing has congestion at most 1/ϕ and length bound hs.Source: The algorithm · p. 37

6.3 LC-Expander Hierarchy

• The construction outputs a ≤h-length (ϕ, s)-expanding t-layer weak LC-expander hierarchy with efficient associated routing algorithms, for s = (log n)^{O(1/ϵ)}.The stated result assumes the parameter conditions of Lemma 6.9.Source: §6.3 · p. 41
• At each hierarchy step, the algorithm combines expansion guarantees over all dyadic scales to make A′ᵢ constraint ϕ-expanding simultaneously for every length bound up to h.It applies Lemma 6.17 at each scale and unifies the resulting guarantees; the O(log n) scales are absorbed into n^{O(ϵ)}.Source: §6.3 · p. 42
• The hierarchy step takes a maximal subcut of C′ᵢ to realize most of A′ᵢ, certifies expansion for degCᵢ, and defines the next residual cut.The remaining cut is bounded using charges to saturated endpoints.Source: §6.3 · pp. 42–43
• The last layer is ϕ-expanding because its root-routing construction has congestion at most 1, and 1 ≤ 1/ϕ.The construction routes total demand at most 1 over edges with capacity at least 1.Source: §6.3 · p. 44
• For each earlier layer, the covering property transfers expansion to the future cut because that cut imposes at least as much length increase.This lets the same routing algorithm certify expansion under the future cut constraint.Source: §6.3 · p. 44
• C1, …, Ct form a ≤h-length (ϕ, s)-expanding t-layer weak LC-ED hierarchy.The final layer is ϕ-expanding, completing the hierarchy’s expansion guarantee.Source: §6.3 · p. 44
• All layer routing algorithms are efficient, using inherited routing for earlier layers and explicit root routing for the last layer.The earlier-layer algorithms are inherited from the node-weighting A′i and domination.Source: §6.3 · p. 44
• Each iteration performs O(log n) calls to Lemma 6.17, and logarithmic factors are absorbed by n^O(ϵ) in the overall complexity.The supplied passage does not state the remaining complexity expression.Source: §6.3 · p. 45

7 DAG Projection Construction via LC Expander Hierarchy

• Lemma 7.1 gives an algorithm for constructing an h-length flow-cost-preserving DAG projection using oracle calls.The supplied passages do not include the lemma’s full size bound.Source: §7 · p. 45

7.1 An Algorithm for Constructing the DAG Projection

• The recursive construction builds path covers at dyadic scales, replaces SCCs with recursively constructed DAGs, and adds bridge edges between heavy SCCs.The resulting graph is a DAG because the SCC condensation and each recursively constructed component are DAGs.Source: §7.1 · p. 47

7.2 Size and Complexity of the Construction

• The construction’s non-oracle running time and cumulative oracle graph size are at most m^{1+O(δ)} · (1/ε)^{O(1/δ^5)}.The section also states a separate bound on the returned DAG’s size, but its formula is absent from the supplied passage.Source: §7.2 · pp. 49–50

7.3 Projection Algorithm for Flows

• A recursive flow-projection algorithm maps feasible flows on the constructed DAG to flows on the original graph, routing deferred demands globally layer by layer.The deferred demands are routed using the original graph’s weak LC-expander hierarchy.Source: §7.3 · pp. 50–51
• The recursive flow mapping produces a local flow and deferred demands, with local-flow congestion bounded by Γ(|S|, i).Across scales, the deferred demands cancel, and the resulting local flow preserves the demand and cost identities.Source: §7.3 · pp. 52, 56, 57
• Bridge flow is converted into auxiliary flows with matching value, average cost at most Lr, and congestion at most 2κfκp/ϵ.The construction also bounds the deferred demands as degCi-respecting and symmetric ˆh-length in G − C>i.Source: §7.3 · pp. 53–54
• Expander routing handles the scaled aggregate deferred demands with congestion at most 1/ϕ, after which the deferred demands cancel exactly.The demands are routed under the stated length-constraint expansion condition.Source: §7.3 · p. 56

7.4 Projection Algorithm for Moving Cuts

• The moving-cut projection returns a cut of the same size and length, while preserving distances within h up to a factor of 1 + ϵ*.The construction builds a length increase from recursive-edge, interface-edge, and bridge-bundle contributions.Source: §7.4 · pp. 57–58
• The moving-cut projection preserves size: translated interface edges preserve it exactly, and each translated bridge bundle adds no more size than its corresponding bridge edge already paid.The correctness argument sums recursive, interface, and bridge-bundle contributions.Source: §7.4 · pp. 59–60
• The moving-cut projection also satisfies the lemma’s length guarantee by recursively lifting path pieces and charging interface and bridge losses within the allowed approximation.The proof absorbs additive losses of O((ϵ + ϵp + ϵf)d) and a multiplicative 1 + O(ϵ + ϵp + ϵf) bridge loss into η(S, i).Source: §7.4 · p. 64
• The moving-cut projection algorithm runs in ˜O(|E(D∗S,i)|) time, processing each recursive edge, interface edge, and bridge bundle once up to polylogarithmic overhead.Source: §7.4 · p. 64

7.5 Combine Everything

• For any q, a h-length projection yields a qh-length DAG projection of size O(q|G′|), with an efficient (4κ, λ)-projection algorithm and O(q)-scaled running time.The construction uses 2q copies of the original projection.Source: §7.5 · p. 65
• The construction yields a qh-length flow-cost-preserving DAG projection with congestion parameter 4κ and length slack λ.The dual guarantee establishes that the resulting graph is a qh-length (4κ, λ)-projection.Source: §7.5 · p. 67
• Lemma 7.1 sets κ=κfκp·S(n,δ,ϵ) and λ=1+O((ϵ+ϵp+ϵf)/δ²); projection runtime is zm·S(n,δ,ϵ).The construction also makes z·S(n,δ,ϵ)-efficient oracle calls.Source: §7.5 · p. 68
• Theorem 5.3 gives an OPDMCF-oracle construction with n^δ·(1/ϵf)^poly(1/δ)-efficient calls and λ=1+ϵf·(1/δ)^O(1/δ).Source: §7.5 · p. 68
• Lemma 7.1 enlarges the length bound by q while increasing congestion slack by κf·n^O(δ)·(1/ϵ)^O(1/δ^5), with fixed complexity qm·S(n,δ,ϵ).Choosing ϵ=ϵf<ϵp makes the length slack minus 1 grow by O(1/δ²); the fixed size is m·S(n,δ,ϵ).Source: §7.5 · p. 68

8 Minimum Cost Flow Algorithm on DAGs

• On a DAG with an s–t flow f*, Theorem 8.1 returns a (1 ± 6ϵ) primal–dual minimum-cost flow pair with value at least val(f*)/3.Source: §8 · p. 69
• Theorem 1.1 gives a combinatorial algorithm for exact minimum-cost flow on general graphs in n^{2+o(1)} time.The proof applies Corollary 5.6, repeating the DAG procedure on remaining demands to obtain an oracle with O(log n) congestion and total cost (1 + O(ϵ))·OPT.Source: §8 · p. 69

8.1 Algorithm

• The algorithm guesses the flow-value and cost scales, then alternates relabeling active vertices with augmenting along admissible s–t paths or directed cycles.Lazy checkpoint checks limit edge-status recomputations; the primal flow is paired with a dual constructed using a penalty on backward residual edges.Source: §8.1 · pp. 69–70

8.2 Correctness

• The correctness analysis proves that termination yields a flow of value at least 0.9q, while the output is an approximate primal–dual pair.Theorem 8.1 states the pair’s (1 ± 6ϵ) guarantee and value of at least val(f*)/3.Source: §8 · p. 69, §8.2 · p. 73
• Positive-flow edges have reduced length at most 6εαw(e), and each unit of s–t flow decomposes into a topological path whose total w-weight is at most n.Together these bounds yield the stated aggregate guarantee.Source: §8.2 · p. 75

8.3 Complexity (Implementation Details)

• The implementation follows Appendix A of, using a maintained admissible-edge pseudoforest and canceling a directed cycle whenever a chosen edge would create one.Cycle cancellation augments by the bottleneck residual capacity and removes saturated tree edges.Source: §8.3 · pp. 75, 77
• Each augmentation saturates at least one residual edge; for an edge direction to saturate again, its reduced length must drop by at least 2εαd.The analysis charges this decrease to the tail vertex’s potential, which never increases and changes in steps of εα.Source: §8.3 · p. 76
• Link–cut trees support the maintained forest operations in amortized O(log n) time, including links, cuts, and path updates.The implementation also augments along the tree path from s to t when the component containing s is cycle-free.Source: §8.3 · pp. 76–77

A.1 Union of Sparse Moving Cuts

• Lemma A.2 considers a subsequence Ca1,...,Caz of moving cuts C1,...,Ck in graph G with positive integral edge lengths and capacities, under h > 1, ϕ ∈ (0,1), 1 ≤ α ≤ log n, and s > 4 log² n.Each selected cut is (h, s)-length ϕ-sparse with respect to A.Source: §A.1 · p. 78
• The proof adapts the potential argument from Lemma 3.17 of by summing potential drops only over the selected cuts.The potential is monotone when edge lengths increase, so the intervening graph changes do not add negative terms.Source: §A.1 · pp. 78–79
• Grouping cuts into dyadic buckets yields an aggregate cut-size bound of O(2^(8α+2)ϕ ln n) · |A| for each bucket.Only O(log H) buckets are nonempty; the bucketed cuts induce the same edge-length increases as the original cuts.Source: §A.1 · pp. 80–81

A.2 FatLDD on Directed Graphs

• The directed LDD partitions vertices into sets of directed diameter at most d, while each edge’s reversal probability is at most O(log^2 n) · w(e)/d.The decomposition is randomized and makes eO(1) calls to an exact SSSP oracle.Source: §A.2 · p. 81
• The construction converts directed round-trip distances into an undirected graph G′ with distortion O(log^2 n), with high probability.Lemma A.4 uses directed SSSP-oracle calls to construct G′.Source: §A.2 · p. 81
• The neighborhood-cover algorithm runs in Ô(m) time when both hdiam/hcov and the cover width ω are n^o(1).The construction uses the undirected neighborhood-cover lemma as an intermediate step.Source: §A.2 · p. 82

Algorithm.

• Starting from G, the construction obtains undirected G′, adds hopset H with n^(1+o(1)) edges, guaranteeing for every pair a path in G′ ∪ H using at most h = n^o(1) edges and length at most 1.1 · distG′(u, v).Source: Algorithm · pp. 82–83
• The output is a neighborhood cover for the directed round-trip metric with the claimed parameters and separation witnesses.The proof checks covering radius, diameter, separation, and witness validity.Source: Algorithm · pp. 83–85
• The resulting construction runs in Ô(m) time, including preprocessing and hopset construction.The runtime argument uses n^o(1) parameters for the diameter ratio and cover width.Source: Algorithm · p. 86

Lemma A.6

• Lemma A.6 turns an s-t demand into a flow of congestion at most κκ′ and average cost a, together with an (a/λ)-length moving cut of size at most the flow value.The cut also has the stated distance lower bound.Source: §A.3 · pp. 86–87

Corollary A.7

• A.7 projects an oracle flow to G with congestion at most κκ′ and preserves its average cost, while producing a moving cut of length min{h, a/(λλ′)} and size at most the flow value.The cut also satisfies the stated distance lower bound; the flow and cut are obtained using one oracle call and one projection-algorithm call.Source: §A.3 · p. 87

Lemma A.8

• Lemma A.8 returns either an hs-length flow routing demand of value at least ϕ|D|/6 or an (h, s/(4λλ′))-length ϕ-sparse cut of size at least ϕ|D|/3.The flow case retains at least half the value of the initially routed flow; the cut case separates at least 5|D|/6 demand on light vertices.Source: §A.3 · pp. 88–90

Lemma 6.16

• Lemma 6.16 repeatedly applies Lemma A.8 to residual demand, stopping with a cut or combining the returned flows into an implicit flow-path decomposition.The decomposition is hs-length bounded, and each iteration contributes congestion at most κκ′.Source: §A.3 · pp. 90–91

B Path Cover with Bounded Width

• The deterministic algorithm constructs a qd-path cover of G in q · m^(1+o(ϵ)) time.The guarantee applies for ϵ in (log log n/log n, 1) and stretch parameter q in the positive integers.Source: B Path Cover with Bounded Width · p. 92

B.1 The Algorithm

• Each recursive call carries positive vertex weights, chooses a root, and runs forward and backward Dijkstra searches to locate stopping layers.The searches are interleaved by settled weighted mass and stop when either finds a thin layer.Source: §B.1 · pp. 92–93
• The recursive cases form pieces from the searched regions and rings, recurse on those pieces with adjusted weights, and return a layered projection.The construction describes both a two-piece projection from the outer regions and a projection using outer regions with a middle subgraph.Source: §B.1 · pp. 93–94

B.2 The Global Potential

• The potential is defined over loaded instances created but not yet expanded, which are the leaves of the current recursion tree.At the end, the leaves of the final recursion tree still have potential at most n².Source: §B.2 · pp. 94, 96
• Every recursive expansion does not increase the active-frontier potential, which is initially n².The proof handles cases where the ring is tiny relative to a side and where both complements are small.Source: §B.2 · pp. 94–96
• For every active recursive instance (A, µ), its squared mass is bounded by n² because it contributes a term to the potential..Source: §B.2 · p. 96

B.3 Correctness: Path Covering

• The proof retains the layered-projection construction while changing the thin-layer definition to use µ mass and adjusting parameters.The path-covering argument is otherwise identified as the same as the original proof in.Source: §B.3 · p. 96
• Each strongly connected component of the returned graph has diameter O(ρ^3 log n) · d.The number of forward and backward layers is at most O(ρ^3 log n).Source: §B.3 · p. 97
• Every loaded instance returns a d-path cover, and every path in its graph of length at most d has a lift in the returned cover.The path-covering proof follows the original proof in.Source: §B.3 · p. 97

• Each original vertex has at most n^{O(ε)} final copies, so the width of H is at most n^{O(ε)}.Each reweight multiplies a copy's weight by ρ; the active-copy mass bound limits reweighting, and ρ = exp(1/ε).Source: §B.4 · p. 97
• The final graph H has size |H| = m^{1+O(ε)}.The path cover is induced, and the per-vertex copy bound limits copies of each edge.Source: §B.4 · p. 98
• The algorithm takes time m^{1+O(ε)}, charging Dijkstra and graph modification to the sum of projected-vertex degrees.The proof uses Lemma B.11 to bound this sum.Source: §B.4 · p. 98

• G(q) covers every path in G of length at most qd by splitting it into at most q subpaths and joining their lifts across consecutive layers.The construction adds connector edges where consecutive subpaths meet.Source: §B.5 · pp. 98–99
• Every strongly connected component of G(q) lies within one copy of H, so its diameter remains at most λd; the stated bound is O(d · ρ^3 log n).All inter-layer edges go strictly forward, preventing a strongly connected component from spanning layers.Source: §B.5 · pp. 98–99
• The width bound scales by q because each original vertex has at most width(H) copies per layer.The construction uses q layers.Source: §B.5 · pp. 98–99
• Each layer contributes |E(H)| internal edges, and connector edges are bounded by projected outgoing degrees across each consecutive layer pair.There are q −1 consecutive layer pairs.Source: §B.5 · pp. 98–99