# The Complexity of Multiterminal Cuts

@article{Dahlhaus1994TheCO, title={The Complexity of Multiterminal Cuts}, author={Elias Dahlhaus and David S. Johnson and Christos H. Papadimitriou and Paul D. Seymour and Mihalis Yannakakis}, journal={SIAM J. Comput.}, year={1994}, volume={23}, pages={864-894} }

In the multiterminal cut problem one is given an edge-weighted graph and a subset of the vertices called terminals, and is asked for a minimum weight set of edges that separates each terminal from all the others. When the number $k$ of terminals is two, this is simply the mincut, max-flow problem, and can be solved in polynomial time. It is shown that the problem becomes NP-hard as soon as $k=3$, but can be solved in polynomial time for planar graphs for any fixed $k$. The planar problem is NP… Expand

#### Figures and Topics from this paper

#### 656 Citations

Parameterized Algorithm for the Multiterminal Cut Problem Yixin Cao

- 2017

We study the multiterminal cut problem, which, given an n-vertex graph whose edges are integer-weighted and a set of terminals, asks for a partition of the vertex set such that each terminal is in a… Expand

Solving (k-1)-Stable Instances of k-terminal cut with Isolating Cuts

- Computer Science, Mathematics
- COCOA
- 2019

This paper concludes that the $(2-2/k)-approximation algorithm returns the optimal solution on $(k-1)$-stable instances of the k-Terminal Cut problem, and is the first result showing that this $(1-1-\epsilon)- approximation is an exact optimization algorithm on a special class of graphs. Expand

Simple and Improved Parameterized Algorithms for Multiterminal Cuts

- Mathematics, Computer Science
- Theory of Computing Systems
- 2009

This paper designs several simple and improved algorithms for Multiterminal Cut, based on a notion farthest minimum isolating cut, and shows that Edge MultiterMinal Cut can be solved in O(2lkT(n,m)) time and Vertex Multiter Minal CutCan be solvedIn O(klT( n,m) time, where T(n),m)=O(min (n2/3,m1/2)m). Expand

An O *(1.84 k ) Parameterized Algorithm for the Multiterminal Cut Problem

- Mathematics, Computer Science
- FCT
- 2013

We study the multiterminal cut problem, which, given an n-vertex graph whose edges are integer-weighted and a set of terminals, asks for a partition of the vertex set such that each terminal is in a… Expand

The Maximum Integer Multiterminal Flow Problem

- Mathematics, Computer Science
- ICCSA
- 2006

For directed graphs, a new parameter kL ≤ k is introduced and it is proved that MaxIMTF is $\mathcal{NP}$-hard when k = kL = 2 and when k l = 1 and k = 3, and polynomial-time solvable when k L = 0 and when l = 2. Expand

An O(1.84k) parameterized algorithm for the multiterminal cut problem

- Mathematics, Computer Science
- Inf. Process. Lett.
- 2014

We study the multiterminal cut problem, which, given an n-vertex graph whose edges are integer-weighted and a set of terminals, asks for a partition of the vertex set such that each terminal is in a… Expand

Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals

- Mathematics
- 2015

Given an undirected, edge-weighted graph G together with pairs of vertices, called pairs of terminals, the minimum multicut problem asks for a minimum-weight set of edges such that, after deleting… Expand

Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals

- Computer Science
- ESA
- 2015

A polynomial-time algorithm is provided for the minimum multicut problem, which asks for a minimum-weight set of edges such that, after deleting these edges, the two terminals of each pair belong to different connected components of the graph. Expand

Algorithms for Multiterminal Cuts

- Mathematics, Computer Science
- CSR
- 2008

Based on a notion farthest minimum isolating cut, some properties for Multiterminal Cuts are presented, which help shed light on the structure of optimal cut problems, and enables us to design efficient algorithms for Multitecuts, as well as some other related cut problems. Expand

An improved approximation algorithm for multiway cut

- Mathematics, Computer Science
- STOC '98
- 1998

A new linear programming relaxation for Multiway Cut is presented and a new approximation algorithm based on it achieves a performance ratio of at most 1.5?1k, which improves the previous result for every value of k. Expand

#### References

SHOWING 1-10 OF 38 REFERENCES

The complexity of multiway cuts (extended abstract)

- Mathematics, Computer Science
- STOC '92
- 1992

It is shown that the Multiway Cut problem becomes NP-hard as soon as k = 3, but can be solved in polynomial time for planar graphs for any fixed <italic>k</italic>, and a simple approximation algorithm is described that is guaranteed to come within a factor of 2–2/k of the optimal cut weight. Expand

Some Simplified NP-Complete Graph Problems

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1976

This paper shows that a number of NP - complete problems remain NP -complete even when their domains are substantially restricted, and determines essentially the lowest possible upper bounds on node degree for which the problems remainNP -complete. Expand

Polynomial algorithm for the k-cut problem

- Mathematics, Computer Science
- [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science
- 1988

A polynomial algorithm for the case of a fixed k, to find a partition of an edge weighted graph into k nonempty components, such that the total edge weight between components is minimum. Expand

Evolutionary trees: An integer multicommodity max-flow-min-cut theorem

- Mathematics
- 1992

In biomathematics, the extensions of a leaf-colouration of a binary tree to the whole vertex set with minimum number of colour-changing edges are extensively studied. Our paper generalizes the… Expand

On the multiway cut polyhedron

- Mathematics, Computer Science
- Networks
- 1991

An integer programming formulation of the problem of finding a minimum-weight multiway cut that separates each pair of nodes in N and study the associated polyhedron is given. Expand

The ellipsoid method and its consequences in combinatorial optimization

- Mathematics, Computer Science
- Comb.
- 1981

The method yields polynomial algorithms for vertex packing in perfect graphs, for the matching and matroid intersection problems, for optimum covering of directed cuts of a digraph, and for the minimum value of a submodular set function. Expand

Planar Formulae and Their Uses

- Mathematics, Computer Science
- SIAM J. Comput.
- 1982

Using these results, it is able to provide simple and nearly uniform proofs of NP-completeness for planar node cover, planar Hamiltonian circuit and line, geometric connected dominating set, and of polynomial space completeness forPlanar generalized geography. Expand

Finding k-cuts within twice the optimal

- Mathematics, Computer Science
- [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science
- 1991

Two simple approximation algorithms are presented for the minimum k-cut problem, requiring a total of only n-1 maximum flow computations for finding a set of near-optimal k-cuts. Expand

A new approach to the maximum-flow problem

- Mathematics, Computer Science
- JACM
- 1988

An alternative method based on the preflow concept of Karzanov, which runs as fast as any other known method on dense graphs, achieving an O(n) time bound on an n-vertex graph and faster on graphs of moderate density. Expand

Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications

- Computer Science, Mathematics
- SIAM J. Comput.
- 1996

The proof technique provides a unified framework in which one can also analyse the case of flows with specified demands of Leighton and Rao and Klein et al. and thereby obtain an improved bound for the latter problem. Expand