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 ow on bipartite graphs to improve a graph bisection partition. Given a graph partition [S, B, W] 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 ow problem. A further enhancement to improve a partition is to generalize the bipartite network to a general network and then solve a max-ow 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.