{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T01:53:21Z","timestamp":1772502801996,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T00:00:00Z","timestamp":1556928000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000741","name":"University of Warwick","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000741","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,8]]},"DOI":"10.1007\/s00453-019-00580-x","type":"journal-article","created":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T13:14:56Z","timestamp":1557148496000},"page":"3200-3216","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A Tight Lower Bound for Planar Steiner Orientation"],"prefix":"10.1007","volume":"81","author":[{"given":"Rajesh","family":"Chitnis","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6229-5332","authenticated-orcid":false,"given":"Andreas Emil","family":"Feldmann","sequence":"additional","affiliation":[]},{"given":"Ond\u0159ej","family":"Such\u00fd","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,5,4]]},"reference":[{"issue":"3","key":"580_CR1","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/S0166-218X(01)00228-1","volume":"116","author":"EM Arkin","year":"2002","unstructured":"Arkin, E.M., Hassin, R.: A note on orientations of mixed graphs. Discrete Appl. Math. 116(3), 271\u2013278 (2002)","journal-title":"Discrete Appl. Math."},{"key":"580_CR2","unstructured":"Beck, M., Blum, J., Kryven, M., L\u00f6ffler, A., Zink, J.: Planar Steiner Orientation is NP-Complete. CoRR. \n                    arXiv:1804.07496\n                    \n                   (2018)"},{"key":"580_CR3","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Cygan, M., Kortsarz, G., Laekhanukit, B., Manurangsi, P., Nanongkai, D., Trevisan, L.: From gap-ETH to FPT-inapproximability: clique, dominating set, and more. In: FOCS 2017, pp. 743\u2013754 (2017)","DOI":"10.1109\/FOCS.2017.74"},{"issue":"8","key":"580_CR4","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72(8), 1346\u20131367 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"580_CR5","doi-asserted-by":"publisher","first-page":"1216","DOI":"10.1007\/s00453-016-0145-8","volume":"77","author":"R Chitnis","year":"2017","unstructured":"Chitnis, R., Esfandiari, H., Hajiaghayi, M.T., Khandekar, R., Kortsarz, G., Seddighin, S.: A tight algorithm for strongly connected Steiner subgraph on two terminals with demands. Algorithmica 77(4), 1216\u20131239 (2017)","journal-title":"Algorithmica"},{"key":"580_CR6","doi-asserted-by":"crossref","unstructured":"Chitnis, R., Feldmann, A.E.: A tight lower bound for Steiner orientation. In: CSR 2018, pp. 65\u201377 (2018)","DOI":"10.1007\/978-3-319-90530-3_7"},{"key":"580_CR7","unstructured":"Chitnis, R., Feldmann, A.E., Manurangsi, P.: Parameterized approximation algorithms for bidirected Steiner network problems. In: 26th Annual European Symposium on Algorithms, ESA 2018, August 20\u201322, 2018, Helsinki, Finland, pp. 20:1\u201320:16 (2018)"},{"key":"580_CR8","unstructured":"Chitnis, R.H., Hajiaghayi, M., Marx, D.: Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions). In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5\u20137, 2014, pp. 1782\u20131801 (2014)"},{"key":"580_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"issue":"3","key":"580_CR10","doi-asserted-by":"publisher","first-page":"1503","DOI":"10.1137\/120883931","volume":"27","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Kortsarz, G., Nutov, Z.: Steiner forest orientation problems. SIAM J. Discrete Math. 27(3), 1503\u20131513 (2013)","journal-title":"SIAM J. Discrete Math."},{"key":"580_CR11","first-page":"128","volume":"23","author":"I Dinur","year":"2016","unstructured":"Dinur, I.: Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electron. Colloq. Comput. Complex. (ECCC) 23, 128 (2016)","journal-title":"Electron. Colloq. Comput. Complex. (ECCC)"},{"key":"580_CR12","doi-asserted-by":"crossref","unstructured":"Gamzu, I., Segev, D., Sharan, R.: Improved orientations of physical networks. In: International Workshop on Algorithms in Bioinformatics (WABI), pp. 215\u2013225 (2010)","DOI":"10.1007\/978-3-642-15294-8_18"},{"key":"580_CR13","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1016\/0024-3795(89)90481-3","volume":"114","author":"R Hassin","year":"1989","unstructured":"Hassin, R., Megiddo, N.: On orientations and shortest paths. Linear Algebra Appl. 114, 589\u2013602 (1989). (special issue dedicated to Alan J. Hoffman)","journal-title":"Linear Algebra Appl."},{"issue":"2","key":"580_CR14","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"580_CR15","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"580_CR16","unstructured":"Manurangsi, P., Raghavendra, P.: A birthday repetition theorem and complexity of approximating dense CSPs. In: ICALP, pp. 78:1\u201378:15 (2017)"},{"key":"580_CR17","doi-asserted-by":"crossref","unstructured":"Marx, D.: On the optimality of planar and geometric approximation schemes. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20\u201323, 2007, Providence, RI, USA, Proceedings, pp. 338\u2013348 (2007)","DOI":"10.1109\/FOCS.2007.26"},{"issue":"1","key":"580_CR18","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory Comput. 6(1), 85\u2013112 (2010)","journal-title":"Theory Comput."},{"key":"580_CR19","doi-asserted-by":"crossref","unstructured":"Marx, D.: A tight lower bound for planar multiway cut with fixed number of terminals. In: ICALP (1), pp. 677\u2013688 (2012)","DOI":"10.1007\/978-3-642-31594-7_57"},{"key":"580_CR20","unstructured":"Marx, D., Pilipczuk, M.: Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask). In: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5\u20138, 2014, Lyon, France, pp. 542\u2013553 (2014)"},{"key":"580_CR21","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using voronoi diagrams. In: Algorithms\u2014ESA 2015\u201423rd Annual European Symposium, Patras, Greece, September 14\u201316, 2015, Proceedings, pp. 865\u2013877 (2015)"},{"key":"580_CR22","doi-asserted-by":"crossref","unstructured":"Medvedovsky, A., Bafna, V., Zwick, U., Sharan, R.: An algorithm for orienting graphs based on cause-effect pairs and its applications to orienting protein networks. In: International Workshop on Algorithms in Bioinformatics (WABI), pp. 222\u2013232 (2008)","DOI":"10.1007\/978-3-540-87361-7_19"},{"key":"580_CR23","unstructured":"Pilipczuk, M., Wahlstr\u00f6m, M.: Directed multicut is W[1]-hard, even for four terminal pairs. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312, 2016, pp. 1167\u20131178 (2016)"},{"issue":"3","key":"580_CR24","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/3201775","volume":"10","author":"M Pilipczuk","year":"2018","unstructured":"Pilipczuk, M., Wahlstr\u00f6m, M.: Directed multicut is W[1]-hard, even for four terminal pairs. TOCT 10(3), 13:1\u201313:18 (2018)","journal-title":"TOCT"},{"issue":"5","key":"580_CR25","doi-asserted-by":"publisher","first-page":"281","DOI":"10.2307\/2303897","volume":"46","author":"HE Robbins","year":"1939","unstructured":"Robbins, H.E.: A theorem on graphs, with an application to a problem of traffic control. Am. Math. Mon. 46(5), 281\u2013283 (1939)","journal-title":"Am. Math. Mon."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00580-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00580-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00580-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,2]],"date-time":"2020-05-02T23:05:15Z","timestamp":1588460715000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00580-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,4]]},"references-count":25,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["580"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00580-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,4]]},"assertion":[{"value":"24 August 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}