PaperlayerView exact revision on arXiv

Source-linked AI summary

Exponential Lower Bounds for Integer-Weighted Shortest-Paths Preservers of DAGs

Michael Yi Wang, Nicole Wein

arXiv:2609.12211v1cs.DS

TL;DR

The paper asks whether DAGs admit shortest-path-preserving reweightings with polynomially bounded integer weights, a question motivated by the usefulness of integer weights. It constructs a reduction using topological-order functions and rigid shortest-path structure, and proves exponential lower bounds even for three-layer DAGs with three middle-layer vertices, including for every finite α > 1.

  • Problem

    Although DAGs have a known linear-aspect-ratio preserver, its weights are not integers, leaving open whether polynomially bounded integer weights suffice.

    Source: §1.2 · p. 3

  • Method

    The construction assigns edge weights from topological-order functions and enforces rigid shortest-path structure so the corresponding equations constrain reweightings.

    Source: §2.2 · p. 10

  • Results

    Integer-weighted preservers can require exponentially large weights even for three-layer DAGs with three middle-layer vertices, and this holds for every finite α > 1.

    Source: §1.3 · pp. 4–5

  • Takeaways & Limitations

    For DAGs, restricting reweightings to integer edge weights changes the known linear-versus-exponential picture.

    Source: §1.3 · p. 4

    In the α-stretch construction, the exact-version argument alone does not force preservation of P when P′ is also α-approximate, even for α = 1 + ε.

    Source: §4 · p. 17

Abstract

from arXiv · show

We study a graph simplification problem introduced by Bernstein, Bodwin, and Wein [ITCS'24]. We start with a graph with arbitrarily large positive edge weights and the goal is to reweight the edges to small aspect ratio (ratio between largest and smallest weight) while preserving the shortest paths structure (the sequence of vertices and edges along shortest paths). They studied whether polynomial aspect ratio is always possible. They proved that for general graphs, both directed and undirected, it is not: there exist graphs for which any shortest-paths preserving reweighting requires exponential aspect ratio. In contrast, they showed that every DAG (directed acyclic graph) admits a reweighting with linear aspect ratio. However, the resulting edge weights are not integers. This motivated them to pose the open question of whether all DAGs admit a reweighting with polynomially-bounded integer edge weights. Our main result is to answer this question in the negative: we prove that there exist DAGs for which any shortest-paths preserving integer reweighting requires weights of size $2^{\Omega(n)}$. In fact, this is even true when the DAG has very simple structure: 3 layers of vertices with only 3 vertices in the middle layer. In contrast, we show that if the number of vertices in the middle layer is decreased to 2, then a linear upper bound is possible. We extend our exponential lower bound to the approximate version of the problem where only a single $\alpha$-approximate shortest path in the original graph must be preserved as an exact shortest path in the reweighted graph. Our exponential lower bound holds even for any finite approximation ratio $\alpha>1$.

1 Introduction

The paper studies whether graph edges can be reweighted to reduce aspect ratio while preserving shortest-path structure, and answers a longstanding integer-weight question negatively for DAGs. Its results show exponential lower bounds even for simple three-layer DAGs, alongside a linear upper bound when the middle layer has two vertices.

1 Introduction

  • Reweighting seeks to reduce edge-weight aspect ratio without changing the vertex-and-edge sequences of shortest paths.Shortest-path lengths themselves may change substantially.Source: §1 · p. 2

1.2 Known Results

  • Earlier work ruled out polynomial aspect ratio for general graphs but gave DAGs a linear-aspect-ratio preserver, leaving polynomially bounded integer weights as an open question.The known DAG construction used non-integer weights; the open question also asked whether allowing stretch would help.Source: §1.2 · pp. 3–4

1.1 Motivation

  • Integer weights matter because they enable techniques such as bucketing, motivating a polynomially bounded integer-weight preserver for DAGs.Bernstein, Bodwin, and Wein also identified a potential application to extending parallel and distributed results to arbitrary weighted graphs, assuming an efficient integer result.Source: §1.2 · p. 3

1.3 Our Results

  • DAGs with three middle-layer vertices can require exponentially large integer-preserver weights, including for every finite α > 1.With two middle-layer vertices, integer weights in [1, ..., |V1| + |V3| + 1] suffice; the lower bounds are proved for the stronger gap-1 preserver condition, which integer-weighted preservers automatically satisfy.Source: §1.3 · pp. 4–5

1.4 Our Techniques

  • The paper’s lower-bound strategy differs from the symmetric cycle-based constructions for general graphs, which derive weight growth by comparing path lengths across layers.The DAG approach instead reduces from a topological-order problem because DAG asymmetry can let some edges absorb weight and allow others to decrease.Source: §1.4 · pp. 5–6
  • The proof reduces a problem about additive triples and compatible topological orderings to shortest-path preservers, then proves an exponential range lower bound for those orderings.The reduction connects the minimum ordering range to the minimum maximum weight of a gap-1 preserver; a modified construction handles α-stretch, and a reverse reduction establishes an equivalence for the three-middle-vertex setting.Source: §1.4 · pp. 6–7
  • The α-stretch construction updates edge weights so each original shortest path becomes the only α-approximate shortest path in the modified graph.This avoids ambiguity that could arise in the exact-version construction when a competing path is also α-approximate.Source: §1.4 · pp. 7–8

2 Reduction from 3-Topological Order Preservers to Shortest-Paths Preservers

The section reduces additive triples of DAGs to 3-layered DAGs with three middle-layer vertices, relating the minimum order range to the minimum maximum edge weight of a gap-1 shortest-paths preserver. The construction encodes topological-order constraints as shortest-path choices, and its analysis recovers a 3-topological order preserver from any qualifying reweighting.

2 Reduction from 3-Topological Order Preservers to Shortest-Paths Preservers

  • The reduction bounds the minimum 3-topological-order range by twice the minimum possible maximum edge weight of a gap-1 preserver of the constructed DAG.The constructed DAG has three layers and exactly three middle-layer vertices.Source: §2 · pp. 8–9

2.1 Construction

  • The construction uses original vertices in the first layer, three middle-layer vertices, and one third-layer vertex for each edge of the additive triple.Edges connect consecutive layers, with the available middle-to-last-layer routes determined by which of the three DAGs contains the represented edge.Source: §2.1 · p. 9

2.2 Intuition Behind the Construction

  • Paired routes encode topological-order differences, with their edge-weight differences chosen to fall between the values at the endpoints of each represented edge.The construction uses the additive relation h1 + h2 = h3 to set weights; adding a constant to every edge preserves shortest paths while making weights positive.Source: §2.1 · p. 9, §2.2 · p. 11

2.3 Analysis

  • The unique shortest-path choices let any gap-1 preserver define topological orders that satisfy h′1 + h′2 = h′3 and have range at most twice its maximum edge weight.The three edge classes use the respective middle-layer pairs z1,z2; z2,z3; and z1,z3.Source: §2.3 · pp. 11–12

3 Lower Bound for 3-Topological Order Preservers

The section constructs additive triples of DAGs whose 3-topological order preservers must have exponentially large range. Its alternating-level construction yields a gap that doubles across levels, forcing a gap of at least 2t at the final level.

3.1 Construction

  • The construction uses a common vertex set with two initial vertices and t additional levels of four vertices each, with edges within or between adjacent levels.The edge patterns alternate between the two patterns shown for the first few levels in Figure 4.Source: §3.1 · p. 14, Figure 4 · p. 15

3.2 Analysis

  • The three DAGs form an additive triple: they admit topological orderings h1, h2, and h3 with h1 + h2 = h3.The construction defines h1 and h2 by alternating their assignments across odd and even levels.Source: §3.2 · pp. 14–15
  • The constructed additive triple forces one topological-order gap at the final level to be at least 2t, with t = Ω(n + m), giving an exponential lower bound.The gap is in h′1 or h′2 depending on the parity of t.Source: §3 · p. 13, §3.2 · p. 16

4 Approximate Version

The section extends the exponential lower bound to α-stretch shortest-paths preservers for every α > 1. It modifies the edge weights so that paths used in the lower-bound argument are uniquely α-approximate shortest paths, then verifies the resulting path and weight inequalities.

4 Approximate Version

  • For every α > 1, the exponential lower bound extends to α-stretch gap-1 shortest-paths preservers on 3-layered DAGs with three middle-layer vertices.The theorem’s graph has |V2| = 3.Source: §4 · p. 17
  • When h1(u) is large, the original construction’s alternate path can remain within α times the designated path’s weight, so an approximate preserver may choose either path.That choice can remove the edge inequalities used to prove the exponential lower bound.Source: §4 · p. 17

4.1 Construction

  • The modified weighting aims to make each path in P the only α-approximate shortest path between its endpoints, forcing those paths to remain shortest in any α-stretch gap-1 preserver.The construction assigns edge exponents so that an alternate path has weight greater than α times the designated path’s weight.Source: §4 · p. 17, §4.1 · pp. 17–18

4.2 Analysis

  • The exponent inequalities give a gap of at least 2 between the relevant maxima for edges in E1 and E2, which supports the uniqueness analysis.For example, the section states max{p(u, z2), p(v, z1)} ≥ max{p(u, z1), p(v, z2)} + 2 and the analogous inequality for z2 and z3.Source: §4.2 · p. 20
  • Under the new weights, the designated paths for edges in E1, E2, and E3 are unique α-stretch shortest paths between their endpoints.The analysis establishes the path choices for each edge class and adapts the E1 proof to E2 and E3 by changing the intermediate vertices.Source: §4.2 · pp. 21, 23

5 Linear Upper Bound for |V2| = 2 Case

For every 3-layered DAG with two middle-layer vertices, the section constructs an integer-weight shortest-paths preserver with weights bounded linearly by the number of outer-layer vertices.

5 Linear Upper Bound for |V2| = 2 Case

  • Every 3-layered DAG with |V2| = 2 has a shortest-paths preserver with integer edge weights in [1, |V1| + |V3| + 1].The proof verifies that the constructed weights preserve all shortest paths.Source: §5 · pp. 23–24
  • Using a topological ordering of the auxiliary graph, the construction assigns outer-layer-to-middle-layer weights so the originally shorter two-edge route remains shorter after reweighting.The proof checks both possible shortest-path routes between the outer layers.Source: §5 · pp. 23–24
  • The construction forms an auxiliary graph with edges between outer-layer vertices, oriented according to which middle vertex lies on their shortest path.The auxiliary graph is bipartite and the section proves it is acyclic.Source: §5 · p. 23

A Reduction in the Other Direction

The section reduces a shortest-paths-preserver problem for a 3-layered DAG with three middle-layer vertices to a 3-topological-order-preserver problem.

A Reduction in the Other Direction

  • The constructed additive triple has a total of 2 · |V1| · |V3| edges across its three DAGs.Source: A Reduction in the Other Direction · p. 27
  • For |V2| = 3, the reduction bounds the minimum maximum edge weight of a gap-1 shortest-paths preserver by one plus the minimum range of a 3-topological-order preserver.The theorem constructs an additive triple of DAGs for this comparison.Source: A Reduction in the Other Direction · p. 27

A.1 Construction

The construction assumes a complete 3-layered DAG with three middle-layer vertices and assigns auxiliary edges according to each outer-layer pair’s shortest route.

A.1 Construction

  • The construction may assume every possible edge between adjacent layers is present, since missing edges can be added with sufficiently large weights without appearing on shortest paths.A shortest-paths-preserving reweighting of the completed graph yields one for the original graph by ignoring the added edges.Source: §A.1 · p. 27
  • When z1 gives the shortest route, the construction adds (u, v) to E*1 and E*3; when z2 does, it adds (v, u) to E*1 and (u, v) to E*2.Source: §A.1 · p. 28
  • When the path u →z3 →v is the shortest path in G, the described construction adds the reversed edge (v, u) to both E*.Source: §A.1 · p. 28

A.2 Analysis

The analysis constructs shortest-paths preservers from topological orderings of derived DAGs. The construction preserves shortest paths with a gap of at least 1, and the proof also establishes a linear relation between the edge counts of the derived graphs and the layer sizes.

A.2 Analysis

  • The three derived graphs have a total of 2 · |V1| · |V3| edges.Source: §A.2 · p. 28
  • The proof verifies that the constructed orderings are valid topological orderings for the derived graphs.Source: §A.2 · p. 28
  • The construction produces a gap-1 shortest-paths preserver from valid topological orderings of the derived graphs.Source: §A.2 · p. 29
  • The construction can be modified to yield a positively weighted gap-1 preserver.Source: §A.2 · pp. 29–30
  • For each endpoint pair, the reweighting preserves relative path differences, so shortest paths remain shortest with gap at least 1 to other paths.Source: §A.2 · p. 30
Loading 2609.12211v1…