Document Open Access Logo

An Experimental Study of Algorithms for Packing Arborescences

Authors Loukas Georgiadis , Dionysios Kefallinos, Anna Mpanti, Stavros D. Nikolopoulos

PDF
Thumbnail PDF

File

LIPIcs.SEA.2022.14.pdf
  • Filesize: 0.73 MB
  • 16 pages

Document Identifiers

Author Details

Loukas Georgiadis
  • Department of Computer Science & Engineering, University of Ioannina, Greece
Dionysios Kefallinos
  • Department of Computer Science & Engineering, University of Ioannina, Greece
Anna Mpanti
  • Department of Computer Science & Engineering, University of Ioannina, Greece
Stavros D. Nikolopoulos
  • Department of Computer Science & Engineering, University of Ioannina, Greece

Funding

Research supported by the Hellenic Foundation for Research and Innovation (H.F.R.I.) under the "First Call for H.F.R.I. Research Projects to support Faculty members and Researchers and the procurement of high-cost research equipment grant", Project FANTA (eFficient Algorithms for NeTwork Analysis), number HFRI-FM17-431.

Acknowledgements

We would like to thank the anonymous referees for several useful comments.

Cite AsGet BibTex

Loukas Georgiadis, Dionysios Kefallinos, Anna Mpanti, and Stavros D. Nikolopoulos. An Experimental Study of Algorithms for Packing Arborescences. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SEA.2022.14

Abstract

A classic result of Edmonds states that the maximum number of edge-disjoint arborescences of a directed graph G, rooted at a designated vertex s, equals the minimum cardinality c_G(s) of an s-cut of G. This concept is related to the edge connectivity λ(G) of a strongly connected directed graph G, defined as the minimum number of edges whose deletion leaves a graph that is not strongly connected. In this paper, we address the question of how efficiently we can compute a maximum packing of edge-disjoint arborescences in practice, compared to the time required to determine the edge connectivity of a graph. To that end, we explore the design space of efficient algorithms for packing arborescences of a directed graph in practice and conduct a thorough empirical study to highlight the merits and weaknesses of each technique. In particular, we present an efficient implementation of Gabow’s arborescence packing algorithm and provide a simple but efficient heuristic that significantly improves its running time in practice.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Graph algorithms
Keywords
  • Arborescences
  • Edge Connectivity
  • Graph Algorithms

Metrics

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

Supplementary Materials

References

  1. András A Benczúr and David R Karger. Augmenting undirected edge connectivity in Õ(n2) time. Journal of Algorithms, 37(1):2-36, 2000. URL: https://doi.org/10.1006/jagm.2000.1093.
  2. Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi. Fast edge splitting and edmonds' arborescence construction for unweighted graphs. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '08, pages 455-464, USA, 2008. Society for Industrial and Applied Mathematics. Google Scholar
  3. Kshipra Bhawalkar, Jon Kleinberg, Kevin Lewi, Tim Roughgarden, and Aneesh Sharma. Preventing unraveling in social networks: The anchored k-core problem. SIAM Journal on Discrete Mathematics, 29(3):1452-1475, 2015. Google Scholar
  4. CAD Benchmarking Lab. ISCAS'89 benchmark information. URL: http://www.cbl.ncsu.edu/www/CBL_Docs/iscas89.html.
  5. C. Demetrescu, A.V. Goldberg, and D.S. Johnson. 9th DIMACS Implementation Challenge: Shortest Paths. http://www.dis.uniroma1.it/~challenge9/, 2007.
  6. J. Edmonds. Submodular functions, matroids, and certain polyhedra. Combinatorial Structures and their Applications, pages 69-81, 1970. Google Scholar
  7. J. Edmonds. Edge-disjoint branchings. Combinatorial Algorithms, pages 91-96, 1972. Google Scholar
  8. D. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, USA, 2010. Google Scholar
  9. S. Fujishige. A note on disjoint arborescences. Combinatorica, 30(2):247-252, 2010. URL: https://doi.org/10.1007/s00493-010-2518-y.
  10. Satoru Fujishige and Naoyuki Kamiyama. The root location problem for arc-disjoint arborescences. Discrete Applied Mathematics, 160(13):1964-1970, 2012. URL: https://doi.org/10.1016/j.dam.2012.04.013.
  11. H. N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. Journal of Computer and System Sciences, 50:259-273, 1995. Google Scholar
  12. Harold N. Gabow. Efficient splitting off algorithms for graphs. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC '94, pages 696-705, New York, NY, USA, 1994. Association for Computing Machinery. URL: https://doi.org/10.1145/195058.195436.
  13. Loukas Georgiadis, Dionysios Kefallinos, Luigi Laura, and Nikos Parotsidis. An experimental study of algorithms for computing the edge connectivity of a directed graph. In Martin Farach-Colton and Sabine Storandt, editors, Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2021, Virtual Conference, January 10-11, 2021, pages 85-97. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976472.7.
  14. M. Ghaffari, K. Nowicki, and M. Thorup. Faster algorithms for edge connectivity via random 2-out contractions. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’20, pages 1260-1279, USA, 2020. Society for Industrial and Applied Mathematics. Google Scholar
  15. M. Henzinger, S. Rao, and D. Wang. Local flow partitioning for faster edge connectivity. SIAM Journal on Computing, 49(1):1-36, 2020. Google Scholar
  16. N. Kamiyama, N. Katoh, and A. Takizawa. Arc-disjoint in-trees in directed graphs. Combinatorica, 29:197-214, 2009. URL: https://doi.org/10.1007/s00493-009-2428-z.
  17. D. R. Karger. Minimum cuts in near-linear time. Journal of the ACM, 47(1):46-76, January 2000. URL: https://doi.org/10.1145/331605.331608.
  18. K.-I. Kawarabayashi and M. Thorup. Deterministic edge connectivity in near-linear time. Journal of the ACM, 66(1), December 2018. URL: https://doi.org/10.1145/3274663.
  19. J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.
  20. Jure Leskovec and Rok Sosič. Snap: A general-purpose network analysis and graph-mining library. ACM Transactions on Intelligent Systems and Technology (TIST), 8(1):1, 2016. Google Scholar
  21. László Lovász. On two minimax theorems in graph. Journal of Combinatorial Theory, Series B, 21(2):96-103, 1976. URL: https://doi.org/10.1016/0095-8956(76)90049-6.
  22. F. D. Malliaros, C. Giatsidis, A. N. Papadopoulos, and M. Vazirgiannis. The core decomposition of networks: theory, algorithms and applications. The VLDB Journal, 29(1):61-92, 2020. URL: https://doi.org/10.1007/s00778-019-00587-4.
  23. H. Nagamochi and T. Ibaraki. Algorithmic Aspects of Graph Connectivity. Cambridge University Press, 2008. 1st edition. Google Scholar
  24. Yossi Shiloach. Edge-disjoint branching in directed multigraphs. Information Processing Letters, 8(1):24-27, 1979. URL: https://doi.org/10.1016/0020-0190(79)90086-3.
  25. Robert Endre Tarjan. A good algorithm for edge-disjoint branching. Information Processing Letters, 3(2):51-53, 1974. URL: https://doi.org/10.1016/0020-0190(74)90024-6.
  26. Po Tong and E.L. Lawler. A faster algorithm for finding edge-disjoint branchings. Information Processing Letters, 17(2):73-76, 1983. URL: https://doi.org/10.1016/0020-0190(83)90073-X.
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