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 ˆG=(V,ˆE) be a known graph. V and ˆE are known and E is not known. The graphs are connected, unweighted and have bounded maximum degree Δ. The task of the graph verification problem is to verify that E=ˆ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 n1+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 Ω(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