1
$\begingroup$

Multicuts or multiway cuts are (edge) cuts of minimum capacity that separate each pair of a set of terminals (a subset of the entire node set). For two terminals, this is the classical $s$-$t$ mincut problem. For $k \geq 3$ terminals, the problem becomes NP-hard.

Such a multicut may or may not be composed of mincuts that isolate each single terminal from the others (in case of $k=3$, 2 isolating cuts suffice to separate all pairs). I am interested in a multicut variant, where the multicut needs to be composed of such mincuts (one for each terminal). I call such a multicut a mincut-multicut (do you know a better name?).

Problem Mincut-Multicut:

Input: An undirected graph $G=(V,E)$, an edge capacity function $c:E \to \mathbb{N}$, a set $T=\{t_1, t_2, \dots t_l\} \subseteq V$ of $l \geq 2$ terminals and a number $k$ (all in binary).

Question: Is there a set $E' \subseteq E$ such that $E' = E_1 \cup E_2 \cup \dots \cup E_l$ where each $E_i$ is a $t_i$ isolating mincut, such that $\sum_{e \in E'} c(e) \leq k$?

Certainly, the capacity of such a mincut-multicut may be greater than of a conventional multicut, but not smaller. For each terminal, there may be an exponential number of mincuts isolating it from the others. For each terminal, we need to choose one of these exponentially many in order to compose the multicut.

If we can choose single terminal isolating mincuts such that the combination of them partitions the set of all nodes into $k$ sets (one for each terminal), we have found a mincut multicut of minimum capacity. It seems, however, quite challenging to determine whether such a mincut multicut exists.

Question: Is anything known about this problem or do you have any suggestions concerning its complexity?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.