Spanning Adjacency Oracles in Sublinear Time

Greg Bodwin, Henry Fleischmann

Suppose we are given an $n$-node, $m$-edge input graph $G$, and the goal is to compute a spanning subgraph $H$ on $O(n)$ edges. This can be achieved in linear $O(m+n)$ time via b…