Steiner Forest Orientation Problems

Details Steiner Forest Orientation Problems Steiner Forest Orientation Problems

2011-12-10

arxiv.org/abs/1112.2273v1

Computer Science

Data Structures and Algorithms

Scientific paper

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) \in P: D contains a uv-paths}$. In the Steiner Forest Orientation problem we are given an undirected graph $G=(V,E)$ with edge-costs and a set $P \subseteq V \times 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 for $|P|=2$, we will show that for a mixed graph $G$ (that may have both directed an 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]| \geq k$ in $O(n+m)+2^{O(k\cdot \log \log k)}$ time; hence this decision problem is fixed parameter tractable, which answers an open question from \cite{fpt}. We also show that {\sf 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 when $|P|

Affiliated with

Also associated with

No associations

Rating

Steiner Forest Orientation Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Steiner Forest Orientation Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Steiner Forest Orientation Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-381556