We investigate the power of CUT queries to reveal the structure of unknown hypergraphs. While simple graphs allow for optimal $O(n)$ query connectivity algorithms, hypergraphs face a fundamental identifiability barrier in that distinct hypergraphs can share identical cut-profiles, making exact edge learning impossible in general, a primitive crucial in the graph connectivity algorithms.
We first present a zero-error randomized algorithm that identifies the connected components of any weighted hypergraph using $O(n)$ expected queries, matching the $\Omega(n)$ lower bound. This approach bypasses the reconstruction barrier by introducing the notion of 'independent families' — vertex subpartitions that do not share hyperedges — and iteratively coarsening them using auxiliary weighted graph connectivity techniques [Liao-Chakrabarty, 2024].
Second, we demonstrate that the impossibility of exact learning depends on hyperedge parity. For even-parity hypergraphs, we show that the structure is reconstructible using a Möbius transform on the CUT function to implement binary-search-style vertex identification. This yields deterministic algorithms for obtaining $k$-connectivity certificates for $r$-bounded even hypergraphs in $\tilde{O}_r(kn)$ queries.
Finally, we bypass parity and rank constraints for linear hypergraphs, achieving a subquadratic $\tilde{O}(kn^{1.5})$ query complexity for $k$-connectivity. This significantly improves upon the general $\tilde{O}(n^2)$ bound derived via symmetric submodular function minimization.
Blogger's Review: This paper showcases the potential of CUT query techniques in hypergraph learning and connectivity, particularly through the proposed zero-error randomized algorithm and the reconstruction method for even-parity hypergraphs. The advancements in this research hold significant theoretical importance and offer new insights for practical applications.