Greedy approximation algorithms for directed multicuts

directed graph G = (V,E) with positive capacities ue on the edges, and a set K ⊆ V × V of ordered pairs of nodes of G, find a minimum capacity K-multicut; C ⊆ E is a K-multicut if in G − C there is no (s, t)-path for any (s, t) ∈ K. In the uncapacitated case (UDM) the goal is to find a minimum size K-multicut. The best approxi-mation ratio known for DM is O(min{√n,opt}) by Gupta, where n = |V |, and opt is the optimal solution value. All known nontrivial approximation algorithms for the problem solve large linear programs. We give the first combinatorial approximation algorithms for the prob-lem. Our main result is an Õ(n2/3/opt1/3)-approximation algorithm for UDM, which improves the O(min{opt,√n})-approximation for opt = (n1/2+ε). Combined with the article of Gupta, we get that UDM can be approximated within better than O( n), unless opt = ̃(√n). We also give a simple and fast O(n2/3)-approximation algorith