Skip to main content
3 of 3
Added top-level tag.
Stefan Kohl
  • 19.6k
  • 21
  • 75
  • 137

Is it known whether Minimum Cost Multicut is APX-hard?

My questions is concerned with the following problem: Given an undirected graph $G = (V, E)$ and (edge costs) $c \in \mathbb{Z}^E$, $$\min \left\{ \sum_{e \in E} c_e x_e\ \middle|\ x \in \{0,1\}^E \ \wedge\ \forall C \in \mathrm{cycles}(G)\ \forall e \in C:\ x_e \leq \!\!\!\!\sum_{e' \in C \setminus \{e\}} \!\! x_{e'} \right\}$$

This problem, studied by Chopra and Rao (1993), is sometimes called Minimum Cost Multicut, although the term is used also for different problems in the literature (e.g. this problem with terminals and positive edge weights).

Is the problem stated above known to be APX-hard?