Optimal Reconstruction of Graphs under the Additive Model

• DOI: 10.1007/s004530010033
• Publication Date: 2002-08-25T01:57:49Z
• Authors: V. Grebinski; G. Kucherov
• Keywords: graph reconstruction; algorithmes de pesage; algorithmes non-adaptatifs; [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH]; coin weighing; reconstruction de graphes; 0102 computer and information sciences; 01 natural sciences; [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH]; recherche combinatoire; nonadaptive algorithms; combinatorial search

We study the problem of reconstructing unknown graphs under the additive combinatorial search model. The main result concerns the reconstruction of {\em bounded degree} \/graphs, i.e.\ graphs with the degree of all vertices bounded by a constant $d$. We show that such graphs can be reconstructed in $O(dn)$ non--adaptive queries, which matches the information--theoretic lower bound. The proof is based on the technique of se\-pa\-rating matrices. A central result here is a new upper bound for a general class of separating matrices. As a particular case, we obtain a tight upper bound for the class of $d$--separating matrices, which settles an open question stated by Lindström in~\cite{Lindstrom75}. Finally, we consider several particular classes of graphs. We show how an optimal non--adaptive solution of $O(n^2/\log n)$ queries for general graphs can be obtained. We also prove that trees with unbounded vertex degree can be reconstructed in a linear number of queries by a non--adaptive algorithm.