Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More

The notion of shortcut partition, introduced recently by Chang, Conroy, Le, Milenković, Solomon, and Than [CCL + 23], is a new type of graph partition into low-diameter clusters. Roughly speaking, the shortcut partition guarantees that for every two vertices u and v in the graph, there exists a path between u and v that intersects only a few clusters. They proved that any planar graph admits a shortcut partition and gave several applications, including a construction of tree cover for arbitrary planar graphs with stretch 1+ϵ and O(1) many trees for any fixed ϵ ∈ (0, 1). However, the construction heavily exploits planarity in multiple steps, and is thus inherently limited to planar graphs.

In this work, we breach the "planarity barrier" to construct a shortcut partition for K r -minor-free graphs for any r. To this end, we take a completely different approach -our key contribution is a novel deterministic variant of the cop decomposition in minor-free graphs [And86, AGG + 14]. Our shortcut partition for K r -minor-free graphs yields several direct applications. Most notably, we construct the first optimal distance oracle for K r -minor-free graphs, with 1 + ϵ stretch, linear space, and constant query time for any fixed ϵ ∈ (0, 1). The previous best distance oracle [AG06] uses O(n log n) space and O(log n) query time, and its construction relies on Robertson-Seymour structural theorem and other sophisticated tools. We also obtain the first tree cover of O(1) size for minor-free graphs with stretch 1 + ϵ, while the previous best (1 + ϵ)-tree cover has size O(log

As a highlight of our work, we employ our shortcut partition to resolve a major open problemthe Steiner point removal (SPR) problem: Given any set K of terminals in an arbitrary edge-weighted planar graph G, is it possible to construct a minor M of G whose vertex set is K, which preserves the shortest-path distances between all pairs of terminals in G up to a constant factor? Positive answers to the SPR problem were only known for very restricted classes of planar graphs: trees [Gup01], outerplanar graphs [BG08], and series-parallel graphs [HL22]. We resolve the SPR problem in the affirmative for any planar graph, and more generally for any K r -minor-free graph for any fixed r. To achieve this result, we prove the following general reduction and combine it with our new shortcut partition: For any graph family closed under taking subgraphs, the existence of a shortcut partition yields a positive solution to the SPR problem.