<p>Let <span class="math-container">$G$</span> be an undirected graph, <span class="math-container">$\{(s_1,t_1),\dots,(s_k,t_k)\}$</span> a collection of pairs of vertices, and <span class="math-container">$p$</span> an integer. The <strong>Vertex Multicut</strong> problem asks if there is a set <span class="math-container">$S$</span> of at most <span class="math-container">$p$</span> vertices such that the removal of <span class="math-container">$S$</span> disconnects every <span class="math-container">$s_i$</span> from every <span class="math-container">$t_i$</span>.</p>
<p>Now, let <span class="math-container">$\{t_1,\dots,t_\ell\}$</span> be a collection of terminals of <span class="math-container">$G$</span>. The <strong>Vertex Multiway Cut</strong> problem asks if there is a set <span class="math-container">$S$</span> of at most <span class="math-container">$p$</span> vertices such that the removal of <span class="math-container">$S$</span> disconnects every pair of terminals in the collection.
It is easily seen that the two problems are distinct. In multicut, a set <span class="math-container">$S$</span> whose removal from <span class="math-container">$G$</span> results in two connected components: <span class="math-container">$C_s$</span> containing <span class="math-container">$\{s_1,\dots, s_k\}$</span>, and <span class="math-container">$C_t$</span> containing <span class="math-container">$\{t_1,\dots,t_k\}$</span> where <span class="math-container">$C_s\neq C_t$</span>, is considered a solution.</p>
<p>In many papers it is mentioned that Vertex Multicut is NP-hard for every fixed <span class="math-container">$k\geq 3$</span>, usually referring to [1]. However, this paper proves that Multiway-cut is NP-hard for <span class="math-container">$k\geq 3$</span>.</p>
<p>Are there any results on the complexity of multicut parameterized by the number of pairs (these are sometimes referred to as &quot;requests&quot;)?</p>
<p>It would seem that a straightforward algorithm would do the following:
There are two options for every one of the <span class="math-container">$k$</span> pairs <span class="math-container">$(s_i,t_i)$</span>: assign <span class="math-container">$s_i$</span> to set <span class="math-container">$A$</span> and <span class="math-container">$t_i$</span> to set <span class="math-container">$B$</span>, or vice versa. Then, find the minimum <span class="math-container">$A-B$</span> separator in <span class="math-container">$G$</span>. Do this for every possible partition to sets <span class="math-container">$A$</span> and <span class="math-container">$B$</span>. This gives a total of <span class="math-container">$2^k$</span> executions of the algorithm for finding a minimum <span class="math-container">$A-B$</span> vertex separator.</p>
<p>Would really like to understand what I am missing...</p>
<p>[1] <em>Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M.</em>, <a href="http://dx.doi.org/10.1137/S0097539792225297" rel="nofollow noreferrer"><strong>The complexity of multiterminal cuts</strong></a>, SIAM J. Comput. 23, No. 4, 864-894 (1994). <a href="https://zbmath.org/?q=an:0809.68075" rel="nofollow noreferrer">ZBL0809.68075</a>.
These, however, refer to the multiway cut problem, and not the multicut problem.</p>

CC BY-SA 4.0
2022-04-11T07:40:42.337Z
I think you are misunderstanding the definition of multiway cut. In multiway cut, we have a set of terminals $T$ and are required to find a set $S$ so that after removing $S$, all terminals are in different components. In particular, note that multiway cut with three terminals can be reduced to multicut with three pairs.
Laakeri
CC BY-SA 4.0
2022-04-11T08:25:27.000Z
Thanks for the clarification! 
Consider a restricted setting in which the pairs in the input for the multicut problem are distinct. That is, if the collection is $(s_1,t_1),\dots,(s_k,t_k)$, then for all $i\neq j$, it holds that $\{s_i,t_i\}\cap \{s_j,t_j\}=\emptyset$. In that case, would the simple algorithm I suggested work ? Is there something else known about such a restricted setting ?
BBK
CC BY-SA 4.0
2022-04-11T10:04:53.957Z
No it would not work. And this setting is actually not restricted, we can assume that the property holds in general case by making copies of the terminals.
Laakeri
CC BY-SA 4.0
2022-04-11T12:50:28.157Z
The only way you can reduce multiway cut with 3 terminals $(a,b,c)$ to multicut is by setting the pairs to be $\{(a,b),(a,c),(b,c)\}$. So, at least one of the terminals has to belong to more than one pair. How can the more restricted case I described be reduced to multiway cut ?
BBK
CC BY-SA 4.0
2022-04-12T07:40:06.857Z
When you replace each of the three terminals $a$, $b$, and $c$ by a clique of size $p+2$, then one can cannot separate the copies with the budget of $p$  and thus one may use a different copy of the terminal for each pair. The misunderstanding seems to be that there is an optimal solution that may not be consistent with any of the branching choices.
Christian Komusiewicz
CC BY-SA 4.0
2022-05-24T04:22:06.980Z
When the number of pairs is considered a constant then the problem where the terminal vertices are *not deletable* is at least as hard as the edge deletion problem (by the reductions outlined in other comments). If terminals are deletable then there is a simple poly time brute force algorithm -- is this perhaps what was causing your confusion?
daniello
<graph-algorithms><optimization><parameterized-complexity><fixed-parameter-tractable>
Parameterized Complexity of Vertex Multicut
BBK
# Parameterized Complexity of Vertex Multicut

(Asked by: username_0 on 2022-04-11)

Let $G$ be an undirected graph, $\{(s\_1,t\_1),\dots,(s\_k,t\_k)\}$ a collection of pairs of vertices, and $p$ an integer. The **Vertex Multicut** problem asks if there is a set $S$ of at most $p$ vertices such that the removal of $S$ disconnects every $s\_i$ from every $t\_i$.

Now, let $\{t\_1,\dots,t\_\ell\}$ be a collection of terminals of $G$. The **Vertex Multiway Cut** problem asks if there is a set $S$ of at most $p$ vertices such that the removal of $S$ disconnects every pair of terminals in the collection.
It is easily seen that the two problems are distinct. In multicut, a set $S$ whose removal from $G$ results in two connected components: $C\_s$ containing $\{s\_1,\dots, s\_k\}$, and $C\_t$ containing $\{t\_1,\dots,t\_k\}$ where $C\_s\neq C\_t$, is considered a solution.

In many papers it is mentioned that Vertex Multicut is NP-hard for every fixed $k\geq 3$, usually referring to [1]. However, this paper proves that Multiway-cut is NP-hard for $k\geq 3$.

Are there any results on the complexity of multicut parameterized by the number of pairs (these are sometimes referred to as "requests")?

It would seem that a straightforward algorithm would do the following:
There are two options for every one of the $k$ pairs $(s\_i,t\_i)$: assign $s\_i$ to set $A$ and $t\_i$ to set $B$, or vice versa. Then, find the minimum $A-B$ separator in $G$. Do this for every possible partition to sets $A$ and $B$. This gives a total of $2^k$ executions of the algorithm for finding a minimum $A-B$ vertex separator.

Would really like to understand what I am missing...

[1] *Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M.*, [**The complexity of multiterminal cuts**](http://dx.doi.org/10.1137/S0097539792225297), SIAM J. Comput. 23, No. 4, 864-894 (1994). [ZBL0809.68075](https://zbmath.org/?q=an:0809.68075).
These, however, refer to the multiway cut problem, and not the multicut problem.

**Tags:** graph-algorithms, optimization, parameterized-complexity, fixed-parameter-tractable
> **Comments:**
> **username_1**: I think you are misunderstanding the definition of multiway cut. In multiway cut, we have a set of terminals $T$ and are required to find a set $S$ so that after removing $S$, all terminals are in different components. In particular, note that multiway cut with three terminals can be reduced to multicut with three pairs.  
> **username_0**: Thanks for the clarification!  Consider a restricted setting in which the pairs in the input for the multicut problem are distinct. That is, if the collection is $(s_1,t_1),\dots,(s_k,t_k)$, then for all $i\neq j$, it holds that $\{s_i,t_i\}\cap \{s_j,t_j\}=\emptyset$. In that case, would the simple algorithm I suggested work ? Is there something else known about such a restricted setting ?  
> **username_1**: No it would not work. And this setting is actually not restricted, we can assume that the property holds in general case by making copies of the terminals.  
> **username_0**: The only way you can reduce multiway cut with 3 terminals $(a,b,c)$ to multicut is by setting the pairs to be $\{(a,b),(a,c),(b,c)\}$. So, at least one of the terminals has to belong to more than one pair. How can the more restricted case I described be reduced to multiway cut ?  
> **username_2**: When you replace each of the three terminals $a$, $b$, and $c$ by a clique of size $p+2$, then one can cannot separate the copies with the budget of $p$  and thus one may use a different copy of the terminal for each pair. The misunderstanding seems to be that there is an optimal solution that may not be consistent with any of the branching choices.  
> **username_3**: When the number of pairs is considered a constant then the problem where the terminal vertices are *not deletable* is at least as hard as the edge deletion problem (by the reductions outlined in other comments). If terminals are deletable then there is a simple poly time brute force algorithm -- is this perhaps what was causing your confusion?  

---

## 0 answers

