Source-linked AI summary
Size-Sensitive Padded Decompositions for Faster Deterministic Negative-Weight Shortest Paths
Khoi Duong
TL;DR
Negative-weight directed-graph SSSP has near-linear algorithms, but the fastest deterministic bound remained slower than the randomized bound. This paper uses size-sensitive padded decompositions in a deterministic algorithm, achieving O((m + n log log n) log^2 n log(nW)) time and improving Li’s deterministic bound by a factor of log n.
Problem
The fastest deterministic negative-weight SSSP bound was slower than the randomized bound, despite near-linear algorithms for the problem.
Source: §1 · p. 1Method
The algorithm recursively decomposes the graph into overlapping subsets and combines child potentials using size-sensitive padded decompositions.
Source: §4.6 · pp. 12–13Results
O((m + n log log n) log^2 n log(nW)) time; the deterministic bound improves Li’s by a factor of log n.
Source: §1 · p. 1Takeaways & Limitations
The result narrows the gap to the randomized bound to a factor of log n / log log n.
Source: §1 · p. 1The decomposition construction’s cutoff is limited by the quadratic cost of rescanning stored balls.
Source: §4.7 · p. 16
Abstract
from arXiv · showhide
We give a deterministic algorithm for single-source shortest paths in directed graphs with integral edge weights at least $-W$ that runs in time $$O((m+n\log\log n)\log^2 n \log(nW)).$$ This improves the previous fastest deterministic bound of Li by a factor of $\log n$.
1 Introduction
The paper gives a deterministic algorithm for negative-weight directed-graph SSSP, improving Li’s deterministic running time by a factor of log n. Its size-sensitive padded decomposition adjusts padding and boundary duplication to the size of each recursive piece.
1.2 Related work
- Earlier near-linear algorithms used randomized LDDs, while deterministic algorithms later achieved near-linear time with progressively improved polylogarithmic overhead.The section also situates the approach among scaling-based shortest-path algorithms and strongly polynomial alternatives.Source: §1 · p. 1, §1.2 · p. 2
1 Introduction
1.1 Techniques
- Smaller recursive pieces receive greater overhead, with size-dependent allowances for both duplicated boundary mass and padding width.The construction peels balls in stages, narrows padding geometrically, then covers the residual with small pieces.Source: §1.1 · pp. 1–2
1.3 Organization
- The paper proceeds from scaling and accounting through ordered merging and size-sensitive decomposition to the final recursion.Section 2 establishes the framework, section 3 combines child potentials, section 4 constructs the decomposition, and section 5 assembles the recursion.Source: §1.3 · p. 2
2 Framework and preliminaries
The framework repeatedly reduces negative edge weights by scaling, using recursive overlapping covers to find potentials. Its accounting tracks progress and work across recursive instances.
2.1 Overview
- Recursive covers produce child graphs whose potentials are combined by BF-Dijkstra; padding limits potentially negative transitions on short comparison walks.Each child either reduces mass by a constant factor or halves the distance scale with a weak-diameter bound.Source: §2.1 · p. 2
2.2 Graphs and potentials
- A valid vertex potential makes every reduced edge weight nonnegative, allowing nonnegative SSSP followed by undoing the potential to recover original distances.Reduced weights are w(u,v) + ϕ(u) − ϕ(v).Source: §2.2 · p. 3
2.3 Scaling and BF-Dijkstra
- Scaling uses O(log(nW)) steps to halve the most-negative reduced-weight bound, then runs nonnegative SSSP; BF-Dijkstra compares against walks with at most η negative edges.Each step seeks a potential reducing the lower bound from −W to −W/2.Source: §2.3 · p. 3
2.4 Mass and accounting
- The framework defines mass for searches and duplication, then bounds recursive work by O(L) times decreases in an accounting potential that telescope.M0 = Θ(m + n log log n) and L = Θ(log n); children reduce potential by lowering mass or halving the distance parameter.Source: §2.4 · p. 3
3 Ordered merge
Ordered merging combines valid child potentials while controlling how often short walks move to later children. Its auxiliary construction and negative-edge bound enable deterministic merging in time proportional to ascent allowance times incidence mass.
3 Ordered merge
- If every walk of length at most d has at most q ascents in the ordered cover, merging takes O(qI) time and returns a valid potential, a negative cycle, or a qualifying walk.An ascent is a transition to a later child in the order.Source: §3 · p. 4
3.1 Shifting the child potentials
- Shifting each child potential by an offset ensures edges to the same or earlier child have nonnegative reduced weight, with all offsets computed in O(I) time.The algorithm processes children in increasing order and updates maxima over each child.Source: §3.1 · p. 4
3.2 Transition graph
- Two shared chains per destination vertex replace quadratic copy-to-copy edges, routing to earlier or later destination copies with at most two connectors per source-copy edge.The graph construction takes O(I) time.Source: §3.2 · pp. 4–5
3.3 Walks with few negative edges
- The endpoint-preserving lemma converts a short comparison walk into one with at most q + 3 negative edges, enabling BF-Dijkstra to recover a valid potential or detect a negative cycle or qualifying walk.The bound preserves the endpoint and does not increase the represented walk’s weight.Source: §3.3 · p. 6
4 Padded decomposition
The padded decomposition deterministically covers each vertex set with linear incidence mass, making progress by reducing child mass or halving the distance parameter when the child has small weak diameter. Its recursive construction and merge order support combining child solutions.
4 Padded decomposition
- Theorem 4.1 constructs a deterministic cover in O(ML) time with O(M) incidence mass, where each child either has mass at most ρM or half the parameter and weak diameter at most d/2.The size-reduction children retain d; diameter-reduction children receive d/2.Source: §4 · p. 6
- Given valid child potentials, reconstruction deterministically combines them in O(LΠX) time.The children are solved recursively before their solutions are combined.Source: §4 · p. 6
4.1 Construction overview
- Peeling removes ball cores around stored centers and keeps their pads as children, while residual division repeatedly seeks a cover by pieces below a fixed mass cutoff.If residual division instead exposes a large small-diameter set, its center either yields diameter reduction or a light direction for peeling; exposed sets are pairwise disjoint, bounding attempts.Source: §4.1 · p. 7
- For successful residual division, reconstruction merges its cover first and then merges the peeled stages in reverse order.The section bounds walk ascents under padded splits and the potential consumed by duplicated vertices to establish the reconstruction bound.Source: §4.1 · p. 7
4.2 Walk ascents
Padded splits and their refinements control how often a walk ascends through an ordered cover. The resulting ascent bound scales with walk length relative to the padding width.
4.2 Walk ascents
- A δ-padded ball consists of a core, pad, and shell, and yields an ordered split whose two exclusive sides are more than δ apart.For an outward ball, the split is (B, S \ B◦); an inward ball reverses directions.Source: §4.2 · p. 7
- A refinement replaces one cover member with an ordered cover of that member, inserting the new members consecutively in its position.A split with width δ′ ≥ δ is also δ-padded, allowing refinements of different widths to use the smallest width.Source: §4.2 · p. 7
- After finitely many δ-padded refinements, every walk P satisfies aY(P) ≤ ⌊ℓ(P)/δ⌋.Walk blocks shorter than δ can be colored without ascents; each cut in a longer walk creates at most one ascent.Source: §4.2 · p. 7
4.3 Accounting for overlaps
Overlapping children increase total potential, so the analysis assigns each parent vertex to one child and measures the duplicated mass. Size and diameter credits quantify the potential decrease available to pay for that overlap.
4.3 Accounting for overlaps
- Overlapping children increase total potential, whereas a partition with retained parameter d would have child masses summing to M.Smaller recursive pieces are allowed more work, while halving a child’s parameter further decreases its potential by its mass.Source: §4.3 · p. 8
- A core partition assigns each vertex of S to exactly one child, and the cover’s duplicated mass measures the excess child mass.This separates the disjoint mass used for credit from mass duplicated by overlapping children.Source: §4.3 · p. 8
- The potential decrease before padding is divided into a size credit for small cores and a diameter credit for halving the parameter.The accounting compares each child’s mass and parameter with those of its assigned core in the parent instance.Source: §4.3 · p. 8
- For a child with core mass b and child mass b′, the potential difference is (b′ − b) log(4d′/W) + (b′ − b) log b′ + b log(b′/b), with all terms nonnegative.Summing the bound over children relates potential loss to duplicated mass; the potential is nonnegative and nondecreasing in mass in the stated parameter range.Source: §4.3 · p. 8
4.4 Local decomposition
The local decomposition creates an ordered, padded cover with linear mass and construction time, using either mass reduction or a compact child with a halved distance parameter. Its padding and overlap are bounded against the potential decrease.
4.4 Local decomposition
- A local cover is constructible in O(M(S)) time with incidence mass O(M(S)); light children retain d and have mass at most ρM(S), while heavy side children have mass at most 7M(S)/8 and the compact central child gets d/2.The central child has weak diameter at most d/2; the heavy-case side bound follows from β = 1/8.Source: §4.4 · pp. 9–10
- The cover is formed by refinements using width δ0 = Θ(d/(L log L)), and each refinement is a δ0-padded split.In the heavy case, two padded balls around a common center yield a central child compact around that center and side children.Source: §4.4 · p. 9
- The local construction searches outward and inward for either light cores with small shells or heavy balls, collecting light cores until their union reaches a quarter of S.If both searches become heavy, shells around the selected center produce the two padded balls used for the three-child decomposition.Source: §4.4 · pp. 9–10
- The light cover has incidence mass at most (1+θ)M(S), while the heavy cover has incidence mass at most 3M(S).In the heavy case, the central child is compact and the side children retain d.Source: §4.4 · p. 10
- The local decomposition satisfies ΠS ≥ M(S)/16 and DS ≤ 2θΠS/L.The shell-mass choice ensures padding consumes at most half of the potential decrease.Source: §4.4 · pp. 9, 11
4.5 Residual cover
Residual division repeatedly refines oversized sets to produce either a large compact set with a center or a bounded-mass ordered cover. Its accounting controls duplication and keeps the cover’s construction work near-linear up to the refinement-depth factor.
4.5 Residual cover
- Residual(R) takes O(M(R)τ) time and returns either a compact set of mass greater than Z with a center or an ordered cover of R.Cover members have mass at most Z, total incidence mass O(M(R)), and child parameters d or d/2.Source: §4.5 · p. 11
- The cover is built by repeatedly dividing members above cutoff Z; a central child still above Z instead supplies the compact-set outcome.Central children at or below Z receive parameter d/2 and have weak diameter at most d/2 in H.Source: §4.5 · p. 11
- Repeated divisions preserve an ascent bound of O(Lτ) for walks of length at most d, while a returned center’s set is compact with weak diameter below d/2.The refinement argument bounds depth by O(τ) and derives the ascent bound using δ0-padded splits.Source: §4.5 · pp. 11–12
- Charging duplicated mass to actual potential decrease is necessary because a linear incidence bound for each division alone does not bound the final cover.For the completed refinement, duplicated mass is O(M(R)), so final incidence mass is O(M(R)) and total work is O(M(R)τ).Source: §4.5 · p. 12
4.6 Peeling
Peeling removes cores around stored centers while retaining padded children, leaving a residual set for later decomposition. The staged shell searches ensure light children, disjoint cores, and a controlled duplication bound, enabling deterministic reconstruction.
4.6 Peeling
- At each decreasing test radius, Peel scans stored centers and grows qualifying balls until it finds a small shell, saves the pad, and removes the core from the active set.Balls use distances in H and contain only vertices still active.Source: §4.6 · p. 12
- Peel constructs at most |S| peeled children with nonempty cores, each of mass below βM, and their cores together with the residual partition X.The peeled children’s total duplicated mass is bounded by the core size credits.Source: §4.6 · p. 13
- A compact set of mass greater than Z in the residual is disjoint from every set compact around a stored center.This property supports bounding the number of new centers exposed during alternating peeling and residual division.Source: §4.6 · p. 13
- Each stored center produces at most one accepted ball, and accepted cores are disjoint, so their total duplication is controlled by the shell bound.The resulting total duplicated mass is bounded by the sum of core size credits.Source: §4.6 · pp. 13–14
- Peeling reconstruction processes stages in reverse, merging the solved later active set with the potentials on that stage’s peeled children.The ordered cover places outward pads first, then the solved child, then inward pads in reverse chronological order.Source: §4.6 · p. 14
- The stage merges retain valid potentials or return a negative c-cycle or a walk with c(P) < 0 and ℓ(P) > d.The total reconstruction work is O(L(κpeel + τM(R))).Source: §4.6 · pp. 14–15
4.7 Construction
The construction alternates peeling and residual division, restarting from the full parent set when a residual center yields a light direction. It returns a cover with bounded incidence and child sizes, and terminates within a controlled number of attempts.
4.7 Construction
- The algorithm alternates peeling and residual division; a light direction from a returned center triggers a restart from X with that center stored.Fixed deterministic tie-breaking is used for all choices.Source: §4.7 · p. 15
- When both radius-7∆ balls around the center are heavy, shell searches yield a three-child decomposition with side masses at most (1 − β)M and a central child of weak diameter at most d/2.The central child receives parameter d/2; the side children retain d, and the construction takes O(M) time.Source: §4.7 · p. 15
- The returned peeled children and residual cover have total incidence mass O(M), each child has mass at most M/8, and children assigned d/2 have weak diameter at most d/2.The residual cutoff is Z = M/2τ, while peeled pads have mass less than M/8.Source: §4.7 · p. 15
- Algorithm 2 terminates after at most 2τ attempts, including unsuccessful attempts.Each newly stored center is exposed by a pairwise-disjoint compact set of mass greater than Z.Source: §4.7 · pp. 15–16
- The construction work bound includes the quadratic cost of rescanning stored balls, which is what limits the cutoff.When L is bounded by a constant, the construction applies Lemma 4.9 directly to X.Source: §4.7 · p. 16
- Padding and core size credits provide enough potential decrease to pay for construction work, with the direct three-child case also giving potential decrease Ω(M).If τ < 4, applying Lemma 4.9 directly takes O(M) time and gives actual potential decrease Ω(M).Source: §4.7 · pp. 16–17
4.8 Reconstruction
Reconstruction first merges the residual cover, then combines its potential with the peeled-child potentials through reverse-stage peeling reconstruction. The resulting work is bounded by the size credits of peeled cores and the residual mass.
4.8 Reconstruction
- The reconstruction first merges the residual cover to obtain a potential on G[R], then combines it with the peeled-child potentials.The second step uses the reconstruction procedure for peeled children and the residual.Source: §4.8 · p. 17
- The residual merge costs O(LτM(R)), and combining peeled children costs O(L(κpeel + τM(R))).Small residual children pay for the τM(R) term.Source: §4.8 · p. 17
- A direct three-child decomposition merges in O(ML) time, while the τ < 4 case merges in O(M) time.In both cases the merge fits within O(LΠX).Source: §4.8 · p. 17
- All merges use parameter d on induced subsets of X, yielding a valid potential on G[X] unless a merge returns a negative cycle or a qualifying negative walk.Such a cycle or walk lies in G[X].Source: §4.8 · p. 17
5 Shortest paths
The section gives a deterministic algorithm for a single scaling step and assembles it into a recursive shortest-path algorithm. Its scaling reduction yields the stated deterministic running time.
5 Shortest paths
- A scaling step either finds a negative-weight cycle or computes a valid potential for shifted weights c = w + W/2 in O(M0L2) time.Source: §5 · p. 17
5.1 Algorithm
- Solve recursively decomposes vertex sets, solves the children, and merges their potentials; its base case scans shifted weights or solves small instances directly.A failed merge or a negative shifted edge can produce a negative w-cycle.Source: §5.1 · p. 18
5.2 Correctness
- The recursion preserves its diameter invariant, and induction shows that successful merges return valid parent potentials while failures yield negative w-cycles.Cycle certificates are converted using a return path when needed; at the root, a valid c-potential supplies the scaling step.Source: §5.2 · p. 18
5.3 Running time
- The running-time proof telescopes potential decreases across the recursion tree; decomposition and merging costs are charged to these decreases, with the return search adding O(M0).The accounting also covers child-graph construction, membership data, and terminal scans.Source: §5.3 · p. 19
- O(log(nW)) scaling steps and one final nonnegative SSSP computation yield the stated bound after substituting M0 = Θ(m + n log log n) and L = Θ(log n).All procedures use deterministic choices.Source: §5.3 · p. 19