Optimal distance query reconstruction for graphs without long induced cycles

Paul Bastide, Carla Groenland

Given access to the vertex set $V$ of a connected graph $G=(V,E)$ and an oracle that given two vertices $u,v\in V$, returns the shortest path distance between $u$ and $v$, how many…