Graph reconstruction with a betweenness oracle

TY - GEN

T1 - Graph reconstruction with a betweenness oracle

AU - Abrahamsen, Mikkel

AU - Bodwin, Greg

AU - Rotenberg, Eva

AU - Stöckel, Morten Danmark

N1 - Conference code: 33

PY - 2016/2/1

Y1 - 2016/2/1

N2 - Graph reconstruction algorithms seek to learn a hidden graph by repeatedly querying a blackbox oracle for information about the graph structure. Perhaps the most well studied and applied version of the problem uses a distance oracle, which can report the shortest path distance between any pair of nodes. We introduce and study the betweenness oracle, where bet(a, m, z) is true iff m lies on a shortest path between a and z. This oracle is strictly weaker than a distance oracle, in the sense that a betweenness query can be simulated by a constant number of distance queries, but not vice versa. Despite this, we are able to develop betweenness reconstruction algorithms that match the current state of the art for distance reconstruction, and even improve it for certain types of graphs. We obtain the following algorithms: 1. Reconstruction of general graphs in O(n2) queries 2. Reconstruction of degree-bounded graphs in Õ(n3/2) queries 3. Reconstruction of geodetic degree-bounded graphs in Õ(n) queries In addition to being a fundamental graph theoretic problem with some natural applications, our new results shed light on some avenues for progress in the distance reconstruction problem.

AB - Graph reconstruction algorithms seek to learn a hidden graph by repeatedly querying a blackbox oracle for information about the graph structure. Perhaps the most well studied and applied version of the problem uses a distance oracle, which can report the shortest path distance between any pair of nodes. We introduce and study the betweenness oracle, where bet(a, m, z) is true iff m lies on a shortest path between a and z. This oracle is strictly weaker than a distance oracle, in the sense that a betweenness query can be simulated by a constant number of distance queries, but not vice versa. Despite this, we are able to develop betweenness reconstruction algorithms that match the current state of the art for distance reconstruction, and even improve it for certain types of graphs. We obtain the following algorithms: 1. Reconstruction of general graphs in O(n2) queries 2. Reconstruction of degree-bounded graphs in Õ(n3/2) queries 3. Reconstruction of geodetic degree-bounded graphs in Õ(n) queries In addition to being a fundamental graph theoretic problem with some natural applications, our new results shed light on some avenues for progress in the distance reconstruction problem.

U2 - 10.4230/LIPIcs.STACS.2016.5

DO - 10.4230/LIPIcs.STACS.2016.5

M3 - Article in proceedings

SN - 978-3-95977-001-9

T3 - Leibniz International Proceedings in Informatics

SP - 5:1-5:14

BT - 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

A2 - Ollinger, Nicolas

A2 - Vollmer, Heribert

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Y2 - 17 February 2016 through 20 February 2016

ER -