## Abstract

We consider the k-Directed Steiner Forest (k-DSF) problem: Given a directed graph G=(V,E) with edge costs, a collection D V×V of ordered node pairs, and an integer k≤|D|, find a minimum cost subgraph H of G that contains an st-path for (at least) k pairs (s,t) D. When k=|D|, we get the Directed Steiner Forest (DSF) problem. The best known approximation ratios for these problems are: Õ(k2^{/3}) for k-DSF by Charikar et al. (1999) [6], and O(k1^{/2+ε}) for DSF by Chekuri et al. (2008) [7]. Our main result is achieving the first sub-linear in terms of n=|V| approximation ratio for DSF. Specifically, we give an O(^{nε}.min{n4^{/5},m2 ^{/3}})-approximation scheme for DSF. For k-DSF we give a simple greedy O(k1^{/2+ε})-approximation algorithm. This improves upon the best known ratio Õ(k2^{/3}) by Charikar et al. (1999) [6], and (almost) matches, in terms of k, the best ratio known for the undirected variant (Gupta et al., 2010 [18]). This algorithm uses a new structure called start-junction tree which may be of independent interest.

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

Pages (from-to) | 279-292 |

Number of pages | 14 |

Journal | Journal of Computer and System Sciences |

Volume | 78 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2012 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics

## Keywords

- Approximation algorithm
- Directed Steiner Forest