We investigate the graph simplification problem introduced by Bernstein, Bodwin, and Wein at ITCS'24. Starting from a graph with arbitrarily large positive edge weights, the goal is to reweight the edges so that the sequence of vertices and edges along every shortest path is preserved while the aspect ratio (largest weight divided by smallest weight) is kept small. The authors showed that for general directed or undirected graphs, any shortest‑path‑preserving reweighting may require an exponential aspect ratio, so a polynomial bound is not guaranteed. In contrast, they proved that every directed acyclic graph (DAG) admits a reweighting with linear aspect ratio, but the resulting weights are typically non‑integers. This raises the natural open question: does every DAG admit an integer reweighting with polynomially bounded aspect ratio?
We answer this question negatively. We construct a family of extremely simple DAGs for which any integer reweighting that preserves the shortest‑path structure must use weights of size at least $2^{\Omega(n)}$. These DAGs consist of only three layers of vertices, with the middle layer containing three vertices, yet they already force exponential weight growth. Moreover, we show that if the middle layer is reduced to two vertices, a linear‑size integer reweighting becomes possible, highlighting the critical role of layer width.
We also extend the lower bound to an approximate variant: it suffices to preserve a single $\alpha$‑approximate shortest path from the original graph as an exact shortest path after reweighting. Even for any finite approximation factor $\alpha > 1$, the exponential lower bound still holds. This demonstrates that allowing approximation does not alleviate the inherent difficulty of achieving integer weights.
Review: The paper demonstrates, via a minimal three‑layer DAG construction, that preserving shortest‑path structure with integer weights can be inherently exponential, closing the gap left by previous results on real‑valued reweightings and revealing how layer size governs feasibility, thereby guiding future work on integer‑constrained graph simplification.