Query Complexity of Hypergraph Connectivity and Learnability using CUT Oracles
2026-07-01 • Data Structures and Algorithms
Data Structures and AlgorithmsDiscrete Mathematics
AI summaryⓘ
The authors study how to learn the structure of complex networks called hypergraphs by asking queries about cuts (ways to split vertices). They show that unlike simple graphs, not all hypergraphs can be exactly reconstructed from these queries due to identical cut patterns. They present a randomized method that efficiently finds connected parts of any weighted hypergraph and also develop special algorithms for certain types of hypergraphs based on properties like edge parity and linearity. These methods improve query efficiency compared to previous general approaches.
HypergraphCut queriesConnected componentsZero-error randomized algorithmIndependent familiesMöbius transformk-connectivityr-bounded hypergraphSymmetric submodular function minimization
Authors
Deeparnab Chakrabarty, Hang Liao
Abstract
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 $Ω(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.