Faster Weak Expander Decompositions and Approximate Max Flow
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915598671282176 |
|---|---|
| author | Fleischmann, Henry Li, George Z. Li, Jason |
| author_facet | Fleischmann, Henry Li, George Z. Li, Jason |
| contents | We give faster algorithms for weak expander decompositions and approximate max flow on undirected graphs. First, we show that it is possible to "warm start" the cut-matching game when computing weak expander decompositions, avoiding the cost of the recursion depth. Our algorithm is also flexible enough to support weaker flow subroutines than previous algorithms.
Our second contribution is to streamline the recent non-recursive approximate max flow algorithm of Li, Rao, and Wang (SODA, 2025) and adapt their framework to use our new weak expander decomposition primitive. Consequently, we give an approximate max flow algorithm within a few logarithmic factors of the limit of expander decomposition-based approaches. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_02943 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Faster Weak Expander Decompositions and Approximate Max Flow Fleischmann, Henry Li, George Z. Li, Jason Data Structures and Algorithms We give faster algorithms for weak expander decompositions and approximate max flow on undirected graphs. First, we show that it is possible to "warm start" the cut-matching game when computing weak expander decompositions, avoiding the cost of the recursion depth. Our algorithm is also flexible enough to support weaker flow subroutines than previous algorithms. Our second contribution is to streamline the recent non-recursive approximate max flow algorithm of Li, Rao, and Wang (SODA, 2025) and adapt their framework to use our new weak expander decomposition primitive. Consequently, we give an approximate max flow algorithm within a few logarithmic factors of the limit of expander decomposition-based approaches. |
| title | Faster Weak Expander Decompositions and Approximate Max Flow |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.02943 |