TL;DR
This paper introduces a significantly faster exact algorithm for the multiterminal cut problem, a fundamental graph problem with applications in diverse fields. By combining novel data reduction techniques with a branch-and-reduce framework and an ILP solver, the authors achieve performance improvements of several orders of magnitude, enabling the solution of much larger instances than previously possible.
What Problem Does This Paper Address?
The multiterminal cut problem asks us to partition the vertices of a weighted undirected graph into $k$ sets, each containing a designated "terminal" vertex, such that the total weight of edges crossing between these sets is minimized. This problem is a generalization of the well-known minimum s-t-cut problem and is NP-hard for $k \ge 3$. While approximation algorithms and fixed-parameter tractable algorithms exist, finding exact solutions for large instances has remained a significant challenge. The de facto standard for obtaining exact solutions has been Integer Linear Programming (ILP), but this approach struggles with scalability. This paper aims to bridge this gap by developing a much faster exact algorithm that can handle larger and more complex graphs.
Methods
The core of the paper's contribution lies in its novel "branch-and-reduce" approach. This method combines two key strategies:
- Kernelization: This involves applying a set of data reduction rules to simplify the graph without altering the optimal solution. These rules identify edges that are either guaranteed to be in the minimum cut (and can be deleted) or guaranteed not to be in the minimum cut (and their incident vertices can be contracted). The paper introduces new kernelization rules and adapts existing ones from related problems.
- Branch-and-Reduce Framework: When kernelization can no longer simplify the graph, the algorithm "branches" by picking an edge and creating two subproblems: one where the edge is contracted and one where it is deleted. This process is guided by maintaining lower and upper bounds on the optimal cut value, allowing the algorithm to prune branches that cannot lead to a better solution.
The authors also integrate their kernelization techniques with an existing ILP formulation. This "Kernel+ILP" approach first applies kernelization to reduce the graph size and then feeds the smaller graph to the ILP solver.
Datasets
The paper evaluates its algorithms on several types of datasets:
- Random Hyperbolic Graphs: Generated using the KaGen tool, these graphs have power-law degree distributions and vary in size ($n=2^{14}-2^{18}$) and average degree (8, 16, 32). They are used with $k \in \{3,4,5,6,7\}$ terminals.
- US State Border Graphs: These weighted graphs represent borders between US states, with vertices as census blocks and edge weights as border lengths. They are used with $k \in \{3,4,5,6,7\}$ terminals.
- Large Real-World Networks: A collection of graphs from various sources, including social, web, and map graphs (e.g., bcsstk30, ca-2010, higgs-twitter). These are used with $k \in \{3,4,5,8\}$ terminals and varying percentages of vertices designated as terminals.
- Protein-Protein Interaction Networks: Graphs derived from the STRING database, where vertices represent proteins and edges represent predicted interactions. Terminals are assigned based on protein function classes.
Key Insights and Ideas
- Kernelization is Crucial: The paper strongly emphasizes that data reduction (kernelization) is not just a minor optimization but a fundamental component that drastically improves performance for both the branch-and-reduce algorithm and the ILP approach.
- Trade-off Between Approaches: There's a clear trade-off: Kernel+ILP excels on problems with small kernels but high cut values, while the pure branch-and-reduce algorithm is more efficient for problems with small cut values. This suggests that a hybrid approach, where subproblems are solved by the most suitable method, could be even more powerful.
- Branching Strategy Matters: The choice of which edge to branch on significantly impacts performance. The "HeavyVertex" strategy, which prioritizes edges connected to vertices with high connectivity to terminals, proved to be consistently superior.
- Priority Queue Design is Important: The order in which subproblems are explored (managed by the priority queue comparator) also affects performance, with strategies focusing on low lower bounds or few terminals showing competitive results.
- Graph Structure Influences Kernelization: The effectiveness of specific kernelization rules (like "Triangle" vs. "HighConnectivity") is highly dependent on the underlying graph structure.
Key Results
- Orders of Magnitude Speedup: The proposed branch-and-reduce algorithm, especially when combined with kernelization (Kernel+ILP), achieves speedups of multiple orders of magnitude compared to the standard ILP formulation.
- Solving Larger Instances: The new algorithms can solve instances that were previously intractable for ILP, including graphs with over a million vertices.
- Performance Comparison: The optimized branch-and-reduce algorithm (using HeavyVertex selection and all kernelization rules) outperforms the basic ILP by a mean speedup factor of 67 (median 95). Kernel+ILP achieves a mean speedup of 43 (median 71).
- Parallelism Benefits: The shared-memory parallel implementation shows good speedup, achieving an average factor of 7.9x with 16 cores, though some problems exhibit limited parallel scalability due to highly varied subproblem complexities.
- Kernelization Variants: Experiments show that combining "Low" and "High" kernelization rules is generally beneficial, while the impact of "Triangle" and "HighConnectivity" varies with graph structure.
Limitations and Future Work
- Limited Parallel Scalability: For a few specific problems with highly disparate subproblem complexities, parallel speedup is limited. The authors suggest that distributing flow computations across threads could address this.
- Hybrid Approach for Subproblems: The paper suggests that future work could involve combining the branching algorithm with ILP more dynamically, solving each subproblem using the method best suited for its properties.
- Scalable Distributed Parallelism: The authors aim to introduce scalable distributed parallelism in future work.
Summary updated