Lund University Publications

LUND UNIVERSITY LIBRARIES

Computing Graph Distances Parameterized by Treewidth and Diameter

(2017) 11th International Symposium on Parameterized and Exact Computation In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) 63. p.1-11
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.
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
volume
63
pages
11 pages
publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
conference name
11th International Symposium on Parameterized and Exact Computation
external identifiers
• scopus:85014621576
ISBN
978-3-95977-023-1
DOI
10.4230/LIPIcs.IPEC.2016.16
language
English
LU publication?
yes
id
00c4f488-9a55-41de-beca-520c54641a51
2017-04-28 11:37:48
date last changed
2018-09-09 04:50:24
```@inproceedings{00c4f488-9a55-41de-beca-520c54641a51,
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 &gt; 0, no algorithm with running time n^{2-epsilon}*exp(o(k)) can distinguish between graphs with diameter 2 and 3.},
author       = {Husfeldt, Thore},
booktitle    = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
isbn         = {978-3-95977-023-1},
language     = {eng},
month        = {01},
pages        = {1--11},
publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title        = {Computing Graph Distances Parameterized by Treewidth and Diameter},
url          = {http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.16},
volume       = {63},
year         = {2017},
}

```