Graph Verification with a Betweenness Oracle

Abstract

In this paper, we examine the query complexity of verifying a hidden graph $G$ with a betweenness oracle. Let $G=(V,E)$ be a hidden graph and $\hat{G}=(V,\hat{E})$ be a known graph. $V$ and $\hat{E}$ are known and $E$ is not known. The graphs are connected, unweighted and have bounded maximum degree $\Delta$. The task of the graph verification problem is to verify that $E=\hat{E}$. We have access to $G$ through a black-box betweenness oracle. A betweenness oracle returns whether a vertex lies along a shortest path between two other vertices. The betweenness oracle nicely captures many real-world problems. We prove that graph verification can be done using $n^{1+o(1)}$ betweenness queries. Surprisingly, this matches the state of the art for the graph verification problem with the much stronger distance oracle. We also prove that graph verification requires $\Omega(n)$ betweenness queries -- a matching lower bound.