Grainger College of Engineering, All Events

View Full Calendar

Hsien-Chih Chang "Shortcut Partitions: Steiner Point Removal, Distance Oracles, Tree Covers, and More"

Event Type
Illinois Computer Science
3401 Siebel Center for Computer Science
Nov 13, 2023   10:00 am  
Hsien-Chih Chang (Dartmouth)
Candice Steidinger
Originating Calendar
Computer Science Speakers Calendar

We look forward to seeing you in person in 3401 Siebel Center for Computer Science. 

Abstract:  The notion of shortcut partition, introduced recently by Chang, Conroy, Le, Milenkovic, Solomon, and Than [FOCS23, SODA24], 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 constantly many clusters; put it differently, the _hop-diameter_ of the graph formed by contracting all the clusters is bounded.

 In this talk we explain how to construct shortcut partitions for planar graphs (and minor-free graphs, if time permits).  Next we give several applications.  First, we demonstrate the existence of _tree cover_ for arbitrary planar graphs with stretch 1+ε and O(1) many trees for any fixed ε.  Specifically, a tree cover [AP92, GKR01, BFN19] of a metric space (X, δ) is a collection of trees, so that every pair of points u and v in X has a low-distortion path in at least one of the trees.  Next, we showcase the applicability of tree covers by constructing distance oracles, emulators, and a simpler and better embedding of planar graphs into O(1)-treewidth graphs with small additive distortion, resolving an open problem in this line of research [FKS19].

 As a highlight of our work, we employ our shortcut partition to resolve a major open problem — the 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.  

Joint work with Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, and Cuong Than. .

link for robots only