<p>Given an undirected graph $G = (V, E)$ and an integer $k$, the well-known minimum (edge) $k$-cut problem asks to find $E' \subseteq E$ with minimum $|E'|$ that the graph $(V, E \setminus E')$ has at least $k$ connected components. </p>

<p>We can similarly define the minimum vertex $k$-cut problem: find $V' \subseteq V$ with minimum $|V'|$ such that the subgraph induced by $V \setminus V'$ has at least $k$ connected components. </p>

<p>There is a slight difference between the edge and the vertex version: for the edge version, a feasible solution $E'$ exists iff $|V| \geq k$, but for the vertex version, a feasible solution $V'$ exists iff $G$ has an independent set of size $k$. Therefore, if $k$ is part of input, for the vertex version, even finding a feasible solution is NP-hard. For the edge version, it is NP-hard to find the minimum solution, but we can get a good (&lt;2)-approximation.</p>

<p>My main question is when $k \geq 3$ is a fixed constant (of course when $k = 2$ both vertex and edge versions can be easily solved). For the edge version, the following paper by Goldschmidt and Hochbaum shows that the minimum $E'$ can be found in time $O(n^{k^2})$. </p>

<p><a href="https://www.computer.org/csdl/proceedings/focs/1988/0877/00/021960.pdf">https://www.computer.org/csdl/proceedings/focs/1988/0877/00/021960.pdf</a></p>

<p>What is the complexity of computing the minimum vertex $k$-cut when $k$ is a fixed constant? Currently I do not know the answer for $k = 3$.</p>

CC BY-SA 3.0
2016-06-09T19:03:36.957Z
This appears to be an open problem. You may find the following useful. Xiao considered the minimum 3-way cut problem in hypergraphs and showed that it is in P. http://www.sciencedirect.com/science/article/pii/S0020019010001183 This was further generalized to 3-way partitioning of submodular set functions. http://link.springer.com/article/10.1007/s00453-010-9483-0
Chandra Chekuri
CC BY-SA 4.0
2021-09-08T20:38:38.853Z
This is an update: The OP proved that the problem is NP-Hard for k=3 in the paper https://link.springer.com/article/10.1007/s10107-018-1270-8. The hypergraph case admits a poly-time algorithm for all fixed k. https://arxiv.org/abs/2009.12442
Chandra Chekuri
<graph-algorithms><max-flow-min-cut><multicommodity-flow>
Minimum vertex k-cut
E. Lee
# Minimum vertex k-cut

(Asked by: username_0 on 2016-06-06)

Given an undirected graph $G = (V, E)$ and an integer $k$, the well-known minimum (edge) $k$-cut problem asks to find $E' \subseteq E$ with minimum $|E'|$ that the graph $(V, E \setminus E')$ has at least $k$ connected components.

We can similarly define the minimum vertex $k$-cut problem: find $V' \subseteq V$ with minimum $|V'|$ such that the subgraph induced by $V \setminus V'$ has at least $k$ connected components.

There is a slight difference between the edge and the vertex version: for the edge version, a feasible solution $E'$ exists iff $|V| \geq k$, but for the vertex version, a feasible solution $V'$ exists iff $G$ has an independent set of size $k$. Therefore, if $k$ is part of input, for the vertex version, even finding a feasible solution is NP-hard. For the edge version, it is NP-hard to find the minimum solution, but we can get a good (<2)-approximation.

My main question is when $k \geq 3$ is a fixed constant (of course when $k = 2$ both vertex and edge versions can be easily solved). For the edge version, the following paper by Goldschmidt and Hochbaum shows that the minimum $E'$ can be found in time $O(n^{k^2})$.

<https://www.computer.org/csdl/proceedings/focs/1988/0877/00/021960.pdf>

What is the complexity of computing the minimum vertex $k$-cut when $k$ is a fixed constant? Currently I do not know the answer for $k = 3$.

**Tags:** graph-algorithms, max-flow-min-cut, multicommodity-flow
> **Comments:**
> **username_1**: This appears to be an open problem. You may find the following useful. Xiao considered the minimum 3-way cut problem in hypergraphs and showed that it is in P. http://www.sciencedirect.com/science/article/pii/S0020019010001183 This was further generalized to 3-way partitioning of submodular set functions. http://link.springer.com/article/10.1007/s00453-010-9483-0  
> **username_1**: This is an update: The OP proved that the problem is NP-Hard for k=3 in the paper https://link.springer.com/article/10.1007/s10107-018-1270-8. The hypergraph case admits a poly-time algorithm for all fixed k. https://arxiv.org/abs/2009.12442  

---

## 0 answers

