我们研究了CUT查询在揭示未知超图结构方面的潜力。简单图允许以最优的 $O(n)$ 查询复杂度实现连通性算法，但超图面临一个基本的可识别性障碍：不同的超图可能共享相同的切割轮廓，这使得一般情况下无法精确学习边缘，这是图连通性算法中的一个关键原始。
我们首先提出了一种零错误随机算法，该算法使用 $O(n)$ 期望查询来识别任何加权超图的连通分量，匹配 $\Omega(n)$ 下界。该方法通过引入“独立家族”的概念——不共享超边的顶点子划分，利用辅助加权图连通性技术迭代粗化它们，从而绕过重建障碍 [Liao-Chakrabarty, 2024]。
其次，我们证明了精确学习的不可能性依赖于超边的奇偶性。对于偶奇超图，我们展示了结构可通过对CUT函数进行Möbius变换来重建，从而实现二分搜索风格的顶点识别。这为 $r$ 有界偶超图提供了在 $\tilde{O}_r(kn)$ 查询中获取 $k$-连通性证书的确定性算法。
最后，我们绕过了奇偶性和秩约束，对于线性超图实现了次二次的 $\tilde{O}(kn^{1.5})$ 查询复杂度，以获得 $k$-连通性。这显著改善了通过对称子模函数最小化导出的总体 $\tilde{O}(n^2)$ 界限。
博主点评： 本文展示了通过CUT查询技术在超图学习和连通性方面的潜力，尤其是提出的零错误随机算法和对偶奇超图的重建方法，展现了超图领域中尚未被充分探索的可能性。研究的进展不仅在理论上具有重要意义，也为实际应用提供了新的思路。