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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.