Graph Decompositions and Length-Constrained Expanders (Invited Talk)

Haeupler, Bernhard

doi:10.4230/LIPIcs.ESA.2025.1

Graph Decompositions and Length-Constrained Expanders

Bernhard Haeupler

INSAIT, Sofia University “St. Kliment Ohridski”, Bulgaria
ETH Zürich, Switzerland

Abstract

Graph decompositions are powerful algorithmic tools with wide applications to graph structures (e.g., spanners, hopsets, sparsifiers, oblivious routings, etc.) and network optimization algorithms, including parallel, distributed and dynamic algorithms for flow and distance problems.

Classical graph decompositions include

$\blacksquare$

low-diameter decomposition, which captures $\ell_{1}$ -quantities like lengths and costs, and
$\blacksquare$

expander decomposition, which captures $\ell_{\infty}$ -quantities like flows and congestion.

This keynote starts with a brief survey of these classical decompositions, then presents length-constrained expanders and length-constrained expander decompositions – a recent and technically rich generalization that simultaneously controls length and congestion ( $\ell_{1}$ & $\ell_{\infty}$ ). Length-constrained expander decompositions significantly broaden and extend the range of applications for graph decompositions, and this talk will discuss several examples and ways to leverage their power.

Keywords and phrases:

Length-Constrained Expanders, Graph Decomposition, Network Optimization Algorithms

Category:

Invited Talk

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Graph algorithms analysis

Funding:

Partially funded by the Ministry of Education and Science of Bulgaria’s support for INSAIT as part of the Bulgarian National Roadmap for Research Infrastructure and through the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (ERC grant agreement 949272).

DOI:

10.4230/LIPIcs.ESA.2025.1

Event:

33rd Annual European Symposium on Algorithms (ESA 2025)

Editors:

Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

References

[1] Greg Bodwin, Bernhard Haeupler, and Merav Parter. Fault-tolerant spanners against bounded-degree edge failures: Linearly more faults, almost for free. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2609–2642. SIAM, 2024. doi:10.1137/1.9781611977912.93.
[2] Mohsen Ghaffari, Bernhard Haeupler, and Goran Zuzic. Hop-constrained oblivious routing. In Annual ACM Symposium on Theory of Computing (STOC), pages 1208–1220, 2021. doi:10.1145/3406325.3451098.
[3] Bernhard Haeupler, D Ellis Hershkowitz, Jason Li, Antti Roeyskoe, and Thatchaphol Saranurak. Low-step multi-commodity flow emulators. Annual ACM Symposium on Theory of Computing (STOC), pages 71–82, 2024. doi:10.1145/3618260.3649689.
[4] Bernhard Haeupler, D Ellis Hershkowitz, and Thatchaphol Saranurak. Maximum length-constrained flows and disjoint paths: Distributed, deterministic and fast. In Annual ACM Symposium on Theory of Computing (STOC), 2023. doi:10.1145/3564246.3585202.
[5] Bernhard Haeupler, D Ellis Hershkowitz, and Zihan Tan. Parallel greedy spanners. arXiv, 2023. arXiv:2304.08892.
[6] Bernhard Haeupler, D Ellis Hershkowitz, and Zihan Tan. New structures and algorithms for length-constrained expander decompositions. Symposium on Foundations of Computer Science (FOCS), pages 1634–1645, 2024. doi:10.1109/FOCS61266.2024.00102.
[7] Bernhard Haeupler, Jonas Huebotter, and Mohsen Ghaffari. A cut-matching game for constant-hop expanders. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1651–1678. SIAM, 2025. doi:10.1137/1.9781611978322.51.
[8] Bernhard Haeupler, Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak, and Shengzhe Wang. Parallel $(1+\epsilon)$ -approximate multi-commodity mincost flow in almost optimal depth and work. Symposium on Foundations of Computer Science (FOCS), 2025.
[9] Bernhard Haeupler, Yaowei Long, and Thatchaphol Saranurak. Dynamic deterministic constant-approximate distance oracles with $n^{\epsilon}$ worst-case update time. Symposium on Foundations of Computer Science (FOCS), pages 2033–2044, 2024. doi:10.1109/FOCS61266.2024.00121.
[10] Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak, and Shengzhe Wang. Length-constrained directed expander decomposition and length-constrained vertex-capacitated flow shortcuts. Annual European Symposium on Algorithms (ESA), 2025. doi:10.4230/LIPIcs.ESA.2025.108.
[11] Bernhard Haeupler, Harald Räcke, and Mohsen Ghaffari. Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality. In Annual ACM Symposium on Theory of Computing (STOC), pages 1325–1338, 2022. doi:10.1145/3519935.3520026.
[12] Bernhard Haeupler, David Wajc, and Goran Zuzic. Network coding gaps for completion times of multiple unicasts. In Symposium on Foundations of Computer Science (FOCS), pages 494–505. IEEE, 2020. doi:10.1109/FOCS46700.2020.00053.

[bib.bib1] [1] Greg Bodwin, Bernhard Haeupler, and Merav Parter. Fault-tolerant spanners against bounded-degree edge failures: Linearly more faults, almost for free. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2609–2642. SIAM, 2024. doi:10.1137/1.9781611977912.93.

[bib.bib2] [2] Mohsen Ghaffari, Bernhard Haeupler, and Goran Zuzic. Hop-constrained oblivious routing. In Annual ACM Symposium on Theory of Computing (STOC), pages 1208–1220, 2021. doi:10.1145/3406325.3451098.

[bib.bib3] [3] Bernhard Haeupler, D Ellis Hershkowitz, Jason Li, Antti Roeyskoe, and Thatchaphol Saranurak. Low-step multi-commodity flow emulators. Annual ACM Symposium on Theory of Computing (STOC), pages 71–82, 2024. doi:10.1145/3618260.3649689.

[bib.bib4] [4] Bernhard Haeupler, D Ellis Hershkowitz, and Thatchaphol Saranurak. Maximum length-constrained flows and disjoint paths: Distributed, deterministic and fast. In Annual ACM Symposium on Theory of Computing (STOC), 2023. doi:10.1145/3564246.3585202.

[bib.bib5] [5] Bernhard Haeupler, D Ellis Hershkowitz, and Zihan Tan. Parallel greedy spanners. arXiv, 2023. arXiv:2304.08892.

[bib.bib6] [6] Bernhard Haeupler, D Ellis Hershkowitz, and Zihan Tan. New structures and algorithms for length-constrained expander decompositions. Symposium on Foundations of Computer Science (FOCS), pages 1634–1645, 2024. doi:10.1109/FOCS61266.2024.00102.

[bib.bib7] [7] Bernhard Haeupler, Jonas Huebotter, and Mohsen Ghaffari. A cut-matching game for constant-hop expanders. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1651–1678. SIAM, 2025. doi:10.1137/1.9781611978322.51.

[bib.bib8] [8] Bernhard Haeupler, Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak, and Shengzhe Wang. Parallel $(1+\epsilon)$ -approximate multi-commodity mincost flow in almost optimal depth and work. Symposium on Foundations of Computer Science (FOCS), 2025.

[bib.bib9] [9] Bernhard Haeupler, Yaowei Long, and Thatchaphol Saranurak. Dynamic deterministic constant-approximate distance oracles with $n^{\epsilon}$ worst-case update time. Symposium on Foundations of Computer Science (FOCS), pages 2033–2044, 2024. doi:10.1109/FOCS61266.2024.00121.

[bib.bib10] [10] Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak, and Shengzhe Wang. Length-constrained directed expander decomposition and length-constrained vertex-capacitated flow shortcuts. Annual European Symposium on Algorithms (ESA), 2025. doi:10.4230/LIPIcs.ESA.2025.108.

[bib.bib11] [11] Bernhard Haeupler, Harald Räcke, and Mohsen Ghaffari. Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality. In Annual ACM Symposium on Theory of Computing (STOC), pages 1325–1338, 2022. doi:10.1145/3519935.3520026.

[bib.bib12] [12] Bernhard Haeupler, David Wajc, and Goran Zuzic. Network coding gaps for completion times of multiple unicasts. In Symposium on Foundations of Computer Science (FOCS), pages 494–505. IEEE, 2020. doi:10.1109/FOCS46700.2020.00053.