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

Chandra Chekuri, Vivek Madan

This paper, authored by Chandra Chekuri and Vivek Madan, tackles a fundamental problem in combinatorial optimization: how to efficiently partition a graph to separate multiple "terminal" nodes at minimum cost. While the undirected edge-weighted version of this problem is well-understood, the directed and node-weighted versions have historically required complex, "mysterious" algorithms. This paper strips away that complexity, providing simple, near-linear time algorithms that achieve state-of-the-art approximation bounds.

TL;DR

The authors present "extremely simple" rounding algorithms for Directed Multiway Cut and Node-weighted Multiway Cut that achieve 2-approximation and $2(1-1/k)$-approximation respectively. Unlike previous methods, these algorithms work with any feasible solution to a natural LP relaxation, enabling significantly faster end-to-end performance by using near-optimal multicommodity flow solvers.

What Problem Does This Paper Address?

The Multiway Cut problem asks: 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 basic undirected version is a staple of computer science, two variants are much trickier:

  1. Directed Multiway Cut (DIR-MC): The graph is directed. Separating $s_i$ from $s_j$ doesn't necessarily separate $s_j$ from $s_i$.
  2. Node-Weighted Multiway Cut (NODE-WT-MC): You pay to remove vertices rather than edges.

Previous algorithms for these problems were often "non-intuitive." For DIR-MC, the existing 2-approximation relied on a custom, complex Linear Programming (LP) formulation and required finding an optimal solution to that LP—a computationally expensive task. The authors sought to find "book" proofs: solutions so simple and elegant they belong in a definitive textbook, while also being fast enough for practical use.

Methods

The authors use a technique called LP Rounding. They first solve a "relaxed" version of the problem where you can cut "fractions" of an edge or node (the LP relaxation). Then, they "round" these fractions into a 0-or-1 decision (cut or don't cut).

Their key methodological contributions are:

  • Natural Distance-Based LP: They use a simple LP where variables represent distances. If the distance between two terminals is at least 1, they are separated.
  • Ball-Cutting (Region Growing): The rounding algorithm is remarkably simple. For DIR-MC, they pick a random radius $\theta$ between 0 and 1 and cut all edges that exit a "ball" of that radius around the terminals.
  • Optimality Independence: Most rounding schemes require the absolute best (optimal) fractional solution. This paper proves their rounding works for any feasible solution. This is a huge win for speed, as finding a "good enough" solution is much faster than finding the "perfect" one.

Datasets

As a theoretical computer science paper, no empirical datasets were used. The results are proven mathematically for all possible graphs. The authors provide complexity analysis (Big-O notation) to demonstrate speed.

Key Insights and Ideas

  • The Power of Simplicity: By reducing the problem to a "ball-cutting" approach similar to the one used for simpler undirected cuts, the authors show that the directed case isn't as fundamentally different as previously thought.
  • Dual Relationship: They highlight that the dual of their LP relaxation is a specific case of the maximum multicommodity flow problem. Because there are very fast algorithms to approximate these flows, their rounding scheme can be paired with them to create a very fast approximation pipeline.
  • Integrality Gap of 2: They prove that for Directed Multiway Cut, the "gap" between the fractional solution and the best possible integer solution is exactly 2, even in simple planar graphs. This suggests that a 2-approximation might be the best we can do with this type of LP.

Key Results

  • DIR-MC: Achieved a 2-approximation in $O(m + n \log n)$ time (near-linear). This matches the best known bound but with a much simpler proof and faster execution.
  • NODE-WT-MC: Achieved a $2(1 - 1/k)$-approximation, matching the best known bound while simplifying the rounding process.
  • Deterministic Versions: They provide a way to "derandomize" the algorithms, turning the randomized "pick a radius" step into a guaranteed deterministic process with only a slight increase in runtime ($O(m \log n)$).
  • Hardness Proof: They proved that the $k=2$ case for directed graphs (separating $s$ from $t$ AND $t$ from $s$) is NP-hard and has an integrality gap of 2, distinguishing it from the standard $s-t$ cut which is solvable in polynomial time.

Limitations and Future Work

  • The "Factor of 2" Barrier: While the algorithm is fast, the approximation factor is still 2. In undirected edge-weighted graphs, researchers have pushed the bound down to ~1.29. It remains an open question if DIR-MC can be approximated better than a factor of 2.
  • Hardness Assumptions: The authors raise the question of whether a factor of 2 is "hard" to beat under the Unique Games Conjecture (UGC).
  • Practical Implementation: While the theory suggests these are "fast," the paper does not include an experimental study comparing these to the older, more complex algorithms in real-world network routing or image segmentation tasks.

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},
}

Loading related content...

Figure