Approximating the k-Multicut Problem

We study the k-multicut problem: Given an edgeweighted undirected graph, a set of l pairs of vertices, and a target k ≤ l, find the minimum cost set of edges whose removal disconnects at least k pairs. This generalizes the well known multicut problem, where k = l. We show that the k-multicut problem on trees can be approximated within a factor of 8 3 + , for any fixed > 0, and within O(log2 n log log n) on general graphs, where n is the number of vertices in the graph. For any fixed > 0, we also obtain a polynomial time algorithm for k-multicut on trees which returns a solution of cost at most (2 + ) · OPT, that separates at least (1 − ) · k pairs, where OPT is the cost of the optimal solution separating k pairs. Our techniques also give a simple 2-approximation algorithm for the multicut problem on trees using total unimodularity, matching the best known algorithm [8]. 1 I