2026-07-22T14:19:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2496 2024-03-06T10:33:22Z ddc:004 open_access

Optimal Query Complexity for Reconstructing Hypergraphs Bshouty, Nader H. Mazzawi, Hanna Query complexity hypergraphs In this paper we consider the problem of reconstructing a hidden weighted hypergraph of constant rank using additive queries. We prove the following: Let $G$ be a weighted hidden hypergraph of constant rank with~$n$ vertices and $m$ hyperedges. For any $m$ there exists a non-adaptive algorithm that finds the edges of the graph and their weights using $$ O\left(\frac{m\log n}{\log m}\right) $$ additive queries. This solves the open problem in [S. Choi, J. H. Kim. Optimal Query Complexity Bounds for Finding Graphs. {\em STOC}, 749--758, 2008]. When the weights of the hypergraph are integers that are less than $O(poly(n^d/m))$ where $d$ is the rank of the hypergraph (and therefore for unweighted hypergraphs) there exists a non-adaptive algorithm that finds the edges of the graph and their weights using $$ O\left(\frac{m\log \frac{n^d}{m}}{\log m}\right). $$ additive queries. Using the information theoretic bound the above query complexities are tight. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nader H. Bshouty and Hanna Mazzawi 2010 Is Part Of LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2010.2496 urn:nbn:de:0030-drops-24968 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2496 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode