Document Open Access Logo

Computing Graph Distances Parameterized by Treewidth and Diameter

Author Thore Husfeldt

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2016.16.pdf
  • Filesize: 414 kB
  • 11 pages

Document Identifiers

Author Details

Thore Husfeldt

Cite AsGet BibTex

Thore Husfeldt. Computing Graph Distances Parameterized by Treewidth and Diameter. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 16:1-16:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.IPEC.2016.16

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.
Keywords
  • Graph algorithms
  • diameter
  • treewidth
  • Strong Exponential Time Hypothesis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, Va, USA, January 10-12, 2016, pages 377-391. SIAM, 2016. Google Scholar
  2. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michał Pilipczuk. An O(c^k n) 5-approximation algorithm for treewidth. SIAM J. Comput., 45(2):317-378, 2016. Google Scholar
  3. Sergio Cabello and Christian Knauer. Algorithms for bounded treewidth with orthogonal range searching. Comput. Geom., 42(9):815-824, 2009. Google Scholar
  4. Shiva Chaudhuri and Christos D. Zaroliagis. Shortest path queries in digraphs of small treewidth. Algorithmica, 27(3):212-226, 2000. Google Scholar
  5. David Eppstein. Subgraph isomorphism in planar graphs and related problems. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 22-24 January 1995. San Francisco, California, pages 632-640. ACM/SIAM, 1995. Google Scholar
  6. Russel Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  7. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms for graphs of bounded treewidth are probably optimal. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 777-789. SIAM, 2011. Google Scholar
  8. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 515-524. ACM, 2013. Google Scholar
  9. Dan E. Willard. New data structures for orthogonal range queries. SIAM J. Comput., 14(1):232-253, 1985. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact