- About
- Events
- Events
- Calendar
- Graduation Information
- Cornell Learning Machines Seminar
- Student Colloquium
- BOOM
- Spring 2025 Colloquium
- Conway-Walker Lecture Series
- Salton 2024 Lecture Series
- Seminars / Lectures
- Big Red Hacks
- Cornell University / Cornell Tech - High School Programming Workshop and Contest 2025
- Game Design Initiative
- CSMore: The Rising Sophomore Summer Program in Computer Science
- Explore CS Research
- ACSU Research Night
- Cornell Junior Theorists' Workshop 2024
- People
- Courses
- Research
- Undergraduate
- M Eng
- MS
- PhD
- PhD
- Admissions
- Current Students
- Computer Science Graduate Office Hours
- Advising Guide for Research Students
- Business Card Policy
- Cornell Tech
- Curricular Practical Training
- A & B Exam Scheduling Guidelines
- Fellowship Opportunities
- Field of Computer Science Ph.D. Student Handbook
- Graduate TA Handbook
- Field A Exam Summary Form
- Graduate School Forms
- Instructor / TA Application
- Ph.D. Requirements
- Ph.D. Student Financial Support
- Special Committee Selection
- Travel Funding Opportunities
- Travel Reimbursement Guide
- The Outside Minor Requirement
- Robotics Ph. D. prgram
- Diversity and Inclusion
- Graduation Information
- CS Graduate Minor
- Outreach Opportunities
- Parental Accommodation Policy
- Special Masters
- Student Spotlights
- Contact PhD Office
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.