Approximation Algorithms for Min-Distance Problems in DAGs

Authors Mina Dalirrooyfard, Jenny Kaufmann



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.60.pdf
  • Filesize: 0.89 MB
  • 17 pages

Document Identifiers

Author Details

Mina Dalirrooyfard
  • MIT, Cambridge, MA, USA
Jenny Kaufmann
  • Harvard University, Cambridge, MA, USA

Acknowledgements

We thank our advisor, Virginia Vassilevska Williams, for many helpful suggestions.

Cite AsGet BibTex

Mina Dalirrooyfard and Jenny Kaufmann. Approximation Algorithms for Min-Distance Problems in DAGs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.60

Abstract

Graph parameters such as the diameter, radius, and vertex eccentricities are not defined in a useful way in Directed Acyclic Graphs (DAGs) using the standard measure of distance, since for any two nodes, there is no path between them in one of the two directions. So it is natural to consider the distance between two nodes as the length of the shortest path in the direction in which this path exists, motivating the definition of the min-distance. The min-distance between two nodes u and v is the minimum of the shortest path distances from u to v and from v to u. As with the standard distance problems, the Strong Exponential Time Hypothesis [Impagliazzo-Paturi-Zane 2001, Calabro-Impagliazzo-Paturi 2009] leaves little hope for computing min-distance problems faster than computing All Pairs Shortest Paths, which can be solved in Õ(mn) time. So it is natural to resort to approximation algorithms in Õ(mn^{1-ε}) time for some positive ε. Abboud, Vassilevska W., and Wang [SODA 2016] first studied min-distance problems achieving constant factor approximation algorithms on DAGs, and Dalirrooyfard et al [ICALP 2019] gave the first constant factor approximation algorithms on general graphs for min-diameter, min-radius and min-eccentricities. Abboud et al obtained a 3-approximation algorithm for min-radius on DAGs which works in Õ(m√n) time, and showed that any (2-δ)-approximation requires n^{2-o(1)} time for any δ > 0, under the Hitting Set Conjecture. We close the gap, obtaining a 2-approximation algorithm which runs in Õ(m√n) time. As the lower bound of Abboud et al only works for sparse DAGs, we further show that our algorithm is conditionally tight for dense DAGs using a reduction from Boolean matrix multiplication. Moreover, Abboud et al obtained a linear time 2-approximation algorithm for min-diameter along with a lower bound stating that any (3/2-δ)-approximation algorithm for sparse DAGs requires n^{2-o(1)} time under SETH. We close this gap for dense DAGs by obtaining a 3/2-approximation algorithm which works in O(n^{2.350}) time and showing that the approximation factor is unlikely to be improved within O(n^{ω - o(1)}) time under the high dimensional Orthogonal Vectors Conjecture, where ω is the matrix multiplication exponent.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Fine-grained complexity
  • Graph algorithms
  • Diameter
  • Radius
  • Eccentricities

Metrics

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

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is Valiant’s parser. SIAM Journal on Computing, 47(6):2527-2555, 2018. Google Scholar
  2. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681-1697, 2015. Google Scholar
  3. 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, 2016. Google Scholar
  4. Udit Agarwal and Vijaya Ramachandran. Fine-grained complexity for sparse graphs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 239-252, 2018. Google Scholar
  5. D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput., 28(4):1167-1181, 1999. Google Scholar
  6. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, 2020. Google Scholar
  7. B. Ben-Moshe, B. K. Bhattacharya, Q. Shi, and A. Tamir. Efficient algorithms for center problems in cactus networks. Theoretical Computer Science, 378(3):237-252, 2007. Google Scholar
  8. P. Berman and S. P. Kasiviswanathan. Faster approximation of distances in graphs. In Proc. WADS, pages 541-552, 2007. Google Scholar
  9. Michele Borassi, Pierluigi Crescenzi, Michel Habib, Walter A. Kosters, Andrea Marino, and Frank W. Takes. Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs: With an application to the six degrees of separation games. Theoretical Computer Science, 586:59-80, 2015. Google Scholar
  10. Karl Bringmann and Philip Wellnitz. Clique-based lower bounds for parsing tree-adjoining grammars. arXiv preprint, 2018. URL: http://arxiv.org/abs/1803.00804.
  11. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The complexity of satisfiability of small depth circuits. In International Workshop on Parameterized and Exact Computation, pages 75-85. Springer, 2009. Google Scholar
  12. T. M. Chan. All-pairs shortest paths for unweighted undirected graphs in o(mn) time. ACM Transactions on Algorithms, 8(4):34, 2012. Google Scholar
  13. Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre Tarjan, and Virginia Vassilevska Williams. Better approximation algorithms for the graph diameter. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1041-1052, 2014. Google Scholar
  14. V. Chepoi, F. Dragan, and Y. Vaxès. Center and diameter problems in plane triangulations and quadrangulations. In Proc. SODA, pages 346-355, 2002. Google Scholar
  15. V. Chepoi and F. F. Dragan. A linear-time algorithm for finding a central vertex of a chordal graph. In ESA, pages 159-170, 1994. Google Scholar
  16. F. R. K. Chung. Diameters of graphs: Old problems and new results. Congr. Numer., 60:295-317, 1987. Google Scholar
  17. D.G. Corneil, F.F. Dragan, M. Habib, and C. Paul. Diameter determination on restricted graph families. Discr. Appl. Math., 113:143-166, 2001. Google Scholar
  18. L. Cowen and C. Wagner. Compact roundtrip routing for digraphs. In SODA, pages 885-886, 1999. Google Scholar
  19. Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, and Yuancheng Yu. Approximation algorithms for min-distance problems. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  20. D. Dvir and G. Handler. The absolute center of a network. Networks, 43:109-118, 2004. Google Scholar
  21. D. Eppstein. Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms and Applications, 3(3):1-27, 1999. Google Scholar
  22. Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks cannot compute their diameter in sublinear time. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1150-1162. SIAM, 2012. Google Scholar
  23. François Le Gall and Florent Urrutia. Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1029-1046. SIAM, 2018. Google Scholar
  24. S.L. Hakimi. Optimum location of switching centers and absolute centers and medians of a graph. Oper. Res., 12:450-459, 1964. Google Scholar
  25. R. Impagliazzo and R. Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  26. Seth Pettie. A faster all-pairs shortest path algorithm for real-weighted sparse graphs. In International Colloquium on Automata, Languages, and Programming, pages 85-97. Springer, 2002. Google Scholar
  27. Seth Pettie and Vijaya Ramachandran. Computing shortest paths with comparisons and additions. In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pages 267-276, 2002. Google Scholar
  28. Liam Roditty and Virginia 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, pages 515-524, 2013. Google Scholar
  29. Virginia Vassilevksa Williams, Nike Sun, and Nishith Khandwala. Lecture notes in graph algorithms (hitting sets, APSP), October 2016. URL: http://theory.stanford.edu/~virgi/cs267/lecture5.pdf.
  30. O. Weimann and R. Yuster. Approximating the diameter of planar graphs in near linear time. In Proc. ICALP, 2013. Google Scholar
  31. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348(2-3):357-365, 2005. Google Scholar
  32. Virginia Vassilevska Williams and R Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. Journal of the ACM (JACM), 65(5):1-38, 2018. Google Scholar
  33. C. Wulff-Nilsen. Wiener index, diameter, and stretch factor of a weighted planar graph in subquadratic time. Technical report, University of Copenhagen, 2008. Google Scholar
  34. Raphael Yuster. Computing the diameter polynomially faster than APSP. arXiv preprint, 2010. URL: http://arxiv.org/abs/1011.6181.
  35. Raphael Yuster and Uri Zwick. Fast sparse matrix multiplication. ACM Trans. Algorithms, 1(1):2–13, 2005. URL: https://doi.org/10.1145/1077464.1077466.
  36. U. Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):289-317, 2002. 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