TY - GEN

T1 - Steiner forest orientation problems

AU - Cygan, Marek

AU - Kortsarz, Guy

AU - Nutov, Zeev

PY - 2012

Y1 - 2012

N2 - We consider connectivity problems with orientation constraints. Given a directed graph D and a collection of ordered node pairs P let P[D] = {(u,v) ∈ P: D contains a uv-path}. In the Steiner Forest Orientation problem we are given an undirected graph G = (V,E) with edge-costs and a set P ⊆ V x V of ordered node pairs. The goal is to find a minimum-cost subgraph H of G and an orientation D of H such that P[D] = P. We give a 4-approximation algorithm for this problem. In the Maximum Pairs Orientation problem we are given a graph G and a multi-collection of ordered node pairs P on V. The goal is to find an orientation D of G such that |P[D]| is maximum. Generalizing the result of Arkin and Hassin [DAM'02] for |P| = 2, we will show that for a mixed graph G (that may have both directed and undirected edges), one can decide in n O(|P|) time whether G has an orientation D with P[D] = P (for undirected graphs this problem admits a polynomial time algorithm for any P, but it is NP-complete on mixed graphs). For undirected graphs, we will show that one can decide whether G admits an orientation D with |P[D]| ≥ k in O(n + m) + 2 O(k·loglogk) time; hence this decision problem is fixed-parameter tractable, which answers an open question from Dorn et al. [AMB'11]. We also show that Maximum Pairs Orientation admits ratio O(log|P|/loglog|P|), which is better than the ratio O(logn/loglogn) of Gamzu et al. [WABI'10] when |P| < n. Finally, we show that the following node-connectivity problem can be solved in polynomial time: given a graph G = (V,E) with edge-costs, s,t ∈ V, and an integer ℓ, find a min-cost subgraph H of G with an orientation D such that D contains ℓ internally-disjoint st-paths, and ℓ internally-disjoint ts-paths.

AB - We consider connectivity problems with orientation constraints. Given a directed graph D and a collection of ordered node pairs P let P[D] = {(u,v) ∈ P: D contains a uv-path}. In the Steiner Forest Orientation problem we are given an undirected graph G = (V,E) with edge-costs and a set P ⊆ V x V of ordered node pairs. The goal is to find a minimum-cost subgraph H of G and an orientation D of H such that P[D] = P. We give a 4-approximation algorithm for this problem. In the Maximum Pairs Orientation problem we are given a graph G and a multi-collection of ordered node pairs P on V. The goal is to find an orientation D of G such that |P[D]| is maximum. Generalizing the result of Arkin and Hassin [DAM'02] for |P| = 2, we will show that for a mixed graph G (that may have both directed and undirected edges), one can decide in n O(|P|) time whether G has an orientation D with P[D] = P (for undirected graphs this problem admits a polynomial time algorithm for any P, but it is NP-complete on mixed graphs). For undirected graphs, we will show that one can decide whether G admits an orientation D with |P[D]| ≥ k in O(n + m) + 2 O(k·loglogk) time; hence this decision problem is fixed-parameter tractable, which answers an open question from Dorn et al. [AMB'11]. We also show that Maximum Pairs Orientation admits ratio O(log|P|/loglog|P|), which is better than the ratio O(logn/loglogn) of Gamzu et al. [WABI'10] when |P| < n. Finally, we show that the following node-connectivity problem can be solved in polynomial time: given a graph G = (V,E) with edge-costs, s,t ∈ V, and an integer ℓ, find a min-cost subgraph H of G with an orientation D such that D contains ℓ internally-disjoint st-paths, and ℓ internally-disjoint ts-paths.

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

U2 - 10.1007/978-3-642-33090-2_32

DO - 10.1007/978-3-642-33090-2_32

M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???

AN - SCOPUS:84866656940

SN - 9783642330896

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

SP - 361

EP - 372

BT - Algorithms, ESA 2012 - 20th Annual European Symposium, Proceedings

T2 - 20th Annual European Symposium on Algorithms, ESA 2012

Y2 - 10 September 2012 through 12 September 2012

ER -