Optimal query complexity bounds for finding graphs

摘要

We consider the problem of finding an unknown graph by using queries with an additive property. This problem was partially motivated by DNA shotgun sequencing and linkage discovery problems of artificial intelligence.Given a graph, an additive query asks the number of edges in a set of vertices while a cross-additive query asks the number of edges crossing between two disjoint sets of vertices. The queries ask the sum of weights for weighted graphs.For a graph G with n vertices and at most m edges, we prove that there exists an algorithm to find the edges of G using queries of both types for all m. The bound is best possible up to a constant factor. For a weighted graph with a mild condition on weights, it is shown that queries are enough provided for a sufficiently large constant α, which is best possible up to a constant factor if for any constant .This settles, in particular, a conjecture of Grebinski [V. Grebinski, On the power of additive combinatorial search model, in: Proceedings of the 4th Annual International Conference on Computing and Combinatorics (COCOON 1998), Taipei, Taiwan, 1998, pp. 194–203] for finding an unweighted graph using additive queries. We also consider the problem of finding the Fourier coefficients of a certain class of pseudo-Boolean functions as well as a similar coin weighing problem.