Applications of the Dulmage--Mendelsohn Decomposition and Network Flow to Graph Bisection Improvement

In this paper, we consider the use of the Dulmage--Mendelsohn decomposition and network flow on bipartite graphs to improve a graph bisection partition. Given a graph partition [B, W, S] with a vertex separator S and two disconnected components B and W, different strategies are considered based on the Dulmage--Mendelsohn decomposition to reduce the separator size |S| and/or the imbalance between B and W. For the case when the vertices are weighted, we relate this to the bipartite network flow problem. A further enhancement to improve a partition is to generalize the bipartite network to a general network and then solve a max-flow problem. We demonstrate the utility of these improvement techniques on a set of sparse test matrices, where we find top-level separators, nested dissection, and multisection orderings.