<p>In the <em>multiterminal cut</em> the input is a graph $G$ and a subset $T$ of its vertices. The task is to remove the minimum number of edges from $G$ such that there is no path connecting any distinct vertices of $T$. The problem is APX-hard, even when $T$ has 3 vertices. This was shown in by Dalhaus et al (E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, M. Yannakakis: The Complexity of Multiterminal Cuts. SIAM J. Comput. 23(4): 864-894, 1994.) </p>

<p>I am interested in the actual value $\alpha&gt;1$ such that no $(\alpha-\varepsilon)$-approximation is possible for multiterminal cut, unless P=NP. A quick adaptation of the reduction used by Dalhaus et al. for general $T$ implies $\alpha=89/88$. (For $|T|=3$ the constant is worse, but I am interested in arbitrary $|T|$.)</p>

<p>My question is: has there been any improvement over Dalhaus et al for the inapproximability of multiterminal cut? Are there other NP-hardness proofs of multiterminal cut in the literature?</p>

<p>Since there are constant-factor approximations for the problem, the question here is about constants. </p>

CC BY-SA 3.0
2012-02-16T00:32:37.517Z
The following paper is relevant http://dl.acm.org/citation.cfm?id=1374379. They give UGC hardness results that match the integrality gap of an LP relaxation but these results hold only for fixed number of terminals. However, the reductions may be useful.
Chandra Chekuri
CC BY-SA 4.0
2018-08-18T15:19:45.567Z
@ChandraChekuri, [as of 2018] http://arxiv.org/abs/1611.05530 seems to give (assuming UGC) a lower bound of $\frac{6}{5+1/(k−1)}$ for $k$ terminals, which (as $\alpha$ is at least the lower bound for any fixed $k$) would imply a lower bound of $\alpha \ge 6/5=1.2$ for the general case. And it looks like this was improved (using just $k=4$?) to 1.20016 in https://arxiv.org/abs/1807.09735.  FWIW they state that the best poly-time upper bound known is 1.2965.
Neal Young
<cc.complexity-theory><reference-request><graph-algorithms><approximation-hardness>
Inapproximability of multiterminal cut
someone
# Inapproximability of multiterminal cut

(Asked by: username_0 on 2012-02-15)

In the *multiterminal cut* the input is a graph $G$ and a subset $T$ of its vertices. The task is to remove the minimum number of edges from $G$ such that there is no path connecting any distinct vertices of $T$. The problem is APX-hard, even when $T$ has 3 vertices. This was shown in by Dalhaus et al (E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, M. Yannakakis: The Complexity of Multiterminal Cuts. SIAM J. Comput. 23(4): 864-894, 1994.)

I am interested in the actual value $\alpha>1$ such that no $(\alpha-\varepsilon)$-approximation is possible for multiterminal cut, unless P=NP. A quick adaptation of the reduction used by Dalhaus et al. for general $T$ implies $\alpha=89/88$. (For $|T|=3$ the constant is worse, but I am interested in arbitrary $|T|$.)

My question is: has there been any improvement over Dalhaus et al for the inapproximability of multiterminal cut? Are there other NP-hardness proofs of multiterminal cut in the literature?

Since there are constant-factor approximations for the problem, the question here is about constants.

**Tags:** cc.complexity-theory, reference-request, graph-algorithms, approximation-hardness

> **Comments:**
> **username_1**: The following paper is relevant http://dl.acm.org/citation.cfm?id=1374379. They give UGC hardness results that match the integrality gap of an LP relaxation but these results hold only for fixed number of terminals. However, the reductions may be useful.  
> **username_2**: @ChandraChekuri, [as of 2018] http://arxiv.org/abs/1611.05530 seems to give (assuming UGC) a lower bound of $\frac{6}{5+1/(k−1)}$ for $k$ terminals, which (as $\alpha$ is at least the lower bound for any fixed $k$) would imply a lower bound of $\alpha \ge 6/5=1.2$ for the general case. And it looks like this was improved (using just $k=4$?) to 1.20016 in https://arxiv.org/abs/1807.09735.  FWIW they state that the best poly-time upper bound known is 1.2965.  

---

## 0 answers

