# Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues

arXiv: https://arxiv.org/abs/2306.09128 · HTML: https://mlsanity.com/paper/2306.09128/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 37 references that are in the map.
- First posted on arXiv 15 Jun 2023.

## Builds on (most cited first, 11 of 11)

- [Maximum Flow and Minimum-Cost Flow in Almost-Linear Time](https://mlsanity.com/paper/2203.00671/) (2022)
- [Cheeger Inequalities for Submodular Transformations](https://mlsanity.com/paper/1708.08781/) (2017)
- [Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms](https://mlsanity.com/paper/1408.2425/) (2014)
- [Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues](https://mlsanity.com/paper/2203.06168/) (2022)
- [A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond](https://mlsanity.com/paper/1910.08025/) (2019)
- [Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues](https://mlsanity.com/paper/2211.09776/) (2022)
- [Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion](https://mlsanity.com/paper/1404.4575/) (2014)
- [Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing](https://mlsanity.com/paper/2009.02584/) (2020)
- [Lecture Notes on the ARV Algorithm for Sparsest Cut](https://mlsanity.com/paper/1607.00854/) (2016)
- [A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems](https://mlsanity.com/paper/1905.11512/) (2019)
- [Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition](https://mlsanity.com/paper/2009.08479/) (2020)

## Abstract (arXiv)

We consider a new semidefinite programming relaxation for directed edge expansion, which is obtained by adding triangle inequalities to the reweighted eigenvalue formulation. Applying the matrix multiplicative weight update method to this relaxation, we derive almost linear-time algorithms to achieve O(√logn)-approximation and Cheeger-type guarantee for directed edge expansion, as well as an improved cut-matching game for directed graphs. This provides a primal-dual flow-based framework to obtain the best known algorithms for directed graph partitioning. The same approach also works for vertex expansion and for hypergraphs, providing a simple and unified approach to achieve the best known results for different expansion problems and different algorithmic techniques.