Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
✍ Scribed by Venkatesan Guruswami; Sanjeev Khanna; Rajmohan Rajaraman; Bruce Shepherd; Mihalis Yannakakis
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 308 KB
- Volume
- 67
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
We study the approximability of edge-disjoint paths and related problems. In the edge-disjoint paths (EDP) problem, we are given a network G with source-sink pairs ðs i ; t i Þ; 1pipk; and the goal is to find a largest subset of source-sink pairs that can be simultaneously connected in an edge-disjoint manner. We show that in directed networks, for any e40; EDP is NP-hard to approximate within m 1=2Àe : We also design simple approximation algorithms that achieve essentially matching approximation guarantees for some generalizations of EDP. Another related class of routing problems that we study concerns EDP with the additional constraint that the routing paths be of bounded length. We show that, for any e40; bounded length EDP is hard to approximate within m 1=2Àe even in undirected networks, and give an Oð ffiffiffiffi m p Þ-approximation algorithm for it. For directed networks, we show that even the single source-sink pair case (i.e. find the maximum number of paths of bounded length between a given source-sink pair) is hard to approximate within m 1=2Àe ; for any e40: