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)](http://link.springer.com/article/10.1007%2FBF01581239), is sometimes called Minimum Cost Multicut, although the term is used also for different problems in the literature (e.g. [this](http://www.nada.kth.se/~viggo/wwwcompendium/node93.html) problem with terminals and positive edge weights).


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



Is it known whether Minimum Cost Multicut is APX-hard?
Yes, it is APX-hard. A proof by Demaine et al. is published [here](http://www.sciencedirect.com/science/article/pii/S0304397506003227).


