Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut

Chandra Chekuri, Vivek Madan

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 natural distance-based LP relaxation (DIR-MC-REL) used for Directed Multiway Cut.

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.

The simple randomized rounding algorithm for Directed Multiway Cut.

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

Abstract

In Directed Multiway Cut(Dir-MC) the input is an edge-weighted directed graph $G=(V,E)$ and a set of $k$ terminal nodes $\{s_1,s_2,\ldots,s_k\} \subseteq V$; the goal is to find a min-weight subset of edges whose removal ensures that there is no path from $s_i$ to $s_j$ for any $i \neq j$. In Node-weighted Multiway Cut(Node-MC) the input is a node-weighted undirected graph $G$ and a set of $k$ terminal nodes $\{s_1,s_2,\ldots,s_k\} \subseteq V$; the goal is to remove a min-weight subset of nodes to disconnect each pair of terminals. Dir-MC admits a $2$-approximation [Naor, Zosin '97] and Node-MC admits a $2(1-\frac{1}{k})$-approximation [Garg, Vazirani, Yannakakis '94], both via rounding of LP relaxations. Previous rounding algorithms for these problems, from nearly twenty years ago, are based on careful rounding of an "optimum" solution to an LP relaxation. This is particularly true for Dir-MC for which the rounding relies on a custom LP formulation instead of the natural distance based LP relaxation [Naor, Zosin '97]. In this paper we describe extremely simple and near linear-time rounding algorithms for Dir-MC and Node-MC via a natural distance based LP relaxation. The dual of this relaxation is a special case of the maximum multicommodity flow problem. Our algorithms achieve the same bounds as before but have the significant advantage in that they can work with "any feasible" solution to the relaxation. Consequently, in addition to obtaining "book" proofs of LP rounding for these two basic problems, we also obtain significantly faster approximation algorithms by taking advantage of known algorithms for computing near-optimal solutions for maximum multicommodity flow problems. We also investigate lower bounds for Dir-MC when $k=2$ and in particular prove that the integrality gap of the LP relaxation is $2$ even in directed planar graphs.
BibTeX
@inproceedings{chekuri2016simple,
  author = {Chandra Chekuri and Vivek Madan},
  title = {{Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut}},
  booktitle = {SODA},
  year = {2016},
  url = {https://openreview.net/forum?id=i9igZev8gk},
}
Figure