Cutting Corners Cheaply, or How to Remove Steiner Points

DOI10.1137/140951382zbMATH Open1328.05059arXiv1304.1449OpenAlexW2569472613MaRDI QIDQ5502176FDOQ5502176

Authors:

Publication date: 18 August 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: Our main result is that the Steiner Point Removal (SPR) problem can always be solved with polylogarithmic distortion, which answers 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 $TsubseteqV$, there is a graph $G^{\prime }=(T,E^{\prime },w^{\prime })$ that is isomorphic to a minor of $G$, such that for every two terminals $u,vinT$, the shortest-path distances between them in $G$ and in $G^{\prime }$ satisfy $d_{G,w}(u,v)le{d}_{G^{\prime },w^{\prime }}(u,v)leO(lo{g}^5|T|)cdot{d}_{G,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 $n$-point metric space $(X,d)$ admits a $$-separating decomposition for $$, which roughly means for every desired diameter bound $Delta>0$ there is a randomized partitioning of $X$, which satisfies the following separation requirement: for every $x,yinX$, the probability they lie in different clusters of the partition is at most $$. We introduce an additional requirement, which is the following tail bound: for every shortest-path $P$ of length $$, the number of clusters of the partition that meet the path $P$, denoted $Z_P$, satisfies $Pr[Z_P>t]le2e^{-Omega(t)}$ for all $t>0$.

Full work available at URL: https://arxiv.org/abs/1304.1449

Recommendations

• Cutting corners cheaply, or how to remove Steiner points
• Steiner point removal with distortion \(O(\log k)\)
• Defuzzification using Steiner points
• Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm
• Steiner point removal -- distant terminals don't (really) bother
• Optimal Steiner Points
• Cutting corners on the sphere
• Optimal Triangulation with Steiner Points
• scientific article; zbMATH DE number 874222

zbMATH Keywords

metric spacesapproximate distancesSteiner point removal

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distance in graphs (05C12) Graph minors (05C83) Discrete geometry (52C99)

Cites Work

• Extending Lipschitz functions via random metric partitions
• Approximate distance oracles
• A tight bound on approximating arbitrary metrics by tree metrics
• Twice-Ramanujan sparsifiers
• Graph spanners
• Ramsey partitions and proximity data structures
• Low diameter graph decompositions
• An improved approximation algorithm for requirement cut
• Excluded minors, network decomposition, and multicommodity flow
• Title not available (Why is that?)
• Strong-diameter decompositions of minor free graphs
• Steiner points in tree metrics don't (really) help
• Approximation algorithms for the 0-extension problem
• Vertex Sparsifiers: New Results from Old Techniques
• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
• Metric extension operators, vertex sparsifiers and Lipschitz extendability
• Algorithms – ESA 2004
• On vertex sparsifiers with Steiner nodes
• A Tight Lower Bound for the Steiner Point Removal Problem on Trees
• Extensions and limits to vertex sparsification
• Metric clustering via consistent labeling

Cited In (14)

• Cutting corners cheaply, or how to remove Steiner points
• Vertex sparsification in trees
• Improved guarantees for vertex sparsification in planar graphs
• Relaxed Voronoi: a simple framework for terminal-clustering problems
• Distance-preserving subgraphs of interval graphs
• Steiner points in tree metrics don't (really) help
• Terminal embeddings
• Steiner point removal -- distant terminals don't (really) bother
• Steiner point removal with distortion \(O(\log k)\)
• Metric decompositions of path-separable graphs
• Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm
• Improved guarantees for vertex sparsification in planar graphs
• Refined vertex sparsifiers of planar graphs
• A Tight Lower Bound for the Steiner Point Removal Problem on Trees

This page was built for publication: Cutting Corners Cheaply, or How to Remove Steiner Points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5502176)