Reconstructing Random Graphs from Distance Queries

Kannan, Mathieu, and Zhou [22, 30] presented a reconstruction algorithm that uses $\tilde{O}(n^{3/2})$ distance queries for bounded degree graphs. They also proved an information–theoretic lower bound $\mathrm{\Omega }(n\log n/\log \log n)$ for trees with maximum degree 3 and asked whether $\tilde{O}(n)$ is achievable for all bounded degree graphs. Tight results for certain families of bounded degree graphs – trees, chordal graphs, and graphs with bounded treelength – were recently obtained by Bastide and Groenland in [4]. In particular, they proved that for every $\mathrm{\Delta }\ge 3$, any randomised algorithm requires $\mathrm{\Omega }(n\log n)$ queries to reconstruct $n$-vertex trees of maximum degree $\mathrm{\Delta }$ for a certain sequence of sizes of trees, which is tight since there exists a deterministic algorithm to reconstruct such trees using $O(n\log n)$ queries. In [31], Mathieu and Zhou answered the question from [22] for random $d$-regular graphs with constant $d$: whp $n{\ln }^{2}n$ distance queries is enough to reconstruct a uniformly random $d$-regular graph.

A modified version of the problem where the hidden graph is a tree and it is only allowed to query pairs of leaves (that are known) comes from biology: it serves as a model of reconstructing evolutionary (phylogenetic) trees and was introduced by Waterman, Smith, Singh, and Beyer [43]. This problem is well studied: lower bounds on query complexity for deterministic and randomised algorithms were obtained in [25] and [4] respectively, and upper bounds were investigated in [11, 23, 25, 27].

Other types of query oracles explored in the literature include all-shortest-path, all-distances, and shortest-path queries. The first two oracles answer all shortest paths [5, 38] and all distances [5, 14] from a queried vertex respectively. The shortest-path oracle answers a shortest path between a queried pair of vertices [22, 37]. Erlebach, Hall, and Mihal’ák [15] studied reconstruction of $G(n,p)$ from all-shortest-path queries for $p=\mathrm{const}$ and $p=n^{-1+\epsilon }$ for specific $\epsilon >0$.

Mathieu and Zhou [31] also showed that their construction of the set of distance queries can be used to get an upper bound for the metric dimension of random $d$-regular graphs. Let us recall that the metric dimension $\beta (G)$ of a graph $G$ is the minimum cardinality of $S\subset V(G)$ such that all vertices of $G$ have different vectors of distances to the vertices from $S$. Such resolving sets $S$ or their variants were used, in particular, to label canonically vertices of random graphs [3, 26]. The metric dimension of $G(n,p)$ was studied by Bollobás, Mitsche, and Prałat in [10]. In particular, they proved that the metric dimension of $G(n,p)$ undergoes the following “zigzag” behaviour: if $p=n^{-\alpha }$, then ${\log }_n\beta (G(n,p))=1-(1-\alpha )\lfloor 1/(1-\alpha )\rfloor$ whp; see also [36] for related results. Although in our proof of the upper bound for the distance query complexity of $G(n,p)$ we use a resolving set whose size is far from being optimal, as we show below the “jumps” of the metric dimension and of the query complexity are synchronous – both happen around $n^{-k/(k+1)}$, $k\in {\mathbb{Z}}_{>0}$.

As follows from the next result, the query complexity drops for the first time when $p$ passes a threshold $n^{-1/2+o(1)}$ on its way down. More generally, we prove that, for every integer constant $k\ge 1$, as soon as $p$ passes a threshold $n^{-(k+1)/(k+2)+o(1)}$, the query complexity drops by a factor of $\mathrm{\Theta }(np)$.

We prove Theorem 1 in Section 3.

Theorem 2 is proven in Section 5. Let us emphasise that its proof is based on an explicit argument which is more efficient than the usual information-theoretic approach: we show a lower bound on the query complexity of a deterministic graph in terms of its diameter and maximum degree, see Claim 14. Unlike the information-theoretic approach, our approach allows to bound the query complexity of any given graph. So, it actually demonstrates that, when the number of queries is less than the bound, even knowing the input graph $G$ does not help choosing the optimal quering strategy – no matter which pairs of vertices are queried, there is always a graph $G^{\prime }\ne G$ with exactly the same answers.

Note that, for any $w_n\to \mathrm{\infty }$ as $n\to \mathrm{\infty }$ and any

the bounds in Theorem 1 and Theorem 2 differ by a constant factor, see Figure 1. So, roughly speaking (ignoring the constant factor) the query complexity in the interval (1) increases with $p$.

We also prove tight (up to a constant factor) bounds for “non-adaptive reconstructibility”. It turns out that if the set of queried pairs $𝒬$ is fixed, then both upper and lower bounds on the minimum $|𝒬|$ such that $G(n,p)$ is $𝒬$-reconstructable increase by a factor of $\log n$ when $p$ satisfies (1).

Theorem 3 is proven in Section 4.

Theorem 4 is proven in Section 6.

For simplicity of presentation, let us assume that $p=n^{-\alpha }$, where for some $k\in {\mathbb{Z}}_{>0}$. The crucial observation that allows to prove tight (up to a constant) upper bounds both for adaptive and non-adaptive query complexities is the following: if $\{v_1,x\}$ and $\{v_2,x\}$ are queried and $d(v_2,x)\ge d(v_1,x)+2$, then $v_1$ and $v_2$ are not adjacent.

Although whp the diameter of $G_n\sim G(n,p)$ equals $k+2$, for a sufficiently large fixed set $X\subset [n]$, every vertex $v\in [n]$ has a vertex from $X$ in its $k$-neighbourhood. Indeed, if $X$ has size $\mathrm{\Theta }\left(\frac{\ln n}{n^{k-1}{p}^k}\right)$, then the expected number of $k$-paths from a fixed vertex $v\in [n]$ to $X$ is $\mathrm{\Theta }(\ln n)$. Thus, using standard concentration inequalities, it is possible to overcome the union bound over the choice of $v\in [n]$ for $|X|=C\frac{\ln n}{n^{k-1}{p}^k}$ and $C$ sufficiently large. Actually, the following stronger property can be proved: whp for every $v_1,v_2\notin X$, there exists $x\in X$ such that $d_{G_n}(v_1,x)\le k$ while $d_{G_n\setminus \{v_1,v_2\}}(v_2,x)\ge k+2$, where $G_n\setminus \{v_1,v_2\}$ is a spanning subgraph of $G_n$ that is obtained by excluding the edge $\{v_1,v_2\}$. Thus, as soon as all pairs of vertices with at least one vertex in $X$ are queried, all the remaining adjacencies are reconstructible whp. Indeed, for non-adjacent $v_1,v_2$, there exists $x$ such that $d(v_1,x)\le k$ and $d(v_2,x)\ge k+2$, thus we may reconstruct all non-adjacencies. All the other pairs of vertices must be adjacent since otherwise if we could exclude, say, the edge $\{v_1,v_2\}$, then there is an $x\in X$ such that $d(v_2,x)\le k+1$ while, in the corrupted graph, the distance between $v_2$ and $x$ would be at least $k+2$. This proves Theorem 3, see details in Section 4. A counterpart of this very simple algorithm was employed by Mathieu and Zhou in [31], who showed that it allows typically to reconstruct random regular graphs with $(1+o(1))n{\ln }^{2}n$ queries, which is tight, up to a ${(\log n)}^{1+o(1)}$-factor.

The proof of Theorem 1 in Section 3 is based on similar ideas but also utilises the possibility of updating queries adaptively: indeed, instead of querying all pairs $\{x\in X,v\in [n]\}$ simultaneously, we may split the set $X$ into $\nu =\mathrm{\Theta }(\log n)$ equal parts $X_1,\mathrm{\dots },X_{\nu }$ and then, for every $i=1,\mathrm{\dots },\nu$, query a pair $\{x\in X_i,v\in [n]\}$ only if $v$ has not yet been excluded from the consideration. A vertex $v$ is excluded from the consideration at time $i$, if it has sufficiently many (at least $M$ for some large enough constant $M$) vertices in the intersection of its $k$-neighbourhood with $X_1\cup \mathrm{\dots }\cup X_i$. This allows to query the desired number of pairs whp. In order to complete the proof, it remains to observe that whp there are no $v_1,v_2$ that have $M$ different vertices $x\in X$ so that $d_{G_n\setminus \{v_1,v_2\}}(v_1,x)\le k$ and $d_{G_n\setminus \{v_1,v_2\}}(v_2,x)\le k+1$. This would imply the existence of a good $x\in X$ as in the proof of Theorem 3 for any pair $\{v_1,v_2\}$.

Proofs of both lower bounds in Theorem 2 and Theorem 4 use the notion of an undetectable pair in a graph $G$ having diameter $d\ge 3$ with a set of queried pairs $𝒬\subset \left(\genfrac{}{}{0pt}{}{V(G)}{2}\right)$: a pair of vertices $\{u_1,u_2\}$ is undetectable if $\{u_1,u_2\}\notin 𝒬\cup E(G)$ and there is no “path” $u_1{w}_1\mathrm{\dots }{w}_{\mathrm{\ell }}{u}_2$ in $G$, where $\mathrm{\ell }\le d-2$, such that $\mathrm{\ell }$ of its “edges” are actual edges of $G$, and the one remaining pair of consecutive vertices belongs to $𝒬$. It is easy to see that if $G$ has at least one undetectable pair, then it is not reconstructible from $𝒬$ since the addition of the edge $\{u_1,u_2\}$ does not change answers to queries. When $𝒬$ is small, then a simple counting proof shows that there are undetectable pairs in $G_n$ whp. This proves Theorem 2, see details in Section 5.

In order to improve the lower bound by a factor of $\log n$ for the “non-adaptive reconstructibility” (Theorem 4), we first refine the notion of undetectability, and then introduce a randomised algorithm that finds an undetectable pair (in the refined sense) in $G_n$ whp. Let us call a pair of vertices $\{u_1,u_2\}$ $\mathrm{\ell }$-undetectable in $G$, if $\{u_1,u_2\}\notin 𝒬\cup E(G)$ and there is no “path” $u_1{w}_1\mathrm{\dots }{w}_{\mathrm{\ell }}{u}_2$ in $G$ such that $\mathrm{\ell }$ of its “edges” are actual edges of $G$, the one remaining pair of consecutive vertices belongs to $𝒬$, and the distance between the two vertices in this pair is at least $\mathrm{\ell }+2$. Though the refined notion is weaker, it still allows to prove non-reconstructibility: if $G$ has diameter $d$ and has a pair which is $\mathrm{\ell }$-undetectable for all $\mathrm{\ell }\le d-2$, then $G$ is not $𝒬$-reconstructible. Notice that, to decide whether a given pair $\{u_1,u_2\}$ is undetectable, it is sufficient to know only the edges induced by the union of $k$-neighbourhoods of $u_1$ and $u_2$. In Section 6, we show that the following algorithm finds an undetectable pair whp: at every step, choose a pair of vertices $\{u_1,u_2\}$ uniformly at random from the set of unconsidered vertices, consider all vertices in $k$-neighbourhoods of $u_1,u_2$, and check whether $\{u_1,u_2\}$ is $\mathrm{\ell }$-undetectable for all $\mathrm{\ell }\le k$.

The rest of the paper is organised as follows. In Section 2 we recall properties of random graphs that we will use in our proofs: namely, asymptotic behaviour of sizes of balls of small radii and the diameter. Proofs of upper bounds – Theorem 1 and Theorem 3 – appear in Sections 3 and 4 respectively. In Sections 5 and 6 we prove the lower bounds, Theorems 2 and 4 respectively. Finally, in Section 7 we raise several natural questions that we leave unanswered.