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.

  • 5
    $\begingroup$ The following paper is relevant 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. $\endgroup$ – Chandra Chekuri Feb 16 '12 at 0:32
  • $\begingroup$ @ChandraChekuri, [as of 2018] 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 arxiv.org/abs/1807.09735. FWIW they state that the best poly-time upper bound known is 1.2965. $\endgroup$ – Neal Young Aug 18 '18 at 15:19

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.