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.111 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^{2epsilon}*exp(o(k)) can distinguish between graphs with diameter 2 and 3.
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/00c4f4889a5541debeca520c54641a51
 author
 Husfeldt, Thore ^{LU}
 organization
 publishing date
 20170131
 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  LeibnizZentrum für Informatik
 conference name
 11th International Symposium on Parameterized and Exact Computation
 external identifiers

 scopus:85014621576
 ISBN
 9783959770231
 DOI
 10.4230/LIPIcs.IPEC.2016.16
 language
 English
 LU publication?
 yes
 id
 00c4f4889a5541debeca520c54641a51
 date added to LUP
 20170428 11:37:48
 date last changed
 20170430 18:18:32
@inproceedings{00c4f4889a5541debeca520c54641a51, 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^{2epsilon}*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 = {9783959770231}, language = {eng}, month = {01}, pages = {111}, publisher = {Schloss Dagstuhl  LeibnizZentrum 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}, }