Abstract

Given a graph G=(V, E) and k source-sink pairs (s 1, t 1), dots, (s k, t k) with each s i, t i in V, the Min-Sum Disjoint Paths problem asks to find k disjoint paths connecting all the source-sink pairs with minimized total length, while the Min-Max Disjoint Paths problem asks for k disjoint paths connecting all the source-sink pairs with minimized length of the longest path. We show that the weighted Min-Sum Disjoint Paths problem is rm FP rm NP-complete in general graphs, and the unweighted Min-Sum Disjoint Paths problem and the unweighted Min-Max Disjoint Paths problem cannot be approximated within Omega(m1- epsilon) for any constant epsilon > 0 even in planar graphs, assuming rm P neq rm NP, where m is the number of edges in G. We give for the first time a simple bicriteria approximation algorithm for the unweighted Min-Max Edge-Disjoint Paths problem and the weighted Min-Sum Edge-Disjoint Paths problem, with guaranteed approximation ratio O(łog k / łog łog k) and O(1), respectively.

Keywords

MSC

68Q17, 68Q25, 68W25

Cite this article

@article{cai-18123,
  author  = {Peng Zhang and Wenbo Zhao and Daming Zhu},
  title   = {Complexity and Approximation Results for the Min-Sum and Min-Max Disjoint Paths Problems},
  journal = {Computing and Informatics},
  volume  = {32},
  number  = {1},
  pages   = {23--45},
  year    = {2013},
  issn    = {1335-9150},
  url     = {https://cai.type.sk/content/2013/1/complexity-and-approximation-results-for-the-min-sum-and-min-max-disjoint-paths-problems/}
}
Download .bib