Graph Reconstruction via MIS Queries

In the Graph Reconstruction (GR) problem, a player initially only knows the vertex set V of an input graph G=(V, E) and is required to learn its set of edges E. To this end, the player submits queries to an oracle and must deduce E from the oracle's answers. In this paper, we initiate the study of GR via Maximal Independent Set (MIS) queries, a more powerful variant of Independent Set (IS) queries. Given a query U subseteq V, the oracle responds with any, potentially adversarially chosen, maximal independent set I subseteq U in the induced subgraph G[U]. We show that, for GR, MIS queries are strictly more powerful than IS queries when parametrized by the maximum degree Delta of the input graph. We give tight (up to poly-logarithmic factors) upper and lower bounds for this problem: 1. We observe that the simple strategy of taking uniform independent random samples of V and submitting those to the oracle yields a non-adaptive randomized algorithm that executes O(Delta2 · log n) queries and succeeds with high probability. Furthermore, combining the strategy of taking uniform random samples of V with the probabilistic method, we show the existence of a deterministic non-adaptive algorithm that executes O(Delta3 · log(fracnDelta)) queries. 2. Regarding lower bounds, we prove that the additional Delta factor when going from randomized non-adaptive algorithms to deterministic non-adaptive algorithms is necessary. We show that every non-adaptive deterministic algorithm requires Omega(Delta3 / log2 Delta) queries. For arbitrary randomized adaptive algorithms, we show that Omega(Delta2) queries are necessary in graphs of maximum degree Delta, and that Omega(log n) queries are necessary, even when the input graph is an n-vertex cycle.