# Steiner forest orientation problems

Marek Cygan, Guy Kortsarz, Zeev Nutov

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

## ملخص

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

اللغة الأصلية الإنجليزيّة Algorithms, ESA 2012 - 20th Annual European Symposium, Proceedings 361-372 12 https://doi.org/10.1007/978-3-642-33090-2_32 نُشِر - 2012 20th Annual European Symposium on Algorithms, ESA 2012 - Ljubljana, سلوفينياالمدة: ١٠ سبتمبر ٢٠١٢ → ١٢ سبتمبر ٢٠١٢

### سلسلة المنشورات

الاسم Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7501 LNCS 0302-9743 1611-3349

### !!Conference

!!Conference 20th Annual European Symposium on Algorithms, ESA 2012 سلوفينيا Ljubljana ١٠/٠٩/١٢ → ١٢/٠٩/١٢

## بصمة

أدرس بدقة موضوعات البحث “Steiner forest orientation problems'. فهما يشكلان معًا بصمة فريدة.