Fast algorithm finds key graph partitions using max flow
Canonical Cut Hierarchy in Almost-Linear Time via Reduction to Max-Flow
Data Structures and Algorithms
Summary
Understanding how a network splits into parts is important in many areas like design and analysis. The authors developed a fast method that uses advanced math tools called max-flow to find a special way to break down a network into smaller groups. Their approach works quickly even on large networks and helps calculate different properties related to connectivity and tree structures inside the network. This can help people who deal with complex networks get useful information faster.
What this means in practice
- •For network engineers: Compute network vulnerability and connectivity properties rapidly to reinforce or reconfigure networks efficiently.
- •For algorithm developers: Integrate fast graph partitioning techniques into tools that require efficient handling of large undirected graphs for optimization or analysis.
Authors
Karthekeyan Chandrasekaran, Harshul Sagar
Abstract
The canonical cut hierarchy recursively partitions a graph along Tutte-Nash-Williams partitions, choosing the partition with the most number of parts at each step. We give a randomized almost linear-time algorithm for computing this hierarchy in undirected graphs with polynomially bounded capacities via reduction to max-flow. This yields randomized almost linear-time algorithms for computing partition connectivity, strength, both arboricity and fractional arboricity, both integral and fractional spanning tree packing numbers, and implicit representations of the principal partition sequence and a maximum fractional spanning tree packing.