我们研究了在给定图中近似最短环长度的问题，即图的环长。Kadria等人[SODA'22]和Roditty与Trabelsi [arXiv'25]提出的无权图的最新近似算法达到了以下折衷：对于每个整数 $k \geq 2$，存在一个运行时间为 $\tilde{O}(n^{1+2/k})$ 的算法，该算法实现了对无权 $n$-节点图的环长的 $(2k/3)$-近似。本文的第一个结果是，对于 $m$-边、$n$-节点的非负实边权图，也实现了相同的折衷：一个运行时间为 $\tilde{O}(m+n^{1+2/k})$ 的 $(2k/3)$-近似算法。在加权图中，对 $m$ 的依赖是不可避免的。我们的结果改善了 Kadria 等人 [SODA'22] 和 Ducoffe [ICALP'19 和 SIDMA'21] 的工作，后者只能对某些 $k$ 的值实现这样的折衷。我们还证明了无权图中环长近似和相关问题的新精细下界。
博主点评： 本文提升了加权与无权图中最短环近似的算法效率，尤其是在处理边权时的复杂度优化，对图论的研究具有重要的推动作用。