License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.66
URN: urn:nbn:de:0030-drops-170041
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17004/
Go to the corresponding LIPIcs Volume Portal

Hershkowitz, D. Ellis ; Li, Jason

O(1) Steiner Point Removal in Series-Parallel Graphs

pdf-format:
LIPIcs-ESA-2022-66.pdf (1 MB)

Abstract

We study how to vertex-sparsify a graph while preserving both the graph’s metric and structure. Specifically, we study the Steiner point removal (SPR) problem where we are given a weighted graph G = (V,E,w) and terminal set V' ⊆ V and must compute a weighted minor G' = (V',E', w') of G which approximates G’s metric on V'. A major open question in the area of metric embeddings is the existence of O(1) multiplicative distortion SPR solutions for every (non-trivial) minor-closed family of graphs. To this end prior work has studied SPR on trees, cactus and outerplanar graphs and showed that in these graphs such a minor exists with O(1) distortion.
We give O(1) distortion SPR solutions for series-parallel graphs, extending the frontier of this line of work. The main engine of our approach is a new metric decomposition for series-parallel graphs which we call a hammock decomposition. Roughly, a hammock decomposition is a forest-like structure that preserves certain critical parts of the metric induced by a series-parallel graph.

BibTeX - Entry

@InProceedings{hershkowitz_et_al:LIPIcs.ESA.2022.66,
  author =	{Hershkowitz, D. Ellis and Li, Jason},
  title =	{{O(1) Steiner Point Removal in Series-Parallel Graphs}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{66:1--66:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17004},
  URN =		{urn:nbn:de:0030-drops-170041},
  doi =		{10.4230/LIPIcs.ESA.2022.66},
  annote =	{Keywords: Metric embeddings, graph algorithms, vertex sparsification}
}

Keywords: Metric embeddings, graph algorithms, vertex sparsification
Collection: 30th Annual European Symposium on Algorithms (ESA 2022)
Issue Date: 2022
Date of publication: 01.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI