Steiner Forest Orientation Problems

Abstract

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 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.