Bshouty, Nader H. ;
Mazzawi, Hanna
Optimal Query Complexity for Reconstructing Hypergraphs
Abstract
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 nonadaptive 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}, 749758, 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 nonadaptive
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.
BibTeX  Entry
@InProceedings{bshouty_et_al:LIPIcs:2010:2496,
author = {Nader H. Bshouty and Hanna Mazzawi},
title = {{Optimal Query Complexity for Reconstructing Hypergraphs}},
booktitle = {27th International Symposium on Theoretical Aspects of Computer Science},
pages = {143154},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897163},
ISSN = {18688969},
year = {2010},
volume = {5},
editor = {JeanYves Marion and Thomas Schwentick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2496},
URN = {urn:nbn:de:0030drops24968},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2496},
annote = {Keywords: Query complexity, hypergraphs}
}
Keywords: 

Query complexity, hypergraphs 
Seminar: 

27th International Symposium on Theoretical Aspects of Computer Science

Issue date: 

2010 
Date of publication: 

09.03.2010 