Document Open Access Logo

Subquadratic-Time Algorithm for the Diameter and All Eccentricities on Median Graphs

Authors Pierre Bergé, Guillaume Ducoffe, Michel Habib

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.9.pdf
  • Filesize: 0.8 MB
  • 21 pages

Document Identifiers

Author Details

Pierre Bergé
  • Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP, France
  • IRIF, CNRS, Université de Paris, France
Guillaume Ducoffe
  • National Institute of Research and Development in Informatics, Bucharest, Romania
  • University of Bucharest, Romania
Michel Habib
  • IRIF, CNRS
  • Université de Paris Cité, France

Cite As Get BibTex

Pierre Bergé, Guillaume Ducoffe, and Michel Habib. Subquadratic-Time Algorithm for the Diameter and All Eccentricities on Median Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.STACS.2022.9

Abstract

On sparse graphs, Roditty and Williams [2013] proved that no O(n^{2-ε})-time algorithm achieves an approximation factor smaller than 3/2 for the diameter problem unless SETH fails. We answer here an open question formulated in the literature: can we use the structural properties of median graphs to break this global quadratic barrier?
We propose the first combinatorial algorithm computing exactly all eccentricities of a median graph in truly subquadratic time. Median graphs constitute the family of graphs which is the most studied in metric graph theory because their structure represents many other discrete and geometric concepts, such as CAT(0) cube complexes. Our result generalizes a recent one, stating that there is a linear-time algorithm for computing all eccentricities in median graphs with bounded dimension d, i.e. the dimension of the largest induced hypercube (note that 1-dimensional median graphs are exactly the forests). This prerequisite on d is not necessarily anymore to determine all eccentricities in subquadratic time. The execution time of our algorithm is O(n^{1.6456}log^{O(1)} n).

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Data structures design and analysis
Keywords
  • Diameter
  • Eccentricities
  • Metric graph theory
  • Median graphs
  • Hypercubes

Metrics

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

Related Versions

References

  1. A. Abboud, F. Grandoni, and V. V. Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proc. of SODA, pages 1681-1697, 2015. Google Scholar
  2. A. Abboud, V. V. Williams, and J. R. Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Proc. of SODA, pages 377-391, 2016. Google Scholar
  3. S. P. Avann. Metric ternary distributive semi-lattices. Proc. Amer. Math. Soc., 12:407-414, 1961. Google Scholar
  4. H. Bandelt. Retracts of hypercubes. Journal of Graph Theory, 8(4):501-510, 1984. Google Scholar
  5. H. Bandelt and V. Chepoi. Metric graph theory and geometry: a survey. Contemp. Math., 453:49-86, 2008. Google Scholar
  6. H. Bandelt, V. Chepoi, A. W. M. Dress, and J. H. Koolen. Combinatorics of lopsided sets. Eur. J. Comb., 27(5):669-689, 2006. Google Scholar
  7. H. Bandelt, V. Chepoi, and D. Eppstein. Combinatorics and geometry of finite and infinite squaregraphs. SIAM J. Discret. Math., 24(4):1399-1440, 2010. Google Scholar
  8. H. Bandelt, L. Quintana-Murci, A. Salas, and V. Macaulay. The fingerprint of phantom mutations in mitochondrial dna data. Am. J. Hum. Genet., 71:1150-1160, 2002. Google Scholar
  9. H. Bandelt and M. van de Vel. Embedding topological median algebras in products of dendrons. Proc. London Math. Soc., 58:439-453, 1989. Google Scholar
  10. H. J. Bandelt, P. Forster, B. C. Sykes, and M. B. Richards. Mitochondrial portraits of human populations using median networks. Genetics, 141(2):743-753, 1995. Google Scholar
  11. J. Barthélemy and J. Constantin. Median graphs, parallelism and posets. Discret. Math., 111(1-3):49-63, 1993. Google Scholar
  12. J. Barthélemy, B. Leclerc, and B. Monjardet. On the use of ordered sets in problems of comparison and consensus of classifications. Journal of Classification, 3:187-224, 1986. Google Scholar
  13. L. Bénéteau, J. Chalopin, V. Chepoi, and Y. Vaxès. Medians in median graphs and their cube complexes in linear time. In Proc. of ICALP, volume 168, pages 10:1-10:17, 2020. Google Scholar
  14. P. Bergé, G. Ducoffe, and M. Habib. Subquadratic-time algorithm for the diameter and all eccentricities on median graphs. CoRR, abs/2110.02709, 2021. Google Scholar
  15. P. Bergé and M. Habib. Diameter, radius and all eccentricities in linear time for constant-dimension median graphs. In Proc. of LAGOS, 2021. Google Scholar
  16. G. Birkhoff and S. A. Kiss. A ternary operation in distributive lattices. Bull. Amer. Math. Soc., 53:745-752, 1947. Google Scholar
  17. B. Bresar. Characterizing almost-median graphs. Eur. J. Comb., 28(3):916-920, 2007. Google Scholar
  18. S. Cabello. Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. In Proc. of SODA, pages 2143-2152, 2017. Google Scholar
  19. S. Chechik, D. H. Larkin, L. Roditty, G. Schoenebeck, R. E. Tarjan, and V. V. Williams. Better approximation algorithms for the graph diameter. In Proc. of SODA, pages 1041-1052, 2014. Google Scholar
  20. V. Chepoi. Graphs of some CAT(0) complexes. Adv. Appl. Math., 24(2):125-179, 2000. Google Scholar
  21. V. Chepoi, F. F. Dragan, and Y. Vaxès. Center and diameter problems in plane triangulations and quadrangulations. In Proc. of SODA, pages 346-355, 2002. Google Scholar
  22. V. Chepoi, A. Labourel, and S. Ratel. Distance labeling schemes for cube-free median graphs. In Proc. of MFCS, volume 138, pages 15:1-15:14, 2019. Google Scholar
  23. G. Ducoffe. Isometric embeddings in trees and their use in distance problems. In Proc. of MFCS, volume 202 of LIPIcs, pages 43:1-43:16, 2021. 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 Proc. of SODA, pages 1905-1922, 2020. Google Scholar
  25. J. Hagauer, W. Imrich, and S. Klavzar. Recognizing median graphs in subquadratic time. Theor. Comput. Sci., 215(1-2):123-136, 1999. Google Scholar
  26. R. Hammack, W. Imrich, and S. Klavzar. Handbook of Product Graphs, Second Edition. CRC Press, Inc., 2011. Google Scholar
  27. W. Imrich, S. Klavzar, and H. M. Mulder. Median graphs and triangle-free graphs. SIAM J. Discret. Math., 12(1):111-118, 1999. Google Scholar
  28. S. Klavzar and H. M. Mulder. Partial cubes and crossing graphs. SIAM J. Discret. Math., 15(2):235-251, 2002. Google Scholar
  29. S. Klavzar, H. M. Mulder, and R. Skrekovski. An Euler-type formula for median graphs. Discret. Math., 187(1-3):255-258, 1998. Google Scholar
  30. S. Klavzar and S. V. Shpectorov. Characterizing almost-median graphs II. Discret. Math., 312(2):462-464, 2012. Google Scholar
  31. M. Kovse. Complexity of phylogenetic networks: counting cubes in median graphs and related problems. Analysis of complex networks: From Biology to Linguistics, pages 323-350, 2009. Google Scholar
  32. F. R. McMorris, H. M. Mulder, and F. S. Roberts. The median procedure on median graphs. Discret. Appl. Math., 84(1-3):165-181, 1998. Google Scholar
  33. H. M. Mulder and A. Schrijver. Median graphs and Helly hypergraphs. Discret. Math., 25(1):41-50, 1979. Google Scholar
  34. M. Mulder. The structure of median graphs. Discret. Math., 24(2):197-204, 1978. Google Scholar
  35. M. Mulder. The interval function of a graph. Mathematical Centre Tracts, Mathematisch Centrum, Amsterdam, 1980. Google Scholar
  36. L. Roditty and V. V. Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proc. of STOC, pages 515-524, 2013. Google Scholar
  37. V. Sassone, M. Nielsen, and G. Winskel. A classification of models for concurrency. In Proc. of CONCUR, volume 715 of Lecture Notes in Computer Science, pages 82-96, 1993. Google Scholar
  38. Peter M Winkler. Isometric embedding in products of complete graphs. Discrete Applied Mathematics, 7(2):221-225, 1984. 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