Steiner forest orientation problems

Marek Cygan, Guy Kortsarz, Zeev Nutov

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

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

Original languageEnglish (US)
Pages (from-to)1503-1513
Number of pages11
JournalSIAM Journal on Discrete Mathematics
Volume27
Issue number3
DOIs
StatePublished - 2013

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Approximation algorithms
  • Graph algorithms
  • Graph orientation
  • Parameterized complexity

Fingerprint Dive into the research topics of 'Steiner forest orientation problems'. Together they form a unique fingerprint.

Cite this