{"ID":5554349,"CreatedAt":"2026-07-02T02:11:27.934456424Z","UpdatedAt":"2026-07-04T17:54:59.62573241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.01216","arxiv_id":"2607.01216","title":"Query Complexity of Hypergraph Connectivity and Learnability using CUT Oracles","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.","short_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...","url_abs":"https://arxiv.org/abs/2607.01216","url_pdf":"https://arxiv.org/pdf/2607.01216v1","authors":"[\"Deeparnab Chakrabarty\",\"Hang Liao\"]","published":"2026-07-01T17:54:03Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}