Complexity and Approximation Results for the Min-Sum and Min-Max Disjoint Paths Problems

Authors

  • Peng Zhang School of Computer Science and Technology, Shandong University, Jinan 250101
  • Wenbo Zhao Department of Computer Science and Engineering, University of California, San Diego, La Jolla
  • Daming Zhu School of Computer Science and Technology, Shandong University, Jinan

Keywords:

Disjoint paths, min-sum, min-max, computational complexity, approximation algorithms

Abstract

Given a graph G=(V, E) and k source-sink pairs (s1, t1), …, (sk, tk) with each si, ti  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 FPNP-complete in general graphs, and the unweighted Min-Sum Disjoint Paths problem and the unweighted Min-Max Disjoint Paths problem cannot be approximated within m(m1-1) for any constant   > 0 even in planar graphs, assuming P P 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, wi

Downloads

Download data is not yet available.

Downloads

Published

2013-03-22

How to Cite

Zhang, P., Zhao, W., & Zhu, D. (2013). Complexity and Approximation Results for the Min-Sum and Min-Max Disjoint Paths Problems. COMPUTING AND INFORMATICS, 32(1), 23–45. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/1465

Issue

Vol. 32 No. 1 (2013): Computing and Informatics

Section

Articles