Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues
This work addresses the problem of efficient graph partitioning for directed graphs, which is incremental as it builds on existing methods to improve algorithmic performance and generality.
The paper tackles directed graph partitioning by developing a new semidefinite programming relaxation using triangle inequalities and reweighted eigenvalues, resulting in almost linear-time algorithms with O(√log n)-approximation and Cheeger-type guarantees for directed edge expansion. It also extends to vertex expansion and hypergraphs, providing a unified framework that achieves the best known results across various expansion problems.
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(\sqrt{\log{n}})$-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.