我们研究的是 Bernstein、Bodwin 与 Wein 在 ITCS'24 提出的图简化问题。给定一个带有任意大正权重的图，目标是重新赋权，使得所有最短路的顶点序列保持不变，同时边权的比例（最大权重除以最小权重）尽可能小。作者证明，对一般有向或无向图，任何保持最短路结构的重新赋权都可能需要指数级的比例，因此多项式比例并非总是可行。相反，他们展示了每个有向无环图（DAG）都可以通过线性比例的重新赋权实现，但得到的权重往往不是整数。于是出现了一个自然的开放问题：是否所有 DAG 都存在多项式上界的整数权重重新赋权？
本文给出否定答案。我们构造了一类极其简单的 DAG，使得任何保持最短路结构的整数重新赋权都必须使用大小至少为 $2^{\Omega(n)}$ 的权重。具体而言，这些 DAG 只包含三层顶点，且中间层仅有三个顶点，但仍迫使权重指数增长。进一步地，我们证明如果将中间层的顶点数降至两个，则可以实现线性上界的整数重新赋权，表明层数和中间层规模对问题的难度有关键影响。
此外，我们将下界扩展到近似版本：仅要求原图中任意一条 $\alpha$‑近似最短路在重新赋权后成为精确最短路。即使在任意有限的近似比 $\alpha > 1$ 下，上述指数下界仍然成立。该结果表明，即使放宽到单条近似最短路的保持，整数权重的需求仍然可能是指数级的。
点评：本文通过极简结构的 DAG 展示了整数权重保持最短路的本质难度，填补了此前仅有实数权重上界的空白，并揭示了层数与中间层规模在可行性中的微妙作用，为后续在整数权重约束下的图简化研究指明了方向。