PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond Distance Ordering: Resource Complexity and Universal Optimality of Exact Labeled Directed Shortest Paths

Bin Cai

arXiv:2609.04825v1cs.DScs.CC

TL;DR

The paper asks how much numerical work exact labeled-distance output intrinsically requires, and whether one uniform algorithm can match topology-specialized programs. It characterizes arithmetic and cyclic comparison tradeoffs, then uses transcript cones to construct a charged-operation-optimal interpreter and active-core reduction for efficient navigation. The result is exact numerical universal optimality, while efficient constant-competitive navigation remains open.

  • Problem

    The paper studies exact single-source shortest paths when the output is only the materialized labeled distance vector rather than a distance order.

  • Method

    The paper combines exact comparison–addition resource characterizations, cyclic shared-hub tradeoffs, a same-program OPTDIST benchmark, transcript-cone minimax policies, and active-core reduction.

  • Results

    A uniform interpreter matches OPTDIST exactly in charged additions and comparisons on every topology, while efficient lifting achieves a sublogarithmic-factor bound.

  • Takeaways & Limitations

    Optimal numerical policies exist uniformly, but efficient constant-competitive navigation remains open.

  • Takeaways & Limitations

    The entropy-tight Pareto law is proved for the shared-hub family, exact comparison complexity on general cyclic topologies remains open, and optimal action search may take exponential time.

Abstract

from arXiv · show

We study exact single-source shortest paths when the output is only the materialized labeled distance vector ($\mathrm{DIST}$), rather than a distance order. In the full deterministic comparison-addition model, the minimum worst-case number of additions on every fixed directed topology is exactly the maximum number $ρ_{\mathrm{fwd}}$ of forward nonsource endpoint classes over rooted vertex orders; the lower bound permits adaptive control, literals, and arbitrary mixed sums. This arithmetic law aligns with the comparison optimum on DAGs, where the full resource region is an exact rectangle. Cycles destroy that alignment: a two-spoke shared-hub graph has coordinatewise optima $(4,2)$ but requires five comparisons at the two-addition budget. Its $k$-spoke extension forces $k\log_2 k+O(k)$ comparisons at the addition optimum and has an entropy-tight deterministic tradeoff $C_{k+r}^*(H_k)=Θ(k+Λ_{k,r})$, where $Λ_{k,r}=\log_2(k!/[r!(r+1)^{k-r}])$, with leading constant one when $Λ_{k,r}/k\to\infty$. Because the two coordinatewise minima need not belong to one program, these conflicts lead to the same-program benchmark $\operatorname{OPT}_{\mathrm{DIST}}=\inf_A\sup_w(C_A(w)+P_A(w))$. An exact transcript-cone game yields one uniform interpreter whose charged addition-comparison cost equals $\operatorname{OPT}_{\mathrm{DIST}}$ on every topology; its optimal actions are synthesizable in polynomial space but may require exponential time. Finally, an active-core reduction and the current deterministic directed-SSSP bound give an efficient uniform $O\!\bigl(\operatorname{OPT}_{\mathrm{DIST}}\sqrt{\log(2+\operatorname{OPT}_{\mathrm{DIST}})\log\log(4+\operatorname{OPT}_{\mathrm{DIST}})}\bigr)$ charged-operation bound. Thus optimal numerical policies exist uniformly, while efficient constant-competitive navigation remains open.

1 Introduction

The paper separates exact labeled-distance materialization from distance ordering, characterizes its arithmetic and comparison resources, and studies when one uniform program can achieve topology-specific optima. DAGs align the resources, while cycles create tradeoffs that motivate a same-program benchmark and an efficient approximation boundary.

  • Output contract: DIST materializes labeled distances without requiring a distance order, predecessor tree, or path witnesses.The comparison–addition model permits adaptive comparisons, arbitrary mixed sums, literals, register reuse, and shared intermediates.
  • Exact arithmetic: ρ_fwd exactly characterizes the minimum worst-case additions on every fixed directed topology.The lower bound applies to adaptive mixed-sum programs, while endpoint-class Dijkstra attains the value uniformly.
  • Acyclic alignment: R(G, s) = {(c, p) : c ≥m −n + 1, p ≥q −ds} is the exact resource region on reachable DAGs.Thus addition and comparison resources align perfectly in the acyclic case.
  • Cyclic conflict: The two-spoke shared-hub graph breaks the resource rectangle because coordinatewise optima need not belong to one program.Its boundary is supported by a reduction to eight strict cells and a finite exhaustive coefficient-state certificate.
  • Endogenous sorting: k log2 k + O(k) comparisons are required at the addition optimum on H_k, while C∗(H_k) = Θ(k).The k-spoke family exposes endogenous sorting, and the interpolation uses entropy-tight bounds with leading constant one when Λ_k,r/k →∞.
  • Universal optimality: OPTDIST charges additions and comparisons to one execution, and transcript cones yield a uniform interpreter matching each topology-specific optimum.The interpreter is synthesizable in polynomial space but may take exponential ordinary time; active-core lifting gives an efficient sublogarithmic-factor bound.

2 Model, output tasks, and benchmarks

The paper studies exact labeled distance-vector computation in a deterministic comparison-addition model, distinguishing charged additions and comparisons while requiring materialized outputs. It defines coordinatewise resource optima and a same-program total-cost benchmark for uniform algorithms.

  • Output tasks: The DIST task requires one materialized register equal to each labeled vertex’s shortest-path distance, without requiring an order, predecessor tree, or witness paths.
  • Comparison-addition model: Charged operations are binary additions and three-way comparisons of materialized finite registers; copying and discrete control are free under stated restrictions.
  • Comparison-addition model: The model permits adaptive branching, mixed and non-path sums, repeated operands, literals, register reuse, equality outcomes, and shared intermediate values.
  • Resource benchmarks: Coordinatewise optima minimize comparisons under an addition budget, while finite infima are attained but need not be attained by one common program.
  • Resource benchmarks: The same-program benchmark takes the worst-case sum of comparisons and additions on one execution, so OPT_DIST is not generally C* + P* or separately optimized worst cases.
  • Uniform algorithms: Exact numerical universal optimality concerns charged-operation equality with OPT_DIST, whereas efficient universality additionally requires near-linear preprocessing and bounded RAM work.

3 Exact addition complexity

The exact addition complexity on every reachable directed topology equals the maximum number of forward nonsource endpoint classes over rooted orders. A uniform endpoint-class Dijkstra algorithm attains this value, while the lower bound survives adaptive mixed-sum programs and related algebraic shortcuts.

  • Parameter and theorem: ρ_fwd counts forward nonsource endpoint classes over rooted vertex orders and is NP-hard to evaluate, although the algorithm does not compute it.
  • Parameter and theorem: Theorem 3.1 establishes the exact addition law for every finite reachable directed multigraph with nonnegative real weights.
  • Upper bound: A uniform endpoint-class version of Dijkstra attains the exact value on every topology by creating additions only for eligible endpoint classes during settlement.
  • Lower bound: The lower bound uses algebraically independent potentials, slacks, equality-kernel projections, and support fibers to force one addition per forward endpoint class.
  • Lower bound: The lower-bound argument remains valid for mixed sums, repeated operands, literals, equality branches, adaptive reuse, and registers containing many endpoint classes.
  • Affine registers: Scaling rays reduce affine-register complications: finite literals become lower order, while leading coefficient records determine nonidentity comparisons.

4 The acyclic baseline

On DAGs, one topological dynamic program simultaneously attains both comparison and addition optima, forming an exact resource rectangle. Minimal shared-hub cycles break this alignment: H2 has coordinatewise corner (4,2), but that corner is infeasible.

  • DAG control case: Theorem 4.1 establishes an exact DAG resource rectangle for comparison and addition costs.One topological dynamic program simultaneously attains both coordinate optima.
  • DAG control case: The DAG lower bounds force m − n + 1 comparisons and q − ds additions on the same execution.Class reduction and incoming-candidate selection attain the matching corner.
  • Cyclic failure: A minimal active cycle destroys the DAG rectangle by making two path extensions compete for one shared hub.The two-spoke shared-hub graph H2 is the smallest useful example.
  • Cyclic failure: Theorem 5.1 shows that H2 has coordinatewise optima (4,2), yet this corner is infeasible.Four comparisons and two additions are separately achievable, but not by one program.
  • Shared-hub family: The Hk extension has P∗(Hk) = k and a linear unrestricted comparison optimum, while addition optimality induces scale-separated spoke-order distinctions.Each spoke contributes one forward endpoint class, and addition-optimal programs must distinguish k! orders.

6 The comparison–addition law on Hk

The shared-hub family Hk exhibits an entropy-controlled comparison–addition tradeoff: fewer additions force more spoke-order information, while bounded-width weak ordering supports a rolling computation. This exposes why scalar same-program cost cannot be formed by adding coordinatewise optima.

  • Tradeoff law: Theorem 6.1 gives a deterministic entropy-tight Pareto law uniformly over addition slack 0 ≤ r ≤ k.Its sharper form is Fk(r) = (1 + o(1))Λk,r when Λk,r/k →∞.
  • Lower bound: Addition exposure limits the compatible spoke permutations on each transcript, yielding the entropy lower bound through exposure deadlines and a binary transcript tree.If a spoke pair remains hidden, it can become simultaneously essential to the hub and later outputs.
  • Upper bound: Deterministic multiple selection partitions spoke values into blocks of size at most r + 1, and a rolling scan spends extra additions only in the crossing block.Earlier blocks need inward candidates, later blocks outward candidates, and at most r crossing elements need both.
  • Same-program benchmark: The cyclic tradeoff requires a same-program scalar benchmark because coordinatewise optima may belong to different programs.The balanced envelope chooses one feasible budgeted program rather than computing C∗ + P∗.

8 Exact numerical universal optimality

The paper characterizes exact numerical universal optimality through a transcript-cone game that reproduces the physical program model. One uniform interpreter matches OPTDIST on every topology, although policy generation may take exponential time and efficient constant-competitive navigation remains open.

  • Transcript-cone game: The transcript-cone game represents held coefficient vectors and comparison outcomes as a cone of consistent inputs.A label is ready only when one fixed held vector is correct throughout the entire cone.
  • Transcript-cone game: Theorem 8.1 proves WING({0, e1, . . . , em}, ∅, K) ⇔ OPTDIST(G, s) ≤ K.Game moves correspond exactly to legal additions and comparisons, while terminal readiness supplies materialized outputs.
  • Uniform optimality: One deterministic uniform interpreter attains OPTDIST on every finite reachable topology without topology-specific advice.It reconstructs the optimal strategy from the input graph.
  • Uniform optimality: Optimal next actions are synthesizable in polynomial space, but direct policy search may require 2^poly(n+m) ordinary time.This separates exact charged-operation optimality from efficient navigation.
  • Efficient boundary: An active-core reduction combined with deterministic directed SSSP yields one explicit uniform exact-DIST algorithm with topology preprocessing O(m + n).Its charged bound is O(OPTDIST · sqrt(log+(2 + OPTDIST) log log+(4 + OPTDIST))).
  • Efficient boundary: A polynomial-time constant-competitive navigation rule remains open, although exact numerical universal optimality is settled.The directed-SSSP routine is used as a black box in the active-core lifting.

10 Related work

The paper distinguishes labeled-distance output from distance-order output and positions its results against prior shortest-path, algebraic-complexity, selection, and universal-optimality frameworks. It also isolates scope boundaries: exact claims concern the stated comparison–addition model, fixed directed topologies, and labeled DIST.

  • Output contracts: Prior universal-optimal Dijkstra results target distance-order output, whereas this paper benchmarks materialized labeled distances.The distinction is between producing vertices in distance order and computing explicit labeled distance values.
  • Directed numerical SSSP: Directed-SSSP work below the sorting barrier supplies an efficient black box but does not characterize the fixed-topology same-program optimum OPTDIST.The lifting theorem uses that work rather than replacing its shortest-path routine.
  • Adjacent complexity models: Algebraic path-complexity and comparison–addition predecessors use different program, output, or relaxation requirements from this adaptive labeled-DIST model.The present competitors may compare arbitrary held aggregates and use mixed sums, literals, equality, and cross-output sharing.
  • Selection and partial orders: Deterministic multiple selection contributes the upper-side primitive, while the paper’s contribution is the shortest-path reduction from addition budgets to banded-permutation entropy.The paper does not claim novelty for the selection primitives themselves.
  • Scope and contribution boundaries: Cycles make coordinatewise optimization insufficient: H2 is the smallest audited obstruction, so C* + P* need not describe any physical algorithm.The same-program benchmark OPTDIST repairs the quantifiers by summing charges on one execution before minimizing over programs.
  • Open boundaries: Efficient exact uniformity remains open because the ratio-one interpreter may require exponential ordinary time to navigate its optimal policy.The paper separates existence of an optimal numerical policy from efficient access to its next operation.

13 Conclusion

The conclusion presents a topology-specific theory for exact labeled distances: arithmetic complexity is governed by ρfwd, DAGs align both resources, and shared-hub cycles create an entropy-driven tradeoff. A transcript-cone interpreter achieves exact charged-operation optimality uniformly, while efficient constant-competitive navigation remains unresolved.

  • Core structural conclusions: The exact addition invariant is ρfwd, while DAGs align comparison and addition costs and a minimal active cycle breaks that alignment.The shared-hub family shows that addition savings can force sorting-scale internal information despite labeled-vector output.
  • Universal optimality: The correct total benchmark is the same-program worst-case sum OPTDIST, not the sum of separately optimized coordinates.Transcript cones yield a single uniform interpreter matching every specialized numerical optimum in charged operations.
  • Addition invariant: Forward endpoint classes count nonsource classes whose tails precede their heads in a rooted order, with endpoint classes grouping parallel arcs.A rooted order starts at the source and gives every nonsource vertex a forward entering endpoint class.
  • Algorithmic qualification: The addition-optimal uniform algorithm never computes ρfwd, whose computation is NP-hard by reduction from directed feedback arc set.The algorithm attains the value without explicitly evaluating the parameter.

B.1 A uniform upper bound

Endpoint-class Dijkstra gives a uniform addition-optimal algorithm: it reduces parallel arcs to class minima and adds only when a forward nonsource class is processed. A coefficient-space lower bound shows that no adaptive mixed-sum program can do better, even with unlimited comparisons.

  • Uniform upper bound: Endpoint-class Dijkstra forms each endpoint-class minimum and creates one path-extension register only when a nonsource tail is settled before its head.Final settled registers are copied to labeled outputs, and the construction remains valid for zero weights and ties.
  • Upper-bound count: For every weighting, the algorithm uses at most the number of forward nonsource endpoint classes in the settlement order, hence at most ρfwd(G, s) additions.A maximizing rooted order and a realizing positive weighting establish equality for each fixed topology.
  • Algebraic proof: Kernel dimensions from common-endpoint path differences supply the required equality normals, while fiber opening charges additions for distinct output fibers.The projection is essential because outside primitive coordinates collapse to one zero-divergence vector.
  • Lower-bound mechanism: The lower bound projects arbitrary coefficient-vector executions onto a rooted spanning DAG and opens fibers corresponding to missing output divergences.This permits outside-contaminated mixed sums and avoids assuming path-register normal form.
  • Theorem: The arbitrary-topology addition theorem remains valid with unlimited comparisons and self-loops, and endpoint-class Dijkstra attains it uniformly.The uniform algorithm needs no computation of the NP-hard parameter ρfwd.
  • DAG specialization: On DAGs, the full comparison–addition frontier is exact: C*(G,s)=m−n+1, P*(G,s)=q−ds=ρfwd(G,s), and one program attains both optima.A potential-tie input makes the two lower bounds simultaneous.

D The first cyclic obstruction

The two-spoke shared-hub graph is the first cyclic obstruction to the DAG rectangle: its coordinatewise optima are incompatible, requiring five comparisons at the two-addition budget. Its k-spoke generalization preserves a shared hub candidate and exposes the broader resource interaction.

  • Motivation: The DAG rectangle can fail when a cycle makes two path extensions compete for one hub; H2 is the smallest useful example.The graph has source-to-hub and two directed feedback-spoke structures.
  • Distance formulas: The H2 distances are dx=min{a,b+z,c+q}, dv=min{b,dx+u}, and dw=min{c,dx+p}.The hub candidate is selected from the direct route and two inward spoke routes, then reused for outward routes.
  • Nonrectangularity: Consequently, C*(H2)=4, P*(H2)=2, but C*2(H2)=5, so the first cyclic example has a genuinely nonrectangular frontier.The two coordinatewise minima cannot be achieved together by one program.
  • Upper bounds: A four-comparison, four-addition program computes H2 by materializing both inward candidates, selecting the hub, and extending it to the two spoke outputs.The construction explicitly demonstrates the upper endpoint for the comparison optimum.
  • Addition-optimal program: A two-addition program uses at most five comparisons by branching on direct source values and computing only the inward or outward candidate still needed on each branch.Weak inequalities make the branch choices valid for ties and zero weights.
  • Comparison lower bound: H2 has eight full-dimensional output cells with distinct affine labels, yielding a human-readable lower bound of four comparisons.Connected facet adjacencies force a comparison wall to split a cell if only three comparisons are available.
  • Two-addition obstruction: No program with at most four comparisons and two additions computes H2; the finite coefficient-state certificate checks arbitrary mixed sums, repeated operands, and legal adaptive actions.The certificate is the only part of this lemma still subject to independent human proof review.
  • Shared-hub family: The shared-hub family Hk gives every spoke one inward and one outward route while all spokes share the same hub candidate and retain labeled spoke outputs.For each spoke, exactly one directed spoke arc is forward in any rooted order, yielding ρfwd(Hk,s)=k.

E.2 The scalar comparison coordinate

The scalar comparison baseline for H_k is linear, but addition-optimal exact DIST computation reaches the sorting scale. Its lower bound uses synchronized threats and pair visibility under arbitrary mixed additions.

  • Scalar baseline: C∗(H_k) = Θ(k) for the scalar comparison optimum.The lower bound uses 2^k independent direct-versus-translated output patterns, while a simple algorithm uses at most 2k comparisons.
  • Addition-optimal endpoint: At the addition optimum, comparison cost is k log2 k + O(k), even though labeled distances are the only requested outputs.The construction and lower bound distinguish all k! spoke orders without requiring ordered output.
  • Threat mechanism: The lower-bound mechanism exposes at most t disjoint designated spoke pairs after t additions, including arbitrary mixed supports and repeated operands.Pair-connectivity follows from a component argument: every newly visible pair requires a paid connecting edge.
  • Threat mechanism: Scale-separated main and threat executions remain synchronized until the threatened pair becomes visible.This synchronization preserves control states, coefficient vectors, and comparison outcomes before pair visibility.
  • Threat mechanism: With at most k + r additions, every pair in a permutation must be exposed by position s no later than s + r.Otherwise a synchronized threat makes multiple shortest-path outputs essential after too few additions remain.

F.5 Entropy lower bound

The H_k tradeoff interpolates between a linear scalar floor and an entropy-dominated sorting regime. Bounded-bucket weak ordering supplies the upper bound, while deadline arguments count compatible permutations for the lower bound.

  • Entropy lower bound: The lower bound counts permutations compatible with addition-induced exposure deadlines, after each transcript fixes pair ranks and exposure times.A transcript is compatible with only a bounded number of banded permutations, yielding the entropy term after logarithms.
  • Weak ordering: A bounded-bucket weak ordering partitions keys into blocks of width at most h, with every earlier block smaller than every later block.Internal order within a block is not produced; its comparison complexity is governed by the corresponding information bound.
  • Weak ordering: The upper bound uses deterministic multiple selection, whose lower-order information term is not strengthened to a uniform additive-O(k) formula.The paper treats multiple selection and partial-order production as standard primitives and contributes their interface to rolling SSSP.
  • Rolling computation: For h = r + 1, rolling-block processing computes exact labeled distances with at most k + r additions and O(k) additional comparisons.Only the crossing block can require both inward and outward candidates; later blocks need only outward candidates.
  • Entropy-tight law: C_{k+r}^*(H_k) = Θ(k + Λ_{k,r}) uniformly for 0 ≤ r ≤ k.The entropy term has leading constant one whenever Λ_{k,r}/k →∞.

J Exact numerical universal optimality

The paper defines a transcript-cone game for exact numerical policies and proves that one uniform interpreter matches the same-program optimum on every topology. This optimal navigation is polynomial-space computable but may take exponential time.

  • Exact universal optimality: One fixed deterministic uniform interpreter matches OPTDIST exactly in charged operations on every topology.The interpreter recomputes a winning move from the current transcript-cone state and executes the corresponding physical operation.
  • Transcript-cone game: Literal constants can be removed through a recession normal form without increasing any input’s charged cost.Positive homogeneity routes comparisons using recession forms and fixed intercept signs while preserving correctness on the closed nonnegative orthant.
  • Transcript-cone game: A transcript-cone state records held homogeneous coefficient forms and observed comparison outcomes, while readiness requires fixed correct output registers throughout the cone.Additions and comparisons reproduce the physical program model, including equality outcomes and feasible transcript constraints.
  • Computational status: The exact policy and winning next actions are computable in polynomial space, but direct search may require exponential time.The succinct state representation avoids storing the unfolded strategy tree without making next-action search fast.
  • Active-core reduction: An active-core reduction is benchmark-neutral for dominator-inactive arcs and bounds the residual core using the same-program optimum.The factorization uses a same-input active-edge charge rather than separate comparison and addition lower bounds.

K.2 Lifting a general directed-SSSP algorithm

The efficient uniform algorithm reduces the topology to an active core and applies a deterministic directed-SSSP routine. It preserves exact DIST output while incurring a sublogarithmic-factor overhead over OPTDIST.

  • Efficient lifting: The directed-SSSP routine is used as a black box; the topology-sensitive guarantee comes from active-core reduction and benchmark charging.The paper separates the external numerical routine from its own topology-sensitive reduction.
  • Efficient lifting: The efficient uniform exact DIST algorithm uses O(m + n) topology preprocessing.Dominator computation, source-class grouping, and active-core construction are topology-only operations.
  • Efficient lifting: Its charged-operation bound is O(OPTDIST(G, s)√log(2 + OPTDIST(G, s)) log log(4 + OPTDIST(G, s))).The residual active-core instance has size controlled by the same-program benchmark, and source comparisons are added separately.
  • Scope: The resulting factor remains above the linear specialized programs available for H_k, so efficient constant-competitive navigation remains unresolved.The bound narrows but does not close the gap between efficient uniform algorithms and topology-specific optima.

N Active-core proofs and the same-input edge charge

The active-core argument preserves shortest-path distances and the DIST benchmark while reducing the graph to a small virtual-source core. A paired-order construction then charges active edges and endpoint classes to the same-program optimum, with cyclic examples illustrating the resulting comparison–addition tradeoffs.

  • Inactive deletion: OPTDIST(G, s) = OPTDIST(Ga, s), so deleting inactive arcs preserves both distances and the benchmark.Programs transfer between the original and reduced graphs by ignoring inactive registers or substituting zero, without increasing numerical-operation budgets.
  • Virtual-source reduction: The active core satisfies dG(s, v) = dH(q, v), while vertices outside the core have distance av and |V(H)| ≤2k + 1.Source primitives are replaced by their held minima, and core paths can be expanded back to source paths.
  • Same-input edge charge: One of two rooted orders has m≺≥ms + k/2 and q≺≥n −1, yielding σ + k ≤2L∗≤2OPTDIST.The paired-order proof reverses incomparable dominator-tree vertices so each active primitive is forward in at least one order, while source arcs are forward in both.
  • Cyclic resource region: On Tr, the complete DIST region is {(c, p) : c ≥2, p ≥r + 1}.Two comparisons resolve the cyclic-core minima, while r suffix outputs require r additions; the lower bounds follow from core restriction and forward endpoint classes.
  • Two-spoke tradeoff: For H2, a five-comparison, two-addition program exists, although four comparisons are achievable with more additions.The two-addition construction uses mutually exclusive additions, while the lower-bound arguments analyze output cones and connected cell geometry.
Loading 2609.04825v1…