Optimal reconstruction of graphs under the additive model

We study the problem of reconstructing unknown graphs under the additive co mbinatorial search model. The main result concerns the reconstruction of bo unded degree graphs, i.e., graphs with the degree of all vertices bounded b y a constant d. We show that such graphs can be reconstructed in O(dn) nona daptive queries, which matches the information-theoretic lower bound. The p roof is based on the technique of separating matrices. A central result her e is a new upper bound for a general class of separating matrices. As a par ticular case, we obtain a tight upper bound for the class of d-separating m atrices, which settles an open question stated by Lindstrom in [20]. Finall y, we consider several particular classes of graphs. We show how an optimal nonadaptive solution of O(n(2)/log n) queries for general graphs can be ob tained. We also prove that trees with unbounded vertex degree can be recons tructed in a linear number of queries by a nonadaptive algorithm.