Shortest path weights in DAGs need exponential integers in some cases
Exponential Lower Bounds for Integer-Weighted Shortest-Paths Preservers of DAGs
Data Structures and Algorithms
Summary
The paper looks at how to simplify graphs while keeping the shortest paths the same. A shortest path is the quickest way to get from one point to another in a network. The authors focus on a certain kind of graph called a DAG, where there are no loops. Previous work showed that you can always adjust weights without changing shortest paths but sometimes with non-integer numbers. This paper proves that if you want these weights to be integers, sometimes you need extremely large exponential values, even in very simple DAGs. They also show smaller integer weights work if the DAG is simplified further.
What this means in practice
- •For graph algorithm developers: Understand limitations of integer reweighting in DAG simplifications to avoid infeasible large weights in implementations.
- •For network routing engineers: Recognize scenarios where integer-based shortest path adjustments require impractically large weights, preventing certain optimizations.
A theory result. No direct application yet.
Authors
Michael Yi Wang, Nicole Wein
Abstract
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^{Ω(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 $α$-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 $α>1$.