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.APPROX-RANDOM.2014.80
URN: urn:nbn:de:0030-drops-46894
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4689/
Go to the corresponding LIPIcs Volume Portal

Chlamtác, Eden ; Dinitz, Michael

Lowest Degree k-Spanner: Approximation and Hardness

pdf-format:
6.pdf (0.5 MB)

Abstract

A k-spanner is a subgraph in which distances are approximately preserved, up to some given stretch factor k. We focus on the following problem: Given a graph and a value k, can we find a k-spanner that minimizes the maximum degree? While reasonably strong bounds are known for some spanner problems, they almost all involve minimizing the total number of edges. Switching the objective to the degree introduces significant new challenges, and currently the only known approximation bound is an O~(Delta^(3-2*sqrt(2)))-approximation for the special case when k = 2 [Chlamtac, Dinitz, Krauthgamer FOCS 2012] (where Delta is the maximum degree in the input graph). In this paper we give the first non-trivial algorithm and polynomial-factor hardness of approximation for the case of general k. Specifically, we give an LP-based O~(Delta^((1-1/k)^2) )-approximation and prove that it is hard to approximate the optimum to within Delta^Omega(1/k) when the graph is undirected, and to within Delta^Omega(1) when it is directed.

BibTeX - Entry

@InProceedings{chlamtc_et_al:LIPIcs:2014:4689,
  author =	{Eden Chlamt{\'a}c and Michael Dinitz},
  title =	{{Lowest Degree k-Spanner: Approximation and Hardness}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{80--95},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4689},
  URN =		{urn:nbn:de:0030-drops-46894},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.80},
  annote =	{Keywords: Graph spanners, approximation algorithms, hardness of approximation}
}

Keywords: Graph spanners, approximation algorithms, hardness of approximation
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

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