10.4230/LIPICS.STACS.2010.2496
Bshouty, Nader H.
Nader H.
Bshouty
Mazzawi, Hanna
Hanna
Mazzawi
Optimal Query Complexity for Reconstructing Hypergraphs
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2010
Query complexity
hypergraphs
Marion, Jean-Yves
Jean-Yves
Marion
Schwentick, Thomas
Thomas
Schwentick
2010
2010-03-09
2010-03-09
2010-03-09
en
urn:nbn:de:0030-drops-24968
10.4230/LIPIcs.STACS.2010
978-3-939897-16-3
1868-8969
10.4230/LIPIcs.STACS.2010
LIPIcs, Volume 5, STACS 2010
27th International Symposium on Theoretical Aspects of Computer Science
2013
5
14
143
154
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Marion, Jean-Yves
Jean-Yves
Marion
Schwentick, Thomas
Thomas
Schwentick
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2010
5
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
313090 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 5, 27th International Symposium on Theoretical Aspects of Computer Science, pages 143-154