Min-sum 2-paths problems

Trevor Fenner, Oded Lachish, Alexandru Popa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

An orientation of an undirected graph G is a directed graph obtained by replacing each edge {u,v} of G by exactly one of the arcs (u,v) or (v,u). In the min-sum k-paths orientation problem, the input is an undirected graph G and ordered pairs (s i ,t i ), where i ∈ {1,2,...,k}. The goal is to find an orientation of G that minimizes the sum over every i ∈ {1,2,...,k} of the distance from s i to t i . In the min-sum k edge-disjoint paths problem the input is the same, however the goal is to find for every i ∈ {1,2,...,k} a path between s i and t i so that these paths are edge-disjoint and the sum of their lengths is minimum. Note that, for every fixed k ≥ 2, the question of NP-hardness for the min-sum k-paths orientation problem and the min-sum k edge-disjoint paths problem have been open for more than two decades. We study the complexity of these problems when k = 2. We exhibit a PTAS for the min-sum 2-paths orientation problem. A by-product of this PTAS is a reduction from the min-sum 2-paths orientation problem to the min-sum 2 edge-disjoint paths problem. The implications of this reduction are: (i) an NP-hardness proof for the min-sum 2-paths orientation problem yields an NP-hardness proof for the min-sum 2 edge-disjoint paths problem, and (ii) any approximation algorithm for the min-sum 2 edge-disjoint paths problem can be used to construct an approximation algorithm for the min-sum 2-paths orientation problem with the same approximation guarantee and only an additive polynomial increase in the running time.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Verlag
Pages1-11
Number of pages11
Volume8447 LNCS
ISBN (Print)9783319080000
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event11th International Workshop on Approximation and Online Algorithms, WAOA 2013 - Sophia Antipolis, France
Duration: Sep 5 2013Sep 6 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8447 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other11th International Workshop on Approximation and Online Algorithms, WAOA 2013
CountryFrance
CitySophia Antipolis
Period9/5/139/6/13

Fingerprint

Hardness
Approximation algorithms
Path
Edge-disjoint Paths
Directed graphs
Byproducts
NP-hardness
Polynomials
Undirected Graph
Approximation Algorithms
Ordered pair
Directed Graph
Disjoint
Arc of a curve
Minimise
Polynomial
Approximation

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this

Fenner, T., Lachish, O., & Popa, A. (2014). Min-sum 2-paths problems. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 8447 LNCS, pp. 1-11). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8447 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-08001-7_1

Min-sum 2-paths problems. / Fenner, Trevor; Lachish, Oded; Popa, Alexandru.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 8447 LNCS Springer Verlag, 2014. p. 1-11 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8447 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Fenner, T, Lachish, O & Popa, A 2014, Min-sum 2-paths problems. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 8447 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8447 LNCS, Springer Verlag, pp. 1-11, 11th International Workshop on Approximation and Online Algorithms, WAOA 2013, Sophia Antipolis, France, 9/5/13. https://doi.org/10.1007/978-3-319-08001-7_1
Fenner T, Lachish O, Popa A. Min-sum 2-paths problems. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 8447 LNCS. Springer Verlag. 2014. p. 1-11. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-08001-7_1
Fenner, Trevor ; Lachish, Oded ; Popa, Alexandru. / Min-sum 2-paths problems. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 8447 LNCS Springer Verlag, 2014. pp. 1-11 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{f177c8cdd3364e33a272bbd558ba5451,
title = "Min-sum 2-paths problems",
abstract = "An orientation of an undirected graph G is a directed graph obtained by replacing each edge {u,v} of G by exactly one of the arcs (u,v) or (v,u). In the min-sum k-paths orientation problem, the input is an undirected graph G and ordered pairs (s i ,t i ), where i ∈ {1,2,...,k}. The goal is to find an orientation of G that minimizes the sum over every i ∈ {1,2,...,k} of the distance from s i to t i . In the min-sum k edge-disjoint paths problem the input is the same, however the goal is to find for every i ∈ {1,2,...,k} a path between s i and t i so that these paths are edge-disjoint and the sum of their lengths is minimum. Note that, for every fixed k ≥ 2, the question of NP-hardness for the min-sum k-paths orientation problem and the min-sum k edge-disjoint paths problem have been open for more than two decades. We study the complexity of these problems when k = 2. We exhibit a PTAS for the min-sum 2-paths orientation problem. A by-product of this PTAS is a reduction from the min-sum 2-paths orientation problem to the min-sum 2 edge-disjoint paths problem. The implications of this reduction are: (i) an NP-hardness proof for the min-sum 2-paths orientation problem yields an NP-hardness proof for the min-sum 2 edge-disjoint paths problem, and (ii) any approximation algorithm for the min-sum 2 edge-disjoint paths problem can be used to construct an approximation algorithm for the min-sum 2-paths orientation problem with the same approximation guarantee and only an additive polynomial increase in the running time.",
author = "Trevor Fenner and Oded Lachish and Alexandru Popa",
year = "2014",
doi = "10.1007/978-3-319-08001-7_1",
language = "English",
isbn = "9783319080000",
volume = "8447 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "1--11",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "Germany",

}

TY - GEN

T1 - Min-sum 2-paths problems

AU - Fenner, Trevor

AU - Lachish, Oded

AU - Popa, Alexandru

PY - 2014

Y1 - 2014

N2 - An orientation of an undirected graph G is a directed graph obtained by replacing each edge {u,v} of G by exactly one of the arcs (u,v) or (v,u). In the min-sum k-paths orientation problem, the input is an undirected graph G and ordered pairs (s i ,t i ), where i ∈ {1,2,...,k}. The goal is to find an orientation of G that minimizes the sum over every i ∈ {1,2,...,k} of the distance from s i to t i . In the min-sum k edge-disjoint paths problem the input is the same, however the goal is to find for every i ∈ {1,2,...,k} a path between s i and t i so that these paths are edge-disjoint and the sum of their lengths is minimum. Note that, for every fixed k ≥ 2, the question of NP-hardness for the min-sum k-paths orientation problem and the min-sum k edge-disjoint paths problem have been open for more than two decades. We study the complexity of these problems when k = 2. We exhibit a PTAS for the min-sum 2-paths orientation problem. A by-product of this PTAS is a reduction from the min-sum 2-paths orientation problem to the min-sum 2 edge-disjoint paths problem. The implications of this reduction are: (i) an NP-hardness proof for the min-sum 2-paths orientation problem yields an NP-hardness proof for the min-sum 2 edge-disjoint paths problem, and (ii) any approximation algorithm for the min-sum 2 edge-disjoint paths problem can be used to construct an approximation algorithm for the min-sum 2-paths orientation problem with the same approximation guarantee and only an additive polynomial increase in the running time.

AB - An orientation of an undirected graph G is a directed graph obtained by replacing each edge {u,v} of G by exactly one of the arcs (u,v) or (v,u). In the min-sum k-paths orientation problem, the input is an undirected graph G and ordered pairs (s i ,t i ), where i ∈ {1,2,...,k}. The goal is to find an orientation of G that minimizes the sum over every i ∈ {1,2,...,k} of the distance from s i to t i . In the min-sum k edge-disjoint paths problem the input is the same, however the goal is to find for every i ∈ {1,2,...,k} a path between s i and t i so that these paths are edge-disjoint and the sum of their lengths is minimum. Note that, for every fixed k ≥ 2, the question of NP-hardness for the min-sum k-paths orientation problem and the min-sum k edge-disjoint paths problem have been open for more than two decades. We study the complexity of these problems when k = 2. We exhibit a PTAS for the min-sum 2-paths orientation problem. A by-product of this PTAS is a reduction from the min-sum 2-paths orientation problem to the min-sum 2 edge-disjoint paths problem. The implications of this reduction are: (i) an NP-hardness proof for the min-sum 2-paths orientation problem yields an NP-hardness proof for the min-sum 2 edge-disjoint paths problem, and (ii) any approximation algorithm for the min-sum 2 edge-disjoint paths problem can be used to construct an approximation algorithm for the min-sum 2-paths orientation problem with the same approximation guarantee and only an additive polynomial increase in the running time.

UR - http://www.scopus.com/inward/record.url?scp=84903635435&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84903635435&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-08001-7_1

DO - 10.1007/978-3-319-08001-7_1

M3 - Conference contribution

SN - 9783319080000

VL - 8447 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 11

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

PB - Springer Verlag

ER -