Distributed Algorithms for Fundamental Graph Problems

This website collects all activity related to the research project “Distributed Algorithms for Fundamental Graph Problems (DiAloG)”. The main objective in this project is to develop faster graph algorithms in the CONGEST model of distributed computing with provable correctness and running time guarantees.

  • Principal Investigator: Sebastian Forster
  • Host Institution: University of Salzburg
  • Funding Agency: Austrian Science Fund (FWF)
  • Project Number: P 32863-N
  • Duration: 03/2020 – 09/2024

Associated Team Members

  • Sebastian Forster, PI
  • Tetiana Mazanko, administration
  • Tijn de Vos, PhD student
  • Anna Bolotina, MSc student

Former Team Members

  • Elisabeth Riedl, administration
  • Judith Warter, administration
  • Emilio Cruciani, postdoc
  • Aditi Dudeja, postdoc
  • Yasamin Nazari, postdoc

Publications

  • Jan van den Brand, Sebastian Forster, Yasamin Nazari, and Adam Polak. “On Dynamic Graph Algorithms with Predictions”. In: Proc. of the 2024 ACM-SIAM Symposium on Discrete Algorithms. SODA 2024 (Alexandria, VA, USA, Jan. 7–10, 2024). Ed. by David P. Woodruff. SIAM, 2024, pp. 3534–3557. doi:  10.1137/1.9781611977912.126. arXiv:  2307.09961.
  • Emilio Cruciani, Sebastian Forster, Gramoz Goranci, Yasamin Nazari, and Antonis Skarlatos. “Dynamic algorithms for 𝑘-center on graphs”. In: Proc. of the 2024 ACM-SIAM Symposium on Discrete Algorithms. SODA 2024 (Alexandria, VA, USA, Jan. 7–10, 2024). Ed. by David P. Woodruff. SIAM, 2024, pp. 3441–3462. doi:  10.1137/1.9781611977912.123. arXiv:  2307.15557.
  • Michal Dory, Sebastian Forster, Yael Kirkpatrick, Yasamin Nazari, Virginia Vassilevska Williams, and Tijn de Vos. “Fast 2-Approximate All-Pairs Shortest Paths”. In: Proc. of the 2024 ACM-SIAM Symposium on Discrete Algorithms. SODA 2024 (Alexandria, VA, USA, Jan. 7–10, 2024). Ed. by David P. Woodruff. SIAM, 2024, pp. 4728–4757. doi:  10.1137/1.9781611977912.169. arXiv:  2307.09258.
  • Luca Becchetti, Vincenzo Bonifaci, Emilio Cruciani, and Francesco Pasquale. “On a Voter Model with Context-Dependent Opinion Adoption”. In: Proc. of the 32nd International Joint Conference on Artificial Intelligence. IJCAI 2023 (Macao, SAR, China, Aug. 19–25, 2023). Announced at AAMAS 2023. ijcai.org, 2023, pp. 38–45. doi:  10.24963/IJCAI.2023/5. arXiv:  2305.07377.
  • Luca Becchetti, Vincenzo Bonifaci, Emilio Cruciani, and Francesco Pasquale. “On a Voter Model with Context-Dependent Opinion Adoption”. In: Proc. of the 2023 International Conference on Autonomous Agents and Multiagent Systems. AAMAS 2023 (London, United Kingdom, May 29–June 2, 2023). Ed. by Noa Agmon, Bo An, Alessandro Ricci, and William Yeoh. ACM, 2023, pp. 2766–2768. doi:  10.5555/3545946.3599071. arXiv:  2305.07377.
  • Emilio Cruciani, Hlafo Alfie Mimun, Matteo Quattropani, and Sara Rizzo. “Phase transition of the 𝑘-majority dynamics in biased communication models”. In: Distributed Computing 36.2 (2023). Announced at ICDCN 2021, pp. 107–135. doi:  10.1007/S00446-023-00444-2. arXiv:  2007.15306.
  • Sebastian Forster, Gramoz Goranci, Yasamin Nazari, and Antonis Skarlatos. “Bootstrapping Dynamic Distance Oracles”. In: Proc. of the 31st Annual European Symposium on Algorithms. ESA 2023 (Amsterdam, The Netherlands, Sept. 4–6, 2023). Ed. by Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman. Vol. 274. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023, 50:1–50:16. doi:  10.4230/LIPICS.ESA.2023.50. arXiv:  2303.06102.
  • Sebastian Forster, Yasamin Nazari, and Maximilian Probst Gutenberg. “Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch”. In: Proc. of the 55th Annual ACM Symposium on Theory of Computing. STOC 2023 (Orlando, FL, USA, June 20–23, 2023). Ed. by Barna Saha and Rocco A. Servedio. ACM, 2023, pp. 1173–1186. doi:  10.1145/3564246.3585213. arXiv:  2211.04217.
  • Sebastian Forster, Antonis Skarlatos, and Tijn de Vos. “Fast Algorithms for Energy Games in Special Cases”. In: Proc. of the Fourteenth International Symposium on Games, Automata, Logics, and Formal Verification. GandALF 2023 (Udine, Italy, Sept. 18–20, 2023). Ed. by Antonis Achilleos and Dario Della Monica. Vol. 390. EPTCS. 2023, pp. 236–252. doi:  10.4204/EPTCS.390.15. arXiv:  2307.08442.
  • Sebastian Forster and Tijn de Vos. “Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique”. In: Proc. of the 2023 ACM Symposium on Principles of Distributed Computing. PODC 2023 (Orlando, FL, USA, June 19–23, 2023). Ed. by Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, and Alkida Balliu. ACM, 2023, pp. 75–78. doi:  10.1145/3583668.3594577. arXiv:  2304.02315.
  • Sebastian Forster and Tijn de Vos. “Faster Cut Sparsification of Weighted Graphs”. In: Algorithmica 85.4 (2023). Announced at ICALP 2022, pp. 929–964. doi:  10.1007/S00453-022-01053-4. arXiv:  2112.03120.
  • Tijn de Vos. “Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model”. In: Proc. of the 2023 ACM Symposium on Principles of Distributed Computing. PODC 2023 (Orlando, FL, USA, June 19–23, 2023). Ed. by Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, and Alkida Balliu. ACM, 2023, pp. 71–74. doi:  10.1145/3583668.3594566. arXiv:  2304.01600.
  • Tijn de Vos. “Minimum Cost Flow in the CONGEST Model”. In: Proc. of the 30th International Colloquium on Structural Information and Communication Complexity. SIROCCO 2023 (Alcalá de Henares, Spain, June 6–9, 2023). Ed. by Sergio Rajsbaum, Alkida Balliu, Joshua J. Daymude, and Dennis Olivetti. Vol. 13892. LNCS. Springer, 2023, pp. 406–426. doi:  10.1007/978-3-031-32733-9\_18. arXiv:  2304.01600.
  • Joran van Apeldoorn and Tijn de Vos. “A Framework for Distributed Quantum Queries in the CONGEST Model”. In: Proc. of the 41st ACM Symposium on Principles of Distributed Computing. PODC 2022 (Salerno, Italy, July 25–29, 2022). Ed. by Alessia Milani and Philipp Woelfel. ACM, 2022, pp. 109–119. doi:  10.1145/3519270.3538413. arXiv:  2202.10969.
  • Greg Bodwin, Michael Dinitz, and Yasamin Nazari. “Vertex Fault-Tolerant Emulators”. In: Proc. of the 13th Innovations in Theoretical Computer Science Conference. ITCS 2022 (Berkeley, CA, USA, Jan. 31–Feb. 3, 2022). Ed. by Mark Braverman. Vol. 215. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 25:1–25:22. doi:  10.4230/LIPIcs.ITCS.2022.25. arXiv:  2109.08042.
  • Jan van den Brand, Sebastian Forster, and Yasamin Nazari. “Fast Deterministic Fully Dynamic Distance Approximation”. In: Proc. of the 63rd IEEE Annual Symposium on Foundations of Computer Science. FOCS 2022 (Denver, CO, USA, Oct. 31–Nov. 3, 2022). IEEE, 2022, pp. 1011–1022. doi:  10.1109/FOCS54457.2022.00099. arXiv:  2111.03361.
  • Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, and Mingquan Ye. “Minor Sparsifiers and the Distributed Laplacian Paradigm”. In: Proc. of the 62nd Annual IEEE Symposium on Foundations of Computer Science. FOCS 2021 (Denver, CO, USA, Feb. 7–10, 2022). IEEE, 2022, pp. 989–999. doi:  10.1109/FOCS52979.2021.00099. arXiv:  2012.15675.
  • Sebastian Forster, Martin Grösbacher, and Tijn de Vos. “An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions”. In: Proc. of the 25th International Conference on Principles of Distributed Systems. OPODIS 2021 (Strasbourg, France, Dec. 13–15, 2021). Ed. by Quentin Bramas, Vincent Gramoli, and Alessia Milani. Vol. 217. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 16:1–16:17. doi:  10.4230/LIPIcs.OPODIS.2021.16. arXiv:  2111.08975.
  • Sebastian Forster and Tijn de Vos. “Faster Cut Sparsification of Weighted Graphs”. In: Proc. of the 49th International Colloquium on Automata, Languages, and Programming. ICALP 2022 (Paris, France, July 4–8, 2022). Ed. by Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff. Vol. 229. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 61:1–61:19. doi:  10.4230/LIPIcs.ICALP.2022.61. arXiv:  2112.03120.
  • Sebastian Forster and Tijn de Vos. “The Laplacian Paradigm in the Broadcast Congested Clique”. In: Proc. of the 41st ACM Symposium on Principles of Distributed Computing. PODC 2022 (Salerno, Italy, July 25–29, 2022). Ed. by Alessia Milani and Philipp Woelfel. ACM, 2022, pp. 335–344. doi:  10.1145/3519270.3538436. arXiv:  2205.12059.
  • Jakub Lacki and Yasamin Nazari. “Near-Optimal Decremental Hopsets with Applications”. In: Proc. of the 49th International Colloquium on Automata, Languages, and Programming. ICALP 2022 (Paris, France, July 4–8, 2022). Ed. by Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff. Vol. 229. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, 86:1–86:20. doi:  10.4230/LIPIcs.ICALP.2022.86. arXiv:  2009.08416.
  • Sebastian Forster, Gramoz Goranci, and Monika Henzinger. “Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications”. In: Proc. of the 2021 ACM-SIAM Symposium on Discrete Algorithms. SODA 2021 (Virtual Conference, Jan. 10–13, 2021). Ed. by Dániel Marx. SIAM, 2021, pp. 1226–1245. doi:  10.1137/1.9781611976465.75. arXiv:  2004.10319.

Related Activities

  • Rising Stars Talk by Yasamin Nazari at the  Fifth TCS Women Meeting at Theory Fest 2022 (Jun 20, 2022)
  • Organization of science-to-public event  “Roadshow der Jungen Akademie” by Sebastian Forster at University of Salzburg  (Jun 15, 2022)
  • Science-to-public  blog post on algorithms by Sebastian Forster in Junge-Akademie-Blog hosted by derstandard.at (Dec 12, 2021)

Related Documents

Logo of the FWF

Supported by the Austrian Science Fund (FWF): P 32863-N.