Reconstructing weighted graphs with minimal query complexity

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(m log n/log m) additive queries. This solves the open problem in [S. Choi, J.H. Kim, Optimal query complexity bounds for finding graphs, in: STOC, 2008, pp. 749-758]. Choi and Kim's proof holds for m >= (log n)(alpha) for a sufficiently large constant alpha and uses the graph theory. We use the algebraic approach for the problem. Our proof is simple and holds for any m. (C) 2011 Elsevier B.V. All rights reserved.