License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.87
URN: urn:nbn:de:0030-drops-90919
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9091/
Go to the corresponding LIPIcs Volume Portal

Lenzen, Christoph ; Levi, Reut

A Centralized Local Algorithm for the Sparse Spanning Graph Problem

pdf-format:
LIPIcs-ICALP-2018-87.pdf (0.5 MB)

Abstract

Constructing a sparse spanning subgraph is a fundamental primitive in graph theory. In this paper, we study this problem in the Centralized Local model, where the goal is to decide whether an edge is part of the spanning subgraph by examining only a small part of the input; yet, answers must be globally consistent and independent of prior queries.
Unfortunately, maximally sparse spanning subgraphs, i.e., spanning trees, cannot be constructed efficiently in this model. Therefore, we settle for a spanning subgraph containing at most (1+epsilon)n edges (where n is the number of vertices and epsilon is a given approximation/sparsity parameter). We achieve a query complexity of O~(poly(Delta/epsilon)n^{2/3}), where Delta is the maximum degree of the input graph. Our algorithm is the first to do so on arbitrary bounded degree graphs. Moreover, we achieve the additional property that our algorithm outputs a spanning subgraph of bounded stretch i.e., distances are approximately preserved. With high probability, for each deleted edge there is a path of O(log n * (Delta+log n)/epsilon) hops in the output that connects its endpoints.

BibTeX - Entry

@InProceedings{lenzen_et_al:LIPIcs:2018:9091,
  author =	{Christoph Lenzen and Reut Levi},
  title =	{{A Centralized Local Algorithm for the Sparse Spanning Graph Problem}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{87:1--87:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9091},
  URN =		{urn:nbn:de:0030-drops-90919},
  doi =		{10.4230/LIPIcs.ICALP.2018.87},
  annote =	{Keywords: local, spanning graph, sparse}
}

Keywords: local, spanning graph, sparse
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

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