DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.150

Query Complexity of Hypergraph Connectivity and Learnability Using CUT Oracles

Authors: Deeparnab Chakrabarty and Hang Liao

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

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 of [Liao and Chakrabarty, 2024]. Second, we demonstrate that the impossibility of exact learning depends on hyperedge parity. For hypergraphs all of whose hyperedges have even cardinality, 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 Õ_r(kn) queries. Finally, we bypass parity and rank constraints for linear hypergraphs, achieving a subquadratic Õ(kn^1.5) query complexity for k-connectivity. This significantly improves upon the general Õ(n²) bound derived via symmetric submodular function minimization.

Cite as

Deeparnab Chakrabarty and Hang Liao. Query Complexity of Hypergraph Connectivity and Learnability Using CUT Oracles. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 150:1-150:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chakrabarty_et_al:LIPIcs.ESA.2026.150,
  author =	{Chakrabarty, Deeparnab and Liao, Hang},
  title =	{{Query Complexity of Hypergraph Connectivity and Learnability Using CUT Oracles}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{150:1--150:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.150},
  URN =		{urn:nbn:de:0030-drops-272860},
  doi =		{10.4230/LIPIcs.ESA.2026.150},
  annote =	{Keywords: Query Complexity, CUT queries, hypergraph connectivity}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2024.16

Learning Partitions Using Rank Queries

Authors: Deeparnab Chakrabarty and Hang Liao

Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)

Abstract

We consider the problem of learning an unknown partition of an n element universe using rank queries. Such queries take as input a subset of the universe and return the number of parts of the partition it intersects. We give a simple O(n)-query, efficient, deterministic algorithm for this problem. We also generalize to give an O(n + klog r)-rank query algorithm for a general partition matroid where k is the number of parts and r is the rank of the matroid.

Cite as

Deeparnab Chakrabarty and Hang Liao. Learning Partitions Using Rank Queries. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chakrabarty_et_al:LIPIcs.FSTTCS.2024.16,
  author =	{Chakrabarty, Deeparnab and Liao, Hang},
  title =	{{Learning Partitions Using Rank Queries}},
  booktitle =	{44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-355-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{323},
  editor =	{Barman, Siddharth and Lasota, S{\l}awomir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.16},
  URN =		{urn:nbn:de:0030-drops-222051},
  doi =		{10.4230/LIPIcs.FSTTCS.2024.16},
  annote =	{Keywords: Query Complexity, Hypergraph Learning, Matroids}
}

Search Results

Documents authored by Liao, Hang

Query Complexity of Hypergraph Connectivity and Learnability Using CUT Oracles

Abstract

Cite as

Learning Partitions Using Rank Queries

Abstract

Cite as

Thanks for your feedback!

Could not send message