Understanding Approximation Error and Query Complexity in WormHole Routing

The WormHole algorithm demonstrates that efficient routing in large graphs can be achieved with minimal error and limited queries. By maintaining a sublinear “inner ring” that still contains the Chung–Lu core, WormHole ensures routing paths deviate by at most O(log log n) from the true shortest path, even in worst-case scenarios. The paper further bounds its query complexity under the node query model, proving that high-accuracy results can be obtained with a fraction of the exploration cost.