Computing (All) Minimum Cuts In Practice (via Zoom)

Abstract: The minimum cut problem is the problem of computing a partition of a graph's vertices into two sets (i.e., a cut) to minimize the number of edges crossing the cut. In this talk, I present a practically efficient algorithm to find all global minimum cuts in huge undirected graphs. While the problem is easily solved in polynomial time in theory, previous techniques are too slow to be used on large graphs in practice: $O(nm  +n^2\log n +n^*m\log n)$, where $n$ is the number of vertices of the graph, $m$ is the number of edges, and $n^*$ is the number of vertices in a cactus representation of all minimum cuts. Our new algorithm is the conclusion of a series of recent results focusing on computing minimum cuts efficiently in practice. I give an overview of these recent results, showing the evolution to the present algorithm for efficiently computing all minimum cuts.

The techniques used have the following general form, which is gaining significant traction in algorithm engineering: aggressively apply data reduction rules (from parameterized algorithms literature) to reduce the graph to a small equivalent instance that can be solved significantly faster with standard (and generally slow) techniques. For finding all minimum cuts, this final step is done using an optimized version of the algorithm of Nagamochi, Nakao, and Ibaraki (2000). In shared memory, the algorithm finds all minimum cuts of graphs with up to billions of edges and millions of minimum cuts in a few minutes.

This is joint work with Monika Henzinger, Alexander Noe, and Christian Schulz. It recently appeared at the 28th European Symposium on Algorithms (ESA 2020).

Bio: Darren Strash’s research interests center on graph algorithms for large social networks and web-crawl graphs. His additional areas of expertise include computational geometry, graph drawing, subgraph counting and listing, dynamic data structures, combinatorial optimization, and heuristic algorithms.  

Before coming to Hamilton, Strash was a visiting assistant professor at Colgate University. Before Colgate, he spent two years in Germany as a postdoctoral researcher at Karlsruhe Institute of Technology’s Institute of Theoretical Informatics. Strash worked for three years as a software engineer at Intel.

In his free time, he enjoys playing strategic board games, reading sci-fi and fantasy novels, and contributing to openstreetmap.org. Strash earned his bachelor’s in computer science from Cal Poly Pomona and his doctorate from the University of California, Irvine.