For each fixed $k \geq 3$, the following well-known problem is NP-complete.

k-Multicut (aka "Multiway Cut", "k-Way Cut", "Multicut")

  • Input: $(N,l)$ where $N=(V,E,T,c)$ is an undirected $k$-terminal network with nodes $V$, edges $E$, terminals $T \subseteq V$ with $|T|=k$, a capacity function $c$ and a positive integer $l$.
  • Question: Is there set $E' \subseteq E$ that separates each pair of terminals from each other such that $\sum_{e \in E'} c(e) \leq l$?

I only consider $k=3$ from now on, so let the set of terminals be $T = \{t_1,t_2,t_3\}$. The minimum conceivable capacity possible for a multicut in a given 3-terminal network $N$ is $\frac{c_1+c_2+c_3}{2}$, where $c_i$ is the capacity of a min-cut separating $t_i$ from the other two terminals in $N$. I wonder what the complexity is to decide whether a given network allows a multicut of this minimum capacity.

Formally, I would like to know the complexity of:

Minimum 3-Multicut

  • Input: A 3-terminal network $N$.
  • Question: Is $\left(N,\frac{c_1+c_2+c_3}{2}\right) \in \textrm{3-Multicut}$?

While this problem clearly is in NP, it is not clear whether this problem is in P since each single terminal can be separated from the other two terminals by up to exponentially in $|V|$ many min-cuts. On the other side, a promising candidate for a reduction to show NP-hardness is k-Multicut. However, it is not clear how such a reduction might work.

  • $\begingroup$ Cygan et al. ( arxiv.org/abs/1107.1585 ) studied parameterized algorithms Multiway Cut and considered various "above-guarantee" parameterizations. It may be that your minimum conceivable capacity is related to their lower bounds. As they show that the question "is there a multiway cut of size lowerbound + k" can be solved in f(k) * n^c time on n-vertex graphs for some fixed constant c, this might resolve your question. $\endgroup$ – Bart Jansen Nov 12 '15 at 7:59

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.