2026-07-22T01:33:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6947 2024-03-06T10:38:48Z ddc:004 open_access

Computing Graph Distances Parameterized by Treewidth and Diameter Husfeldt, Thore Graph algorithms diameter treewidth Strong Exponential Time Hypothesis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thore Husfeldt 2017 Is Part Of LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2016.16 urn:nbn:de:0030-drops-69476 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.16 eng https://creativecommons.org/licenses/by/3.0/legalcode