Steiner forest orientation problems

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)+2^{O(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.