Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more

Le and Wulff-Nilsen [SODA '24] initiated a systematic study of VC set systems to unweighted Kh-minor-free directed graphs. We extend their results in the following ways: bullet We present the first application of VC set systems for real-weighted minor-free digraphs to build the first exact subquadratic-space distance oracle with O(log n) query time. Prior work using VC set systems only applied in unweighted and integer weighted digraphs. bullet We describe a unified system for analyzing the VC dimension of balls and the LP set system (based on Li--Parter [STOC '19]) of Le--Wulff-Nilsen [SODA '24] using pseudodimension. This is a major conceptual contribution that allows for both improving our understanding of set systems in digraphs as well as improving the bound of the LP set system in directed graphs to h-1. bullet We present the first application of these set systems in a dynamic setting. Specifically, we construct decremental reachability oracles with subquadratic total update time and constant query time. Prior to this work, it was not known if this was possible to construct oracles with subquadratic total update time and polylogarithmic query time, even in planar digraphs. bullet We describe subquadratic time algorithms for unweighted digraphs including (1) constructions of exact distance oracles, (2) computation of vertex eccentricities and Wiener index. The main innovation in obtaining these results is the use of dynamic string data structures.