## Abstract

The Directed Multicut (DM) problem is: given a simple directed graph G = (V, E) with positive capacities u_{e} 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 every (s, t) ∈ K. In the uncapacitated case (UDM) the goal is to find a minimum size K-multicut. The best approximation ratio known for DM is min{O(√n),opt} by Anupam Gupta [5], where n = |V|, and opt is the optimal solution value. All known non-trivial approximation algorithms for the problem solve large linear programs. We give the first combinatorial approximation algorithms for the problem. Our main result is a Ō(n^{2/3}/opt^{1/3})- approximation algorithm for UDM, which improves the √n-approximation for opt = Ω(n^{1/2+ε}). Combined with the paper of Gupta [5], we get that UDM can be approximated within better than O(√n), unless opt = Θ̃(√n). We also give a simple and fast O(n^{2/3})- approximation algorithm for DM.

Original language | English (US) |
---|---|

Pages (from-to) | 61-67 |

Number of pages | 7 |

Journal | Lecture Notes in Computer Science |

Volume | 3351 |

DOIs | |

State | Published - 2005 |

Event | Second International Workshop on Approximation and Online Algorithms, WAOA 2004 - Bergen, Norway Duration: Sep 14 2004 → Sep 16 2004 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- General Computer Science