Reconstructing Weighted Graphs with Minimal Query Complexity
Abstract
In this paper we consider the problem of reconstructing a hidden weighted graph using additive queries. We prove the following: Let G be a weighted hidden graph with n vertices and m edges such that the weights on the edges are bounded between n ^− a and n ^ b for any positive constants a and b . For any m there exists a non-adaptive algorithm that finds the edges of the graph 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. Proc. of the 40th annual ACM Symposium on Theory of Computing , 749–758, 2008]. Choi and Kim’s proof holds for m ≥ (log n )^ α for a sufficiently large constant α and uses graph theory. We use the algebraic approach for the problem. Our proof is simple and holds for any m .
Cite
Text
Bshouty and Mazzawi. "Reconstructing Weighted Graphs with Minimal Query Complexity." International Conference on Algorithmic Learning Theory, 2009. doi:10.1007/978-3-642-04414-4_12Markdown
[Bshouty and Mazzawi. "Reconstructing Weighted Graphs with Minimal Query Complexity." International Conference on Algorithmic Learning Theory, 2009.](https://mlanthology.org/alt/2009/bshouty2009alt-reconstructing/) doi:10.1007/978-3-642-04414-4_12BibTeX
@inproceedings{bshouty2009alt-reconstructing,
title = {{Reconstructing Weighted Graphs with Minimal Query Complexity}},
author = {Bshouty, Nader H. and Mazzawi, Hanna},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2009},
pages = {97-109},
doi = {10.1007/978-3-642-04414-4_12},
url = {https://mlanthology.org/alt/2009/bshouty2009alt-reconstructing/}
}