Huy L. Nguyen: Cutting corners cheaply, or how to remove Steiner points

Wednesday, October 9, 2013 - 4:00pm to 5:00pm
Huy L. Nguyen

Our main result is that the Steiner Point Removal (SPR) problem can always be solved with polylogarithmic distortion, which resolves in the affirmative a question posed by Chan, Xia, Konjevod, and Richa (2006). Specifically, we prove that for every edge-weighted graph G=(V,E,w) and a subset of terminals T⊆V, there is a graph G′=(T,E′,w′) that is isomorphic to a minor of G, such that for every two terminals u,v∈T, the shortest-path distances between them in G and in G′ satisfy dG,w(u,v)≤dG′,w′(u,v)≤O(log6|T|)⋅dG,w(u,v). Our existence proof actually gives a randomized polynomial-time algorithm.

Our proof features a new variant of metric decomposition. It is well-known that every finite metric space (X,d) admits a β-separating decomposition for β=O(log|X|), which roughly means for every desired diameter bound Δ>0 there is a randomized partitioning of X, which satisfies the following separation requirement: for every x,y∈X, the probability they lie in different clusters of the partition is at most βd(x,y)/Δ. We introduce an additional requirement, which is the following tail bound: for every shortest-path P of length d(P)≤Δ/β, the number of clusters of the partition that meet the path P, denoted ZP, satisfies Pr[ZP>t]≤2e−Ω(t) for all t>0.

Joint work with Lior Kamma and Robert Krauthgamer.