Graph Reconstruction via MIS Queries

We give a randomized algorithm for reconstructing an $n$-vertex graph with maximum degree $\mathrm{\Delta }$ that uses $O({\mathrm{\Delta }}^2\log n)$ non-adaptive queries and succeeds with high probability¹¹1As it is standard, we say that an event related to the input graph $G=(V,E)$ occurs with high probability if the probability is $1-\frac{1}{\mathrm{poly}n}$, where $n=|V|$. (Theorem 1). This result shows that, for the class of graphs of maximum degree $\mathrm{\Delta }$, MIS queries are stronger than IS queries since an information-theoretic lower bound similar to the one given in [7] shows that $\mathrm{\Omega }(\mathrm{\Delta }n\log (\frac{n}{\mathrm{\Delta }}))$ IS queries are needed to reconstruct a graph with maximum degree $\mathrm{\Delta }$ (Corollary 16 in Appendix A). Observe that, for the class of constant degree graphs, $O(\log n)$ MIS queries are sufficient, but $\mathrm{\Omega }(n\log n)$ IS queries are necessary.

We also investigate whether randomization is necessary to obtain algorithms with low query complexity. Using the probabilistic method, we show that there exists a non-adaptive deterministic query algorithm that executes $O({\mathrm{\Delta }}^3\log (\frac{n}{\mathrm{\Delta }}))$ queries (Corollary 7).

Our non-adaptive randomized and deterministic algorithms assume that the maximum degree $\mathrm{\Delta }$ is known in advance. This cannot be avoided since, as proved in Theorem 14, any algorithm that executes $o(n^2)$ queries cannot solve all instances with $\mathrm{\Delta }=\mathrm{\Theta }(n)$. We show that the non-adaptive algorithms above can be turned into adaptive algorithms with query complexities that are by at most a constant factor larger. These adaptive algorithms do not require any information about $\mathrm{\Delta }$ in order to operate and only require $O(\log \mathrm{\Delta })$ rounds of adaptivity (Corollary 9).

We give lower bounds on the number of queries required by both non-adaptive deterministic algorithms and adaptive randomized algorithms.

First, we show that every non-adaptive deterministic query algorithm requires $\mathrm{\Omega }({\mathrm{\Delta }}^3/{\log }^2\mathrm{\Delta })$ queries (Corollary 12), which renders our deterministic algorithm optimal, up to poly-logarithmic factors. This result together with our non-adaptive randomized algorithm (Theorem 1) establishes a separation result between non-adaptive randomized and non-adaptive deterministic algorithms since our randomized algorithm only requires $O({\mathrm{\Delta }}^2\log n)$ queries.

Next, we show that every adaptive randomized query algorithm requires $\mathrm{\Omega }(\log n)$ queries, even if the input graph is guaranteed to be an $n$-vertex cycle (Theorem 13). Furthermore, we show that every adaptive randomized query algorithm requires $\mathrm{\Omega }({\mathrm{\Delta }}^2)$ queries, for any $\mathrm{\Delta }$ (Theorem 14). These lower bounds show that the number of queries executed by our randomized algorithm is optimal, up to a logarithmic factor, and that the logarithmic dependency on $n$ cannot be avoided entirely.

For an overview of our results, see Table 1.

The starting point for all our algorithms is an algorithm by Angluin and Chen [7] for GR that uses IS queries. Our randomized algorithm is in fact identical to their algorithm, up to the use of a different sampling probability. It works as follows:

The key idea is to learn all the non-edges rather than all the edges of the input graph. To this end, we sample sufficiently many random vertex-induced subgraphs $G[V_i]\subseteq G$, for integers $i$, such that, for every non-edge $uv\in (V\times V)\setminus E(G)$, the probability that both $u$ and $v$ are contained in $V_i$ and are isolated in $G[V_i]$ is $\mathrm{\Theta }(\frac{1}{{\mathrm{\Delta }}^2})$. This is achieved by including every vertex in $V_i$ with probability $\frac{1}{\mathrm{\Delta }+1}$. Observe that when $u$ and $v$ are isolated in $G[V_i]$ then the oracle necessarily needs to include both $u$ and $v$ in the returned maximal independent set. The returned maximal independent set therefore serves as a witness that proves that the potential edge $uv$ is not contained in the input graph. We then argue that, after repeating this process $O({\mathrm{\Delta }}^2\log n)$ times, we have learnt all non-edges with high probability, which allows us to identify the edges of the input graph by complementing the set of non-edges.

Angluin and Chen use this idea in the context of IS queries for graphs with maximum degree $\mathrm{\Delta }$, where the significantly lower inclusion probability of each vertex into each sample $V_i$ of $\frac{1}{\sqrt{\mathrm{\Delta }n}}$ needs to be used.

Our deterministic algorithm is built on a similar idea. We show that, when taking $\mathrm{\ell }=\mathrm{\Theta }({\mathrm{\Delta }}^3\log (\frac{n}{\mathrm{\Delta }}))$ random subsets $V_1,\mathrm{\dots },V_{\mathrm{\ell }}\subseteq V$ as above, i.e., by inserting every vertex $v\in V$ into any subset $V_i$ with probability $\frac{1}{\mathrm{\Delta }+1}$, then, for any tuple $(\{u,v\},\{w_1,\mathrm{\dots },w_{2\mathrm{\Delta }}\})$ of $2\mathrm{\Delta }+2$ disjoint vertices, which we also refer to as a witness, there exists a set $V_i$ such that $u,v\in V_i$ but $w_1,\mathrm{\dots },w_{2\mathrm{\Delta }}\notin V_i$ with positive probability. Since this event happens with non-zero probability, such a family of subsets $V_1,\mathrm{\dots },V_{\mathrm{\ell }}$ exists. Our deterministic algorithm then queries all of these subsets ${(V_i)}_{1\le i\le \mathrm{\ell }}$. We now claim that our algorithm learns every non-edge $uv\in (V\times V)\setminus E$: We know that there exists a set $V_i$ such that $u,v\in V_i$ but $(\mathrm{\Gamma }(v)\cup \mathrm{\Gamma }(u))\cap V_i=\mathrm{\varnothing }$ since $|\mathrm{\Gamma }(v)\cup \mathrm{\Gamma }(u)|\le 2\mathrm{\Delta }$ holds. The vertices $u$ and $v$ are thus isolated in $G[V_i]$ and therefore necessarily reported in the oracle answer, which provides a proof to the algorithm that the edge $uv$ is not contained in the input graph.

Both our non-adaptive randomized and deterministic algorithms require advanced knowledge of $\mathrm{\Delta }$, which, as previously argued, is unavoidable. We turn both of these algorithms into adaptive algorithms that require only $O(\log \mathrm{\Delta })$ rounds of adaptivity and whose total number of queries executed is only by a constant factor larger. This is achieved by successively running our algorithms for the guesses $D=1,2,4,8,\mathrm{\dots }$ for the maximum degree $\mathrm{\Delta }$ until a final guess is used, in which case it is easy to see that the graph is correctly reconstructed. While this is a standard doubling argument, the non-trivial part of the argument is to identify when the condition is reached since $\mathrm{\Delta }$ is now unknown. Denoting by $F$ the set of non-edges learnt by the execution of one of our algorithms when invoked on the current guess $D$, we show that if the maximum degree in the graph spanned by the edges $(V\times V)\setminus F$ is at least $D$ then we have indeed learnt all the non-edge of the input graph, and thus also reconstructed the graph.

We first discuss our $\mathrm{\Omega }({\mathrm{\Delta }}^3/{\log }^2\mathrm{\Delta })$ lower bound for deterministic non-adaptive algorithms. Witnesses, i.e., tuples $(\{u,v\},\{w_1,\mathrm{\dots },w_{2\mathrm{\Delta }}\})$ of $2\mathrm{\Delta }+2$ disjoint vertices, play a key role in our lower bound argument. We argue that any deterministic non-adaptive query algorithm must be such that, for every witness $(\{u,v\},\{w_1,\mathrm{\dots },w_{2\mathrm{\Delta }}\})$ of disjoint $2\mathrm{\Delta }+2$ vertices, there exists a query $Q_i$ such that $u,v\in Q_i$ and $\{w_1,\mathrm{\dots },w_{2\mathrm{\Delta }}\}\cap Q_i=\mathrm{\varnothing }$. We call a set of $\mathrm{\ell }$ queries that fulfills this property a $\mathrm{\Delta }$-Query-Scheme of size $\mathrm{\ell }$. To see that the previous property is true, for the sake of a contradiction, suppose that this is not the case and there exists a witness $(\{u,v\},\{w_1,\mathrm{\dots },w_{2\mathrm{\Delta }}\})$ that does not fulfill these properties, i.e., whenever $u,v$ is included in a query then at least one of the vertices $w_1,\mathrm{\dots },w_{2\mathrm{\Delta }}$ is included in this query as well. We claim that the two graphs $G_1$ and $G_2$, where, in both graphs, $w_1,\mathrm{\dots },w_{\mathrm{\Delta }}$ are incident on $u$ and $w_{\mathrm{\Delta }+1},\mathrm{\dots },w_{2\mathrm{\Delta }}$ are incident on $v$, and $uv$ is an edge in $G_1$ but not in $G_2$ cannot be distinguished²²2This construction generates a maximum degree of $\mathrm{\Delta }+1$ in $G_1$, which is technically not allowed since we consider algorithms that run on graphs of maximum degree $\mathrm{\Delta }$. To circumvent this issue, in our actual proof we therefore relate algorithms that operate on maximum degree $\mathrm{\Delta }$ graphs to $(\mathrm{\Delta }-1)$-Query-Schemes.. Indeed, we claim that, for any query executed, the oracle can always report an independent set that contains at most one of the two vertices $u,v$, even on graph $G_2$. This is because whenever $u,v$ is included in a query then at least one of the vertices ${(w_i)}_{1\le i\le 2\mathrm{\Delta }}$ is also included in this query. The oracle can therefore include $w_i$ in the oracle answer, which implies that at most one of $u$ and $v$ will also be included. Both graphs $G_1$ and $G_2$ are therefore consistent with all oracle answers and are thus indistinguishable, a contradiction.

Our task, therefore, is to prove that any $\mathrm{\Delta }$-Query-Scheme must be of size at least $\mathrm{\Omega }({\mathrm{\Delta }}^3/{\log }^2\mathrm{\Delta })$. We achieve this by combining two separate arguments that address small queries, i.e., queries $V_i\subseteq V$ of size at most $|V_i|\le t:=C\cdot \frac{n\ln (\mathrm{\Delta })}{\mathrm{\Delta }}$ and large queries of size larger than $t$, respectively: For any pair of vertices $\{u,v\}$, small queries are such that they cover many witnesses $(\{u,v\},\{w_1,\mathrm{\dots },w_{2\mathrm{\Delta }}\})$, for many different vertices ${(w_i)}_{1\le i\le 2\mathrm{\Delta }}$, since the vertices ${(w_i)}_{1\le i\le 2\mathrm{\Delta }}$ are chosen from $V\setminus V_i$, however, on average, vertex pairs $\{u,v\}$ cannot be included in many small queries (at most $\left(\genfrac{}{}{0pt}{}{t}{2}\right)$). In contrast, vertex pairs $\{u,v\}$ can be included in many large queries, however, those queries do not cover many witnesses $(\{u,v\},\{w_1,\mathrm{\dots },w_{2\mathrm{\Delta }}\})$, for vertices ${(w_i)}_{1\le i\le 2\mathrm{\Delta }}$. We obtain our result by combining these observations, see the proof of Lemma 10.

Next, we discuss our $\mathrm{\Omega }(\log n)$ queries lower bound for adaptive randomized algorithms on $n$-vertex cycles. Observe that, in an $n$-vertex cycle $G=(V,E)$, every pair of vertices $u,v\in V$ is such that $\mathrm{\Gamma }(u)\ne \mathrm{\Gamma }(v)$. Hence, for a query algorithm to be able to distinguish any two vertices of the input graph, the algorithm is required to obtain oracle answer maximal independent sets such that $u$ and $v$ do not behave the same in all returned independent sets. We show that $\mathrm{\Omega }(\log n)$ queries are needed to distinguish between all the vertices. Our argument is based on the observation that, given a set of vertices $U\subseteq V$ that are so far indistinguishable and a query set $V_i\subseteq V$, the returned maximal independent set $I_i$ only allows us to differentiate between the vertices of $U$ that are not queried, queried and contained in $I_i$, and queried and not contained in $I_i$. Every query thus allows us to partition any set of vertices that is still indistinguishable into only three subsets, which implies that $\mathrm{\Omega }({\log }_{3}n)=\mathrm{\Omega }(\log n)$ queries are needed to distinguish between all the vertices.

Last, we discuss our $\mathrm{\Omega }({\mathrm{\Delta }}^2)$ queries lower bound for arbitrary randomized adaptive algorithms. We work with the family of graphs $𝒢$ obtained from the family of all balanced bipartite graphs $G=(A,B,E)$ with $|A|=|B|=\mathrm{\Theta }(\mathrm{\Delta })$, where the two bipartitions $A$ and $B$ are turned into two separate cliques. Observe that each such graph has a maximum independent set size of $2$. We now claim that, for every non-edge $ab\in (V\times V)\setminus E(G)$ in the input graph $G$, there must exist an independent set $I_i$ returned by the oracle such that $I_i=\{a,b\}$. This needs to be the case since otherwise the algorithm cannot distinguish between $G$ and the graph $G^{\prime }=G\cup \{ab\}$, i.e., $G$ with the edge $ab$ added, since all query responses are then consistent with both $G$ and $G^{\prime }$. However, since at most one non-edge can be learnt per query, and $𝒢$ contains many graphs with $\mathrm{\Omega }({\mathrm{\Delta }}^2)$ non-edges, the result follows. Our actual lower bound is proved for randomized algorithms via an application of Yao’s Lemma, which makes the argument slightly more complicated.

Let $G=(V,E)$ denote the input graph, $\mathrm{\Delta }$ the maximum degree, and let $\overline{E}=(V\times V)\setminus E$ denote the set of non-edges. We will prove that, with high probability, every non-edge can be identified by the algorithm in that, for a non-edge $uv\in \overline{E}$, there exists an independent set $I_i$ such that $\{u,v\}\in I_i$ with high probability.

Consider thus any non-edge $uv\in \overline{E}$. Then, for every $i$, the probability that both $u$ and $v$ are reported in independent set $I_i$ is at least:

since both $u$ and $v$ need to be included in a maximal independent set if they are isolated vertices in $G[V_i]$.

Next, observe that the events “$u,v\in V_i$” and “$(\mathrm{\Gamma }(u)\cup \mathrm{\Gamma }(v))\cap V_i=\mathrm{\varnothing }$” are independent since $u$ and $v$ are not adjacent and are thus not contained in $\mathrm{\Gamma }(u)\cup \mathrm{\Gamma }(v)$. Furthermore, observe that $|\mathrm{\Gamma }(u)\cup \mathrm{\Gamma }(v)|\le 2\mathrm{\Delta }$. Then:

where we used the bound $1-x\ge e^{-\frac{x}{1-x}}$, which holds for every .

Next, we compute the probability that both endpoints of the non-edge $uv$ are never reported together:

where we used the inequality $1+x\le \exp (x)$, and the last inequality holds when $C$ is chosen to be large enough.

By the union bound, the probability that the endpoints of at least one of the $O(n^2)$ non-edges are not reported in any independent set $I_i$ is therefore at most $\frac{1}{n}$, which completes the proof. $◀$

We use the bound $\left(\genfrac{}{}{0pt}{}{a}{b}\right)\le {\left(e\cdot \frac{a}{b}\right)}^b$ and obtain:

$◀$

We show in Lemma 5 that a $\mathrm{\Delta }$-Query-Scheme of size $\mathrm{\ell }$ immediately yields a non-adaptive deterministic query algorithm for GR for graphs of maximum degree $\mathrm{\Delta }$ that executes $\mathrm{\ell }$ queries. Our task is thus to design a $\mathrm{\Delta }$-Query-Scheme of small size, which we do in the proof of Lemma 6.

Let $G=(V,E)$ be the input graph, and let $𝒬$ be a $\mathrm{\Delta }$-Query-Scheme of size $\mathrm{\ell }$. The algorithm executes every query $Q_i\in 𝒬$. Let $I_i$ denote the query answer to $Q_i$.

We now claim that, for every non-edge $uv\in (V\times V)\setminus E$ in the input graph, there exists an independent set $I_i$ such that $u,v\in I_i$. To see this, denote by $w_1,\mathrm{\dots },w_{\mathrm{deg}(u)}$ the neighbours of $u$ in $G$ and by $w_{\mathrm{\Delta }+1},\mathrm{\dots },w_{\mathrm{\Delta }+\mathrm{deg}(v)}$ the neighbours of $v$ in $G$. Then, since $𝒬$ is a $\mathrm{\Delta }$-Query-Scheme, there exists a query $Q_i$ such that $u,v\in I_i$, but none of $u$’s and $v$’s neighbours are included. Hence, both $u$ and $v$ are necessarily included in $I_i$ and the algorithm therefore observes a witness that proves that the edge $uv$ does not exist in the input graph.

Since the argument applies to every non-edge, the algorithm learns all non-edges of the input graph and thus also learns all of the input graph’s edges by complementing the set of non-edges. $◀$

For an integer $\mathrm{\ell }$ whose value we will determine later, let $𝒬=\{Q_1,Q_2,\mathrm{\dots },Q_{\mathrm{\ell }}\}$ be such that, for every $i$, $Q_i\subseteq V$ is the subset of $V$ obtained by including every vertex with probability $\frac{1}{\mathrm{\Delta }+1}$. We use the probabilistic method and prove that $𝒬$ is a $\mathrm{\Delta }$-Query-Scheme with positive probability, which in turn implies that such a scheme exists.

To this end, let $u,v,w_1\mathrm{\dots },w_{2\mathrm{\Delta }}\in V$ be distinct vertices. Then, for any $i$, we obtain (the derivation is identical to Inequality 1 and therefore not repeated here)

Furthermore, the probability that there does not exist a query $Q_i$, for any $i\in [\mathrm{\ell }]$, such that $u,v\in Q_i$ and $w_1,\mathrm{\dots },w_{2\mathrm{\Delta }}\notin Q_i$ is at most:

Hence, by the union bound over all witnesses $u,v,w_1,\mathrm{\dots },w_{2\mathrm{\Delta }}$ (see Lemma 3), the probability that there exists a witness that is not considered by the $\mathrm{\Delta }$-Query-Scheme is at most:

For this probability to be strictly below $1$, it is enough to set

which in turn implies that such a scheme exists. $◀$

Combining Lemma 5 and Lemma 6, we obtain the main result of this section.

Let $G=(V,E)$ denote the input graph and $\mathrm{\Delta }$ the maximum degree.

We will argue that when exiting the last iteration of the while loop of the algorithm, the inequalities

hold. The lower bound $\mathrm{\Delta }\le D$ establishes correctness since the last run of $𝒜$ is executed with a guess $\mathrm{\Delta }\le D$, which implies that all non-edges are correctly identified. The upper bound is required in order to bound the query complexity of the algorithm.

We first argue the lower bound in Inequality 2. Observe that, in any iteration of the loop, $E^{\prime }\supseteq E$ holds since $F$ is a subset of the non-edges and $E^{\prime }=(V\times V)\setminus F$. Thus, we have $\mathrm{\Delta }(E^{\prime })\ge \mathrm{\Delta }(E)=\mathrm{\Delta }$. When exiting the last iteration of the algorithm, we have $\mathrm{\Delta }(E^{\prime })\le D$ since otherwise this would not be the last iteration of the algorithm. Combining these two inequalities yields $\mathrm{\Delta }\le D$.

Regarding the upper bound, we have just proved that, when exiting the last iteration, $\mathrm{\Delta }\le D$ holds. It is then also clear that a run with is executed since the guess $D$ is doubled in each iteration. We claim that this run with is indeed the last iteration of the algorithm. Indeed, in this iteration, all non-edges $F$ are correctly identified since $D\ge \mathrm{\Delta }$, which implies that $E^{\prime }$ constitutes the edge set $E$ of the input graph. This further implies that $\mathrm{\Delta }(E^{\prime })=\mathrm{\Delta }$. The condition in the while loop then ensures that this is indeed the last iteration of the algorithm.

Last, regarding the runtime of the algorithm, let $D^{\prime }=2^i$ be the guess used in the last iteration. We then have that . Then, under the assumption that $R(D)=\mathrm{\Omega }(D)$, we have:

which establishes the query complexity of the algorithm. Last, since the while loop is executed $O(\log \mathrm{\Delta })$ times, the algorithm requires only $O(\log \mathrm{\Delta })$ rounds of adaptivity. $◀$

The previous lemma together with our randomized and deterministic algorithms from the previous sections yield the following corollary.

Let $C$ be a suitably large constant, and suppose that there exists a $\mathrm{\Delta }$-Query-Scheme $𝒬$ of size $\mathrm{\ell }=\frac{1}{6\cdot C^2}\cdot \frac{{\mathrm{\Delta }}^3}{{\ln }^2(\mathrm{\Delta })}$. We will show by contradiction that a $\mathrm{\Delta }$-Query-Scheme of this size does not exist. Furthermore, we define a relevant query size threshold $t$ by $t:=C\cdot \frac{n\ln (\mathrm{\Delta })}{\mathrm{\Delta }}$.

Given $𝒬$, we will first argue that there exists a pair of disjoint vertices $x,y\in V$ such that there is no query $Q\in 𝒬$ with $Q=\{x,y\}$, and there are at most $\mathrm{\Delta }/2$ queries of size at most $t$ that contain both $x,y$. Then, once we have established that such a pair $\{x,y\}$ exists then we use the probabilistic method to show that there exist $2\mathrm{\Delta }$ disjoint vertices $w_1,\mathrm{\dots },w_{2\mathrm{\Delta }}$ different to $x,y$ such that the witness $(\{x,y\},\{w_1,\mathrm{\dots },w_{2\mathrm{\Delta }}\}$ is not considered in $𝒬$, a contradiction to the fact that $𝒬$ is a $\mathrm{\Delta }$-Query-Scheme. This implies that a query scheme of size $\mathrm{\ell }$ cannot exist.

Denote by $𝒳$ the set of subsets of $V$ of size $2$, i.e., $𝒳=\{\{u,v\}:u,v\in V,u\ne v\}$, where $V$ denotes the set of $n$ vertices of the input graph, and observe that $|𝒳|=\left(\genfrac{}{}{0pt}{}{n}{2}\right)$.

First, observe that at most $\mathrm{\ell }$ queries in $𝒬$ are of size exactly $2$. Hence, as long as $\mathrm{\ell }\le \left(\genfrac{}{}{0pt}{}{n}{2}\right)/10$, at most a $(1/10)$-fraction of $𝒳$ is part of queries of size $2$. Observe that, since the statement of the lemma assumes that $\mathrm{\Delta }\le n^{2/3}$, we have

where we assumed that $C$ is large enough, and the last inequality holds for every $n\ge 2$. Observe that a query $Q=\{u,v\}$ of size $2$ immediately considers all witnesses of the form $(\{u,v\},\{w_1,\mathrm{\dots },w_{2\mathrm{\Delta }}\})$, for any vertices ${(w_i)}_{1\le i\le 2\mathrm{\Delta }}$. The previous argument shows that this can happen for at most a $(1/10)$-fraction of pairs $\{u,v\}\in 𝒳$.

Next, we argue that at least a $(1/4)$-fraction of the pairs $\{u,v\}\in 𝒳$ are such that $\{u,v\}$ is contained in at most $\frac{1}{2}\mathrm{\Delta }$ queries of size at most $t$ in $𝒬$. To this end, observe that any query of size at most $t$ contains at most $\left(\genfrac{}{}{0pt}{}{t}{2}\right)\le t^2$ distinct pairs $\{u,v\}$, and since there are overall $\mathrm{\ell }$ queries, at most

pairs appear overall in all queries of size at most $t$. If less than a $(1/4)$-fraction of pairs $\{u,v\}$ were contained in at most $\frac{1}{2}\mathrm{\Delta }$ queries of size at most $t$ in $𝒬$, then at least a $(3/4)$-fraction of pairs were contained in more than $\frac{1}{2}\mathrm{\Delta }$ queries of size at most $t$. But this implies that the following inequality must hold:

This inequality, however, does not hold for $n\ge 10$, a contradiction. Hence, we have proved that at least a $(1/4)$-fraction of pairs $\{u,v\}\in 𝒳$ are such that $\{u,v\}$ is contained in at most $\frac{1}{2}\mathrm{\Delta }$ queries of size at most $t$ in $𝒬$.

Consider thus a pair $\{u,v\}\in 𝒳$ that is included in at most $\mathrm{\Delta }/2$ queries of size at most $t$, and that is not included in a query of size $2$. The arguments above ensure that such a pair exists. Denote by $Q_1,\mathrm{\dots },Q_k$ the set of queries that contain both $u$ and $v$, and suppose that $Q_1,\mathrm{\dots },Q_j$ are the queries of size at most $t$ (which implies $j\le \mathrm{\Delta }/2$). We now claim that there is a witness $W=(\{u,v\},\{w_1,\mathrm{\dots },w_{2\mathrm{\Delta }}\})$, for some vertices ${(w_i)}_{1\le i\le 2\mathrm{\Delta }}$, that is not considered by the queries $Q_1,\mathrm{\dots },Q_k$, contradicting the assumption that $𝒬$ is a $\mathrm{\Delta }$-Query-Scheme, which then completes the proof.

The witness is constructed as follows. For $1\le i\le j$, let ${\tilde{w}}_i\in Q_i\setminus \{u,v\}$ be any element. Recall that $\{u,v\}$ is not contained in any query of size exactly $2$, hence, ${\tilde{w}}_i$ is well-defined. Furthermore, let $\tilde{W}=\{{\tilde{w}}_1,{\tilde{w}}_2,\mathrm{\dots },{\tilde{w}}_j\}$. We observe that the elements ${({\tilde{w}}_i)}_{1\le i\le j}$ are not necessarily disjoint, and, hence, $|\tilde{W}|\in \{1,\mathrm{\dots },j\}$. Next, let $R\subseteq V\setminus \left(\{u,v\}\cup \tilde{W}\right)$ be a random subset of size $2\mathrm{\Delta }-|\tilde{W}|$. Then, our witness $W$ is obtained as $W=\{\{u,v\},\tilde{W}\cup R\}$, and we will prove in the following that, with positive probability, this witness is indeed not considered by $𝒬$. This implies that there exists a witness that is not considered by $𝒬$, which completes the proof.

Consider now any query $Q_i$, for $i\ge j+1$. Then, the probability that $Q_i$ considers $W$ is bounded as follows:

Since $C$ is a large enough constant, by the union bound, the probability that at least one query of the queries $Q_{j+1}\mathrm{\dots },Q_k$ considers $W$ is therefore strictly below $1$ (recall that there are at most $k\le \mathrm{\ell }\le {\mathrm{\Delta }}^3$ queries, and holds, for large enough $C$). Hence, there exists a witness that is not considered by these queries, which completes the proof. $◀$

For the sake of a contradiction, suppose that there exists a sequence of queries $Q_1,\mathrm{\dots },Q_k$ that does not form a $(\mathrm{\Delta }-1)$-Query-Scheme but still allows the algorithm $𝒜$ to learn the input graph exactly. Since the queries do not form a $(\mathrm{\Delta }-1)$-Query-Scheme, there exists a witness $W=(\{u,v\},\{w_1,\mathrm{\dots },w_{2\mathrm{\Delta }-2}\})$ that is not considered by the queries. Consider now any two input graphs $G_1$ and $G_2$ of maximum degree $\mathrm{\Delta }$ that have the following properties: $u$’s neighbours are $w_1,\mathrm{\dots },w_{\mathrm{\Delta }-1}$, and $v$’s neighbours are $w_{\mathrm{\Delta }},\mathrm{\dots },w_{2\mathrm{\Delta }-2}$. In $G_1$, there is also an edge between $u$ and $v$, and in $G_2$ there is no edge between $u$ and $v$. Observe that the degrees of $u$ and $v$ in $G_1$ and $G_2$ are $\mathrm{\Delta }$ and $\mathrm{\Delta }-1$, respectively. The maximum degrees in $G_1$ and $G_2$ are therefore at most $\mathrm{\Delta }$.

Now, we claim that, for every query $Q_i$, the oracle can respond with an independent set $I_i$ that does not include both vertices $u$ and $v$. Observe that the algorithm therefore cannot learn whether the edge $uv$ exists since both $G_1$ and $G_2$ are consistent with all query answers. The algorithm therefore cannot distinguish between the two graphs $G_1,G_2$, which then completes the argument.

Since $Q_i$ does not consider $W$, there exists a vertex $w\in \{w_1,\mathrm{\dots },w_{2\mathrm{\Delta }-2}\}$ such that $w\in Q_i$. Hence, the oracle can construct an independent set starting with vertex $w$ (e.g., by running the Greedy maximal independent set algorithm where $w$ is the first vertex picked), which implies that either $u$ or $v$ cannot be included in the independent set. This completes the proof. $◀$

Combining Lemma 10 with Lemma 11, we obtain the main lower bound result of this section as a corollary:

Denote by $𝒞$ the family of $n$-vertex cycles on the vertex set $V$ with $|V|=n$, which serve as the input to our algorithm.

Let $𝐀$ be a randomized query algorithm that executes $\mathrm{\ell }:={\log }_3(n)-1$ rounds and that, on any input $C\in 𝒞$, succeeds with probability strictly above $\frac{1}{2}$. Then, by Yao’s lemma, there exists a deterministic query algorithm ${𝐀}_{\text{det}}$ that succeeds on strictly more than half of the inputs in $𝒞$ and also runs in $\mathrm{\ell }$ rounds.

We first observe that, since ${𝐀}_{\text{det}}$ is deterministic, and we also assume that the oracle answers are deterministic, for every $C\in 𝒞$, there exists a unique execution of ${𝐀}_{\text{det}}$, i.e., a sequence of query vertices $V_1,\mathrm{\dots },V_{\mathrm{\ell }}$, query answers $I_1,\mathrm{\dots },I_{\mathrm{\ell }}$, and output $C_{\text{out}}\in 𝒞$ produced by the algorithm. We observe that $C_{\text{out}}$ may be different from $C$ if the algorithm errs on input $C$.

Denote by ${𝒞}_1\subseteq 𝒞$ the subset of inputs on which the algorithm succeeds, and let ${𝒞}_0=𝒞\setminus {𝒞}_1$ denote the inputs on which the algorithm fails. We will now argue that, for every input $C\in {𝒞}_1$ on which the algorithm succeeds, there exists a unique input $C^{\prime }\in {𝒞}_0$ on which the algorithm fails, i.e., there exists an injective mapping from ${𝒞}_1$ into ${𝒞}_0$, which implies that $|{𝒞}_1|\le |{𝒞}_0|$. This is a contradiction to the fact that ${𝐀}_{\text{det}}$ is correct on strictly more than half of the instances in $𝒞$, which in turn implies that the algorithm $𝐀$ does not exist.

Let $C\in {𝒞}_1$ be an input on which ${𝐀}_{\text{det}}$ succeeds. Denote by $V_1,\mathrm{\dots },V_{\mathrm{\ell }}$ the vertices queried by the algorithm in the $\mathrm{\ell }$ query rounds and by $I_1,\mathrm{\dots },I_{\mathrm{\ell }}$ the query responses. We associate the following complete ternary tree $𝒯$ with $\mathrm{\ell }+1$ layers to the query vertices and responses in an execution of $𝐀$:

• $\mathrm{■}$

  The root (layer 1) is labelled with $V=[n]$.

• $\mathrm{■}$

  For an internal node in layer $1\le i\le \mathrm{\ell }$ with label $U\subseteq V$, the node has three children with labels $U_1,U_2,U_3$ such that $U=U_1\dot{\cup }{U}_2\dot{\cup }{U}_3$, and

  	$U_1$	$=(U\cap V_i)\cap I_i,$	queried and reported
  	$U_2$	$=(U\cap V_i)\setminus I_i,$	queried and not reported
  	$U_3$	$=U\setminus V_i.$	not queried

Denote by $L_1,L_2,\mathrm{\dots }$ the leaves of $𝒯$ from left-to-right. We observe that, by construction, the leaves are disjoint and their union equals $V$, i.e., ${\dot{\cup }}_i{L}_i=V$. Consider now a leaf $L_i$ that contains at least two vertices $u,v$. The vertices $u,v$ are indistinguishable as they behaved exactly the same throughout the execution of the algorithm. Indistinguishable here means that the cycle $C^{\prime }$ obtained from the cycle $C$ by swapping the positions of $u$ and $v$ leads to the exact same execution of the algorithm as the execution for $C$. The algorithm, however, fails on $C^{\prime }$ as the output produced is $C_{\text{out}}=C$. Hence, as long as there exists a leaf that contains at least two vertices, we can identify an input on which the algorithm fails and establish our injective mapping from ${𝒞}_1$ to ${𝒞}_0$. To avoid that there are no leaves that contain two vertices, the number of leaves in $𝒯$ must be at least $n$. Since $𝒯$ is ternary and of depth $\mathrm{\ell }+1$, we obtain that $\mathrm{\ell }\ge {\log }_3(n)$ must hold, a contradiction to the assumption that $\mathrm{\ell }={\log }_3(n)-1$. This completes the proof. $◀$

Last, we give our $\mathrm{\Omega }({\mathrm{\Delta }}^2)$ queries lower bound for graphs of maximum degree $\mathrm{\Delta }$. The key observation in our proof is that, for every non-edge $uv$ in the input graph $G$, there must exist an oracle response maximal independent set that contains both vertices $u$ and $v$, since, if the opposite was true then the algorithm could not distinguish between the input graph $G$ and the graph $G\cup \{uv\}$.

For integers $N>0$, let ${\mathscr{H}}_N$ denote the set of all bipartite graphs $H=(A,B,E)$ with $|A|=|B|=N$. Then, let ${𝒢}_N$ be the family of graphs obtained from ${\mathscr{H}}_N$ by turning the bipartitions $A$ and $B$ of each of its graphs $H=(A,B,E)\in {\mathscr{H}}_N$ into (disjoint) cliques.

Let $𝐀$ denote a randomized query algorithm that succeeds with probability strictly above $1/2$ on each input $G\in {𝒢}_N$, and for the sake of a contradiction, we assume that $𝒜$ executes at most $\mathrm{\ell }=N^2-1$ queries. Then, by Yao’s lemma, there exists a deterministic query algorithm ${𝒜}_{\text{det}}$ that also executes at most $\mathrm{\ell }$ queries and succeeds on strictly more than half of the inputs in ${𝒢}_N$.

First, observe that $\alpha (G)\le 2$, for every $G\in {𝒢}_N$ since at most one vertex from $A$ and at most one vertex from $B$ can be included in any independent set. Hence, every independent set reported by ${𝐀}_{\text{det}}$ on any of the input graphs $G\in {𝒢}_N$ is of size at most $2$.

Denote by ${𝒢}_N^1\subseteq {𝒢}_N$ the subset of inputs on which ${𝒜}_{\text{det}}$ succeeds, and let ${𝒢}_N^0={𝒢}_N\setminus {𝒢}_N^1$. We will show that there exists an injective map from ${𝒢}_N^1$ to ${𝒢}_N^0$, which implies that $|{𝒢}_N^1|\le |{𝒢}_N^0|$, a contradiction to the fact that ${𝒜}_{\text{det}}$ succeeds on strictly more than half of the instances. This in turn implies that algorithm $𝐀$ does not exists, which establishes the theorem.