Graph Reconstruction via MIS Queries

Christian Konrad, Conor O'Sullivan, Victor Traistaru

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,…