{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:39:09Z","timestamp":1787326749605,"version":"build-2736575974"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>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 \\mbox{ contains a } uv\\mbox{-path}\\}$. In the \\sf 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 \\sf 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 $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 Dorn et al. [Algorithms Molecular Biol., 6 (2011)]. 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 [Proceedings of WABI 2010, pp. 215--225] when $|P|&lt;n$.<\/jats:p>","DOI":"10.1137\/120883931","type":"journal-article","created":{"date-parts":[[2013,9,12]],"date-time":"2013-09-12T11:40:55Z","timestamp":1378986055000},"page":"1503-1513","source":"Crossref","is-referenced-by-count":6,"title":["Steiner Forest Orientation Problems"],"prefix":"10.1137","volume":"27","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zeev","family":"Nutov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,9,12]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00228-1"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90039-2"},{"key":"atypb3","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1145\/301250.301447","author":"Dodis Y.","year":"1999","journal-title":"Proceedings of STOC"},{"key":"atypb4","first-page":"6","author":"Dorn B.","year":"2011","journal-title":"Algorithms Molecular Biol."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01375475"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.044"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00460-2"},{"key":"atypb8","first-page":"400","volume":"131","author":"Frank A.","year":"2003","journal-title":"Discrete Appl. Math."},{"key":"atypb9","first-page":"243","author":"Gamzu I.","year":"2012","journal-title":"Proceedings of SIROCCO"},{"key":"atypb10","first-page":"215","author":"Gamzu I.","year":"2010","journal-title":"Proceedings of WABI"},{"key":"atypb11","first-page":"223","author":"Goemans M.","year":"1994","journal-title":"Proceedings of SODA"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"R. Hassin and N. Megiddo,<i>On orientations and shortest paths<\/i> Linear Algebra Appl. (1989), pp. 589-602.","DOI":"10.1016\/0024-3795(89)90481-3"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"atypb15","first-page":"663","author":"Khanna S.","year":"2000","journal-title":"Proceedings of SODA"},{"key":"atypb16","first-page":"222","author":"Medvedovsky A.","year":"2008","journal-title":"Proceedings of WABI"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1960-049-6"},{"key":"atypb18","first-page":"424","author":"Silverbush D.","year":"2011","journal-title":"Proceedings of RECOMB"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120883931","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:35:37Z","timestamp":1787322937000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120883931"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/120883931"],"URL":"https:\/\/doi.org\/10.1137\/120883931","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}