Improved Directed Expander Decompositions
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912697117835264 |
|---|---|
| author | Fleischmann, Henry Li, George Z. Li, Jason |
| author_facet | Fleischmann, Henry Li, George Z. Li, Jason |
| contents | We obtain faster expander decomposition algorithms for directed graphs, matching the guarantees of Saranurak and Wang (SODA 2019) for expander decomposition on undirected graphs. Our algorithms are faster than prior work and also generalize almost losslessly to capacitated graphs. In particular, we obtain the first directed expander decomposition algorithm for capacitated graphs in near-linear time with optimal dependence on $ϕ$.
To obtain our result, we provide the first implementation and analysis of the non-stop cut-matching game for directed, capacitated graphs. All existing directed expander decomposition algorithms instead temporarily add ''fake edges'' before pruning them away in a final cleanup step. Our result shows that the natural undirected approach applies even to directed graphs. The difficulty is in its analysis, which is technical and requires significant modifications from the original setting of undirected graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_09729 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Directed Expander Decompositions Fleischmann, Henry Li, George Z. Li, Jason Data Structures and Algorithms We obtain faster expander decomposition algorithms for directed graphs, matching the guarantees of Saranurak and Wang (SODA 2019) for expander decomposition on undirected graphs. Our algorithms are faster than prior work and also generalize almost losslessly to capacitated graphs. In particular, we obtain the first directed expander decomposition algorithm for capacitated graphs in near-linear time with optimal dependence on $ϕ$. To obtain our result, we provide the first implementation and analysis of the non-stop cut-matching game for directed, capacitated graphs. All existing directed expander decomposition algorithms instead temporarily add ''fake edges'' before pruning them away in a final cleanup step. Our result shows that the natural undirected approach applies even to directed graphs. The difficulty is in its analysis, which is technical and requires significant modifications from the original setting of undirected graphs. |
| title | Improved Directed Expander Decompositions |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.09729 |