1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Yes, it is APX-hard. A proof by Demaine et al. is published here.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .