Approximating the k-multicut problem

We study the k-multicut problem: Given an edge-weighted 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(log² 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].