Graph Verification with a Betweenness Oracle

Mano Vikash Janardhanan
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:238-249, 2017.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v76-janardhanan17a, title = {Graph Verification with a Betweenness Oracle}, author = {Janardhanan, Mano Vikash}, booktitle = {Proceedings of the 28th International Conference on Algorithmic Learning Theory}, pages = {238--249}, year = {2017}, editor = {Hanneke, Steve and Reyzin, Lev}, volume = {76}, series = {Proceedings of Machine Learning Research}, month = {15--17 Oct}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v76/janardhanan17a/janardhanan17a.pdf}, url = {https://proceedings.mlr.press/v76/janardhanan17a.html}, 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.} }
Endnote
%0 Conference Paper %T Graph Verification with a Betweenness Oracle %A Mano Vikash Janardhanan %B Proceedings of the 28th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Steve Hanneke %E Lev Reyzin %F pmlr-v76-janardhanan17a %I PMLR %P 238--249 %U https://proceedings.mlr.press/v76/janardhanan17a.html %V 76 %X 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.
APA
Janardhanan, M.V.. (2017). Graph Verification with a Betweenness Oracle. Proceedings of the 28th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 76:238-249 Available from https://proceedings.mlr.press/v76/janardhanan17a.html.

Related Material