本文研究无向图 $G=(V,E)$ 在最多 $f$ 条边失效的情况下,如何仅通过顶点 $s,t$ 与失效边集合 $F\subseteq E$($|F|\le f$)的标签来判断 $s$ 与 $t$ 在 $G-F$ 中是否连通。我们构造了一种标签方案,标签长度为 $O(\log^{2} n)$ 位,且标签可以在确定性多项式时间内计算得到。该方案相较于 Long、Pettie、Saranurak\'25 给出的 $\tilde{O}(\sqrt{f})$ 确定性上界有显著提升,并在 $f = \Omega(\log^{2} n)$ 时略优于 Dory、Parter\'21 与 Long 等人的随机上界 $O(\min\{f+\log n,\;\log^{2} n\log f\})$。更重要的是,对于任意 $f$,这是首个在所有查询上同时正确且标签大小为 $\tilde{O}(1)$ 的方案。技术上,我们将 Dory 与 Parter 的基于环空间的标签方法与 Knauer\'26 最近关于稀疏环基的结果相结合,实现了稀疏表示与快速查询的统一。
点评:该工作在理论上把确定性容错连通性标签的复杂度推向了新的极限,为后续在大规模网络容错监测中的实际实现提供了可行的路径。