Document Open Access Logo

On Computing the Average Distance for Some Chordal-Like Graphs

Author Guillaume Ducoffe

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.44.pdf
  • Filesize: 0.78 MB
  • 16 pages

Document Identifiers

Author Details

Guillaume Ducoffe
  • National Institute of Research and Development in Informatics, Bucharest, Romania
  • University of Bucharest, Romania

Funding

  • Ducoffe, Guillaume: This work was supported by project PN-19-37-04-01 “New solutions for complex problems in current ICT research fields based on modelling and optimization”, funded by the Romanian Core Program of the Ministry of Research and Innovation (MCI) 2019-2022.

Cite As Get BibTex

Guillaume Ducoffe. On Computing the Average Distance for Some Chordal-Like Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 44:1-44:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.44

Abstract

The Wiener index of a graph G is the sum of all its distances. Up to renormalization, it is also the average distance in G. The problem of computing this parameter has different applications in chemistry and networks. We here study when it can be done in truly subquadratic time (in the size n+m of the input) on n-vertex m-edge graphs. Our main result is a complete answer to this question, assuming the Strong Exponential-Time Hypothesis (SETH), for all the hereditary subclasses of chordal graphs. Interestingly, the exact same result also holds for the diameter problem. The case of non-hereditary chordal subclasses happens to be more challenging. For the chordal Helly graphs we propose an intricate Õ(m^{3/2})-time algorithm for computing the Wiener index, where m denotes the number of edges. We complete our results with the first known linear-time algorithm for this problem on the dually chordal graphs. The former algorithm also computes the median set.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • Wiener index
  • Graph diameter
  • Hardness in P
  • Chordal graphs
  • Helly graphs

Metrics

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

References

  1. A. Backurs, L. Roditty, G. Segal, V. Vassilevska Williams, and N. Wein. Towards tight approximation bounds for graph diameter and eccentricities. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 267-280, 2018. Google Scholar
  2. L. Bénéteau, J. Chalopin, V. Chepoi, and Y. Vaxès. Medians in median graphs and their cube complexes in linear time. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  3. J. Blair and B. Peyton. An introduction to chordal graphs and clique trees. In Graph theory and sparse matrix computation, pages 1-29. ORNL, 1993. Google Scholar
  4. John Adrian Bondy and Uppaluri Siva Ramachandra Murty. Graph theory, volume 244 of Graduate Texts in Mathematics. Springer-Verlag London, 2008. Google Scholar
  5. E. Bonnet. 4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time n^4/3. Technical report, arXiv, 2021. URL: http://arxiv.org/abs/2101.02312.
  6. E. Bonnet. Inapproximability of diameter in super-linear time: Beyond the 5/3 ratio. In Markus Bläser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference), volume 187 of LIPIcs, pages 17:1-17:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.STACS.2021.17.
  7. Michele Borassi, Pierluigi Crescenzi, and Michel Habib. Into the square: On the complexity of some quadratic-time solvable problems. Electronic Notes in Theoretical Computer Science, 322:51-67, April 2016. URL: https://doi.org/10.1016/j.entcs.2016.03.005.
  8. Nicolas Bousquet, Aurélie Lagoutte, Zhentao Li, Aline Parreau, and Stéphan Thomassé. Identifying codes in hereditary classes of graphs and vc-dimension. SIAM Journal on Discrete Mathematics, 29(4):2047-2064, 2015. Google Scholar
  9. A. Brandstädt, V. Chepoi, and F.F. Dragan. The algorithmic use of hypertree structure and maximum neighbourhood orderings. Discrete Applied Mathematics, 82(1-3):43-77, 1998. Google Scholar
  10. A. Brandstädt, V. Chepoi, and F.F. Dragan. Tree-structured graphs. In Handbook of Graph Theory, Combinatorial Optimization, and Algorithms. CRC Press, 2016. Google Scholar
  11. A. Brandstädt, F.F. Dragan, V. Chepoi, and V. Voloshin. Dually chordal graphs. SIAM Journal on Discrete Mathematics, 11(3):437-455, 1998. Google Scholar
  12. K. Bringmann, T. Husfeldt, and M. Magnusson. Multivariate Analysis of Orthogonal Range Searching and Graph Distances. Algorithmica, pages 1-24, 2020. Google Scholar
  13. P. Buneman. A characterisation of rigid circuit graphs. Discrete Mathematics, 9(3):205-212, 1974. Google Scholar
  14. S. Cabello. Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. ACM Transactions on Algorithms, 15(2):21, 2018. Google Scholar
  15. G. Chang and G. Nemhauser. The k-domination and k-stability problems on sun-free chordal graphs. SIAM Journal on Algebraic Discrete Methods, 5(3):332-345, 1984. Google Scholar
  16. B. Chazelle and E. Welzl. Quasi-optimal range searching in spaces of finite VC-dimension. Discrete & Computational Geometry, 4(5):467-489, 1989. Google Scholar
  17. D. Corneil, F. F. Dragan, M. Habib, and C. Paul. Diameter determination on restricted graph families. Discrete Applied Mathematics, 113(2-3):143-166, 2001. Google Scholar
  18. M. Dalirrooyfard and N. Wein. Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs. In 53rd Annual ACM Symposium on Theory of Computing (STOC), 2021. To appear. Google Scholar
  19. P. Dankelmann. Computing the average distance of an interval graph. Information Processing Letters, 48(6):311-314, 1993. Google Scholar
  20. Reinhard Diestel. Graph Theory. Graduate Texts in Mathematics. Springer, 2010. 4th edition. URL: https://doi.org/10.1007/978-3-662-53622-3.
  21. F.F. Dragan, G. Ducoffe, and H.M. Guarnera. Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs, 2021. To appear. Technical report available on arXiv (https://arxiv.org/abs/2102.08349).
  22. G. Ducoffe and Feodor F.F. Dragan. A story of diameter, radius, and (almost) Helly property. Networks, 77(3):435-453, 2021. Google Scholar
  23. G. Ducoffe, M. Habib, and L. Viennot. Fast diameter computation within split graphs. In COCOA, pages 155-167. Springer, 2019. Google Scholar
  24. G. Ducoffe, M. Habib, and L. Viennot. Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1905-1922. SIAM, 2020. Google Scholar
  25. Guillaume Ducoffe. Around the diameter of AT-free graphs. CoRR, abs/2010.15814, 2020. URL: http://arxiv.org/abs/2010.15814.
  26. Guillaume Ducoffe. Optimal diameter computation within bounded clique-width graphs. CoRR, abs/2011.08448, 2020. URL: http://arxiv.org/abs/2011.08448.
  27. David Eppstein and Joseph Wang. Fast approximation of centrality. Journal of Graph Algorithms and Applications, 8(1):39-45, 2004. URL: https://doi.org/10.7155/jgaa.00081.
  28. Jacob Evald and Søren Dahlgaard. Tight hardness results for distance and centrality problems in constant degree graphs. Technical Report arXiv:1609.08403, ArXiv, 2016. Google Scholar
  29. S. Foldes and P.L. Hammer. Split graphs having Dilworth number two. Canadian Journal of Mathematics, 29(3):666-672, 1977. Google Scholar
  30. F. Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1):47-56, 1974. Google Scholar
  31. A. Goldman. Optimal center location in simple networks. Transportation science, 5(2):212-221, 1971. Google Scholar
  32. R. Impagliazzo and R. Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  33. C. Jordan. Sur les assemblages de lignes. J. Reine Angew. Math, 70(185):81, 1869. Google Scholar
  34. Dirk Koschützki, Katharina Anna Lehmann, Leon Peeters, Stefan Richter, Dagmar Tenfelde-Podehl, and Oliver Zlotowski. Centrality indices. In Network Analysis, pages 16-61. Springer, 2005. URL: https://doi.org/10.1007/978-3-7091-0741-6_9.
  35. P.S. Kumar and C.V. Madhavan. Minimal vertex separators of chordal graphs. Discrete Applied Mathematics, 89(1-3):155-168, 1998. Google Scholar
  36. R. Li. Settling SETH vs. Approximate Sparse Directed Unweighted Diameter (up to (NU)NSETH). In 53rd Annual ACM Symposium on Theory of Computing (STOC), 2021. To appear. Google Scholar
  37. M. Moscarini. Doubly chordal graphs, Steiner trees, and connected domination. Networks, 23(1):59-69, 1993. Google Scholar
  38. S. Olariu. A simple linear-time algorithm for computing the center of an interval graph. International Journal of Computer Mathematics, 34(3-4):121-128, 1990. Google Scholar
  39. L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing (STOC), pages 515-524, 2013. Google Scholar
  40. R. E. Tarjan and M. Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on computing, 13(3):566-579, 1984. Google Scholar
  41. J. R. Walter. Representations of rigid cycle graphs. PhD thesis, Wayne State University, Department of Mathematics, 1972. Google Scholar
  42. H. Wiener. Structural determination of paraffin boiling points. Journal of the American chemical society, 69(1):17-20, 1947. Google Scholar
  43. D. Willard. New data structures for orthogonal range queries. SIAM Journal on Computing, 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 About DROPS Imprint Privacy Contact