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.IPEC.2016.16
URN: urn:nbn:de:0030-drops-69476
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6947/
Go to the corresponding LIPIcs Volume Portal

Husfeldt, Thore

Computing Graph Distances Parameterized by Treewidth and Diameter

pdf-format:
LIPIcs-IPEC-2016-16.pdf (0.4 MB)

Abstract

We show that the eccentricity of every vertex in an undirected graph on n vertices can be computed in time n exp O(k*log(d)), where k is the treewidth of the graph and d is the diameter. This means that the diameter and the radius of the graph can be computed in the same time. In particular, if the diameter is constant, it can be determined in time n*exp(O(k)). This result matches a recent hardness result by Abboud, Vassilevska Williams, and Wang [SODA 2016] that shows that under the Strong Exponential Time Hypothesis of Impagliazzo, Paturi, and Zane [J. Comp. Syst. Sc., 2001], for any epsilon > 0, no algorithm with running time n^{2-epsilon}*exp(o(k)) can distinguish between graphs with diameter 2 and 3.

BibTeX - Entry

@InProceedings{husfeldt:LIPIcs:2017:6947,
  author =	{Thore Husfeldt},
  title =	{{Computing Graph Distances Parameterized by Treewidth and Diameter}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{16:1--16:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Jiong Guo and Danny Hermelin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6947},
  URN =		{urn:nbn:de:0030-drops-69476},
  doi =		{10.4230/LIPIcs.IPEC.2016.16},
  annote =	{Keywords: Graph algorithms, diameter, treewidth, Strong Exponential Time Hypothesis}
}

Keywords: Graph algorithms, diameter, treewidth, Strong Exponential Time Hypothesis
Collection: 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Issue Date: 2017
Date of publication: 09.02.2017

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