Abstract
In Directed Multiway Cut (Dir-MC), the goal is to find a minimum-weight subset of edges in a directed graph to disconnect $k$ terminal nodes from each other. In Node-weighted Multiway Cut (Node-MC), the goal is to remove a minimum-weight subset of nodes to achieve the same for an undirected graph. While these problems have known approximations, previous algorithms relied on complex LP formulations and optimal solutions. This paper introduces extremely simple, near-linear time rounding algorithms for both problems using a natural distance-based LP relaxation. These algorithms achieve state-of-the-art approximation bounds (2 for Dir-MC and $2(1-1/k)$ for Node-MC) and work with any feasible solution, allowing for significant speedups via multicommodity flow solvers.
Introduction
The Multiway Cut problem is a fundamental challenge in combinatorial optimization: given a graph and a set of $k$ terminal nodes, what is the minimum cost to remove edges (or nodes) such that no two terminals can reach each other? While the undirected edge-weighted version is well-understood, the directed and node-weighted variants have historically required complex, non-intuitive algorithms.
Chandra Chekuri and Vivek Madan address this complexity by providing "book" proofs—solutions so simple and elegant they belong in a definitive textbook. Their algorithms achieve 2-approximation for Directed Multiway Cut (DIR-MC) and $2(1-1/k)$-approximation for Node-weighted Multiway Cut (NODE-MC). Crucially, these algorithms are fast enough for practical use because they do not require an optimal LP solution; any feasible solution will suffice.
Methods: LP Rounding and Ball-Cutting
The authors employ LP Rounding, a technique where a discrete optimization problem is first solved as a continuous "relaxation" (allowing fractional cuts) and then "rounded" back to a discrete solution.
The LP Relaxation
The core of their approach is a natural distance-based Linear Program (LP). In this relaxation, variables $x_e$ represent the "length" of an edge. The objective is to minimize the total weighted length while ensuring that the distance between any two distinct terminals $s_i$ and $s_j$ is at least 1.
The Rounding Algorithm
The rounding process is remarkably straightforward, utilizing a "ball-cutting" or region-growing approach. For DIR-MC, the algorithm picks a random radius $\theta \in (0, 1)$ and cuts all edges that exit a "ball" of that radius around the terminals.
A key innovation is that this rounding works for any feasible solution to the LP. This is a significant departure from previous methods that required finding an absolute optimal solution. By allowing for near-optimal solutions, the authors can leverage fast multicommodity flow solvers to achieve near-linear end-to-end runtimes.
Key Insights and Results
The paper provides several theoretical and practical breakthroughs:
- Algorithmic Simplicity: By reducing the problem to a ball-cutting approach, the authors demonstrate that the directed case is not as fundamentally different from the undirected case as previously thought.
- Speed: The DIR-MC algorithm achieves a 2-approximation in $O(m + n \log n)$ time. The authors also provide a deterministic version that runs in $O(m \log n)$.
- Integrality Gap: The authors prove that the integrality gap of their LP relaxation is exactly 2, even for directed planar graphs with $k=2$. This suggests that a 2-approximation may be the best possible result for this specific LP formulation.
- Dual Relationship: The dual of the LP relaxation is a special case of the maximum multicommodity flow problem. This connection is what enables the use of high-performance flow algorithms to find feasible solutions quickly.
Conclusion and Future Work
This work simplifies two classic problems in graph theory, replacing complex procedures with intuitive, fast algorithms. However, the "factor of 2" barrier remains. While undirected edge-weighted cuts have been approximated to within a factor of ~1.29, it is still an open question whether DIR-MC can be improved beyond a factor of 2. Additionally, while the theoretical speedups are clear, future empirical studies could compare these algorithms against traditional methods in real-world applications like network routing or image segmentation.
Summary updated