zbMATH — the first resource for mathematics

Algorithms for multiterminal cuts. (English) Zbl 1142.68462
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 314-325 (2008).
Summary: Given a graph $$G = (V,E)$$ with $$n$$ vertices and $$m$$ edges, and a subset $$T$$ of $$l$$ vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of $$k$$ edges (non-terminal vertices), whose removal from $$G$$ separates each terminal from all the others. These two problems are NP-hard for $$l \geq 3$$ but well-known to be polynomial-time solvable for $$l = 2$$ by the flow technique. In this paper, we show that Edge Multiterminal Cut is polynomial-time solvable for $$k = O(\log n)$$ by presenting an $$O(2^{k } lT(n,m))$$ algorithm, where $$T(n,m) = O(\min (n ^{2/3},m ^{1/2})m)$$ is the running time of finding a minimum $$(s,t)$$ cut in an unweighted graph. We also give two algorithms for Vertex Multiterminal Cut that run in $$O(l ^{k } T(n,m))$$ time and $$O((k!)^{2} T(n,m))$$ time respectively. The former one indicates that Vertex Multiterminal Cut is solvable in polynomial time for $$l$$ being a constant and $$k = O(\log n)$$, and the latter one improves the best known algorithm of running time $$O(4^{k^3}n^{O(1)})$$. When $$l = 3$$, we show that the running times can be improved to $$O(1.415^{k } T(n,m))$$ for Edge Multiterminal Cut and $$O(2.059^{k } T(n,m))$$ for Vertex Multiterminal Cut. Furthermore, we present a simple idea to solve another important problem Multicut by finding minimum multiterminal cuts. Our algorithms for Multicuts are also faster than the previously best algorithm.
Based on a notion farthest minimum isolating cut, we present some properties for Multiterminal Cuts, which help shed light on the structure of optimal cut problems, and enables us to design efficient algorithms for Multiterminal Cuts, as well as some other related cut problems.
For the entire collection see [Zbl 1136.68005].

MSC:
 68R10 Graph theory (including graph drawing) in computer science 05C85 Graph algorithms (graph-theoretic aspects) 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68Q25 Analysis of algorithms and problem complexity
Full Text: