TY - JOUR

T1 - Steiner forest orientation problems

AU - Cygan, Marek

AU - Kortsarz, Guy

AU - Nutov, Zeev

PY - 2013

Y1 - 2013

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 × 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 multicollection 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 [Discrete Appl. Math., 116 (2002), pp. 271-278] for |P| = 2, we will show that for a mixed graph G (that may have both directed and undirected edges), one can decide in nO(|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)+2O(k·log log k) time; hence this decision problem is fixed-parameter tractable, which answers an open question from Dorn et al. [Algorithms Molecular Biol., 6 (2011)]. We also show that Maximum Pairs Orientation admits ratio O(log |P|/ log log |P|), which is better than the ratio O(log n/ log log n) of Gamzu, Segev, and Sharan [Proceedings of WABI 2010, pp. 215-225] when |P| < n.

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 × 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 multicollection 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 [Discrete Appl. Math., 116 (2002), pp. 271-278] for |P| = 2, we will show that for a mixed graph G (that may have both directed and undirected edges), one can decide in nO(|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)+2O(k·log log k) time; hence this decision problem is fixed-parameter tractable, which answers an open question from Dorn et al. [Algorithms Molecular Biol., 6 (2011)]. We also show that Maximum Pairs Orientation admits ratio O(log |P|/ log log |P|), which is better than the ratio O(log n/ log log n) of Gamzu, Segev, and Sharan [Proceedings of WABI 2010, pp. 215-225] when |P| < n.

KW - Approximation algorithms

KW - Graph algorithms

KW - Graph orientation

KW - Parameterized complexity

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

U2 - 10.1137/120883931

DO - 10.1137/120883931

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:84887918342

SN - 0895-4801

VL - 27

SP - 1503

EP - 1513

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -