{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T00:10:09Z","timestamp":1758586209887,"version":"3.44.0"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032046994","type":"print"},{"value":"9783032047007","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T00:00:00Z","timestamp":1757548800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T00:00:00Z","timestamp":1757548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-04700-7_3","type":"book-chapter","created":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T23:45:44Z","timestamp":1758498344000},"page":"30-44","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the\u00a0Exact & Approximate Complexity of\u00a0the\u00a0Strongly Connected Steiner Subgraph Problem on Two Terminals with Demands"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-2179-9974","authenticated-orcid":false,"given":"Kevin Kurien","family":"Alex","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6098-7770","authenticated-orcid":false,"given":"Rajesh","family":"Chitnis","sequence":"additional","affiliation":[]},{"given":"Alex","family":"Tempest","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,11]]},"reference":[{"issue":"4","key":"3_CR1","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1002\/jgt.22109","volume":"85","author":"P Aboulker","year":"2017","unstructured":"Aboulker, P., Brettell, N., Havet, F., Marx, D., Trotignon, N.: Coloring graphs with constraints on connectivity. J. Graph Theory 85(4), 814\u2013838 (2017). https:\/\/doi.org\/10.1002\/jgt.22109","journal-title":"J. Graph Theory"},{"issue":"2","key":"3_CR2","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/S00453-013-9862-4","volume":"72","author":"D Chakrabarty","year":"2015","unstructured":"Chakrabarty, D., Chekuri, C., Khanna, S., Korula, N.: Approximability of capacitated network design. Algorithmica 72(2), 493\u2013514 (2015). https:\/\/doi.org\/10.1007\/S00453-013-9862-4","journal-title":"Algorithmica"},{"issue":"1","key":"3_CR3","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/JAGM.1999.1042","volume":"33","author":"M Charikar","year":"1999","unstructured":"Charikar, M., et al.: Approximation algorithms for directed steiner problems. J. Algorithms 33(1), 73\u201391 (1999). https:\/\/doi.org\/10.1006\/JAGM.1999.1042","journal-title":"J. Algorithms"},{"issue":"2","key":"3_CR4","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1137\/21M1395089","volume":"37","author":"R Chitnis","year":"2023","unstructured":"Chitnis, R.: A tight lower bound for edge-disjoint paths on planar dags. SIAM J. Discret. Math. 37(2), 556\u2013572 (2023). https:\/\/doi.org\/10.1137\/21M1395089","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"3_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). https:\/\/doi.org\/10.1007\/S00453-016-0145-8","journal-title":"Algorithmica"},{"key":"3_CR6","doi-asserted-by":"publisher","unstructured":"Chitnis, R., Feldmann, A.E.: FPT inapproximability of directed cut and connectivity problems. In: Jansen, B.M.P., Telle, J.A. (eds.) 14th International Symposium on Parameterized and Exact Computation, IPEC 2019. LIPIcs, vol.\u00a0148, pp. 8:1\u20138:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPICS.IPEC.2019.8","DOI":"10.4230\/LIPICS.IPEC.2019.8"},{"key":"3_CR7","doi-asserted-by":"publisher","unstructured":"Chitnis, R., Feldmann, A.E., Manurangsi, P.: Parameterized approximation algorithms for bidirected steiner network problems. ACM Trans. Algorithms 17(2), 12:1\u201312:68 (2021). https:\/\/doi.org\/10.1145\/3447584","DOI":"10.1145\/3447584"},{"issue":"8","key":"3_CR8","doi-asserted-by":"publisher","first-page":"3200","DOI":"10.1007\/S00453-019-00580-X","volume":"81","author":"R Chitnis","year":"2019","unstructured":"Chitnis, R., Feldmann, A.E., Such\u00fd, O.: A tight lower bound for planar steiner orientation. Algorithmica 81(8), 3200\u20133216 (2019). https:\/\/doi.org\/10.1007\/S00453-019-00580-X","journal-title":"Algorithmica"},{"issue":"2","key":"3_CR9","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1137\/18M122371X","volume":"49","author":"RH Chitnis","year":"2020","unstructured":"Chitnis, R.H., Feldmann, A.E., Hajiaghayi, M.T., Marx, D.: Tight bounds for planar strongly connected steiner subgraph with fixed number of terminals (and extensions). SIAM J. Comput. 49(2), 318\u2013364 (2020). https:\/\/doi.org\/10.1137\/18M122371X","journal-title":"SIAM J. Comput."},{"key":"3_CR10","doi-asserted-by":"publisher","unstructured":"Chitnis, R.H., Hajiaghayi, M., Kortsarz, G.: Fixed-parameter and approximation algorithms: a new look. In: Gutin, G.Z., Szeider, S. (eds.) Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Revised Selected Papers. LNCS, vol.\u00a08246, pp. 110\u2013122. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-319-03898-8_11","DOI":"10.1007\/978-3-319-03898-8_11"},{"issue":"6","key":"3_CR11","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM 52(6), 866\u2013893 (2005). https:\/\/doi.org\/10.1145\/1101821.1101823","journal-title":"J. ACM"},{"key":"3_CR12","doi-asserted-by":"publisher","unstructured":"Diestel, R.: Graph Theory, 5th edn. Springer, Berlin, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-70107-2","DOI":"10.1007\/978-3-662-70107-2"},{"key":"3_CR13","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (2012). https:\/\/doi.org\/10.1007\/978-1-4612-0515-9","DOI":"10.1007\/978-1-4612-0515-9"},{"issue":"2","key":"3_CR14","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1137\/S0097539704441241","volume":"36","author":"J Feldman","year":"2006","unstructured":"Feldman, J., Ruhl, M.: The directed steiner network problem is tractable for a constant number of terminals. SIAM J. Comput. 36(2), 543\u2013561 (2006). https:\/\/doi.org\/10.1137\/S0097539704441241","journal-title":"SIAM J. Comput."},{"key":"3_CR15","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCSS.2024.103604","volume":"148","author":"AE Feldmann","year":"2025","unstructured":"Feldmann, A.E., Mukherjee, A., van Leeuwen, E.J.: The parameterized complexity of the survivable network design problem. J. Comput. Syst. Sci. 148, 103604 (2025). https:\/\/doi.org\/10.1016\/J.JCSS.2024.103604","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR16","doi-asserted-by":"publisher","unstructured":"Fomin, F., Kolay, S., Lokshtanov, D., Panolan, F., Saurabh, S.: Subexponential algorithms for rectilinear steiner tree and arborescence problems. In: 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a051, pp. 39:1\u201339:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2016). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2016.39","DOI":"10.4230\/LIPIcs.SoCG.2016.39"},{"key":"3_CR17","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 515\u2013524 (2016). https:\/\/doi.org\/10.1109\/FOCS.2016.62","DOI":"10.1109\/FOCS.2016.62"},{"key":"3_CR18","doi-asserted-by":"publisher","unstructured":"Galby, E., Kisfaludi-Bak, S., Marx, D., Sharma, R.: Subexponential parameterized directed steiner network problems on planar graphs: A complete classification. In: Bringmann, K., Grohe, M., Puppis, G., Svensson, O. (eds.) 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024. LIPIcs, vol.\u00a0297, pp. 67:1\u201367:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/LIPICS.ICALP.2024.67","DOI":"10.4230\/LIPICS.ICALP.2024.67"},{"key":"3_CR19","unstructured":"Goemans, M.X., Goldberg, A.V., Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9., Williamson, D.P.: Improved approximation algorithms for network design problems. In: Sleator, D.D. (ed.) Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 223\u2013232. ACM\/SIAM (1994). http:\/\/dl.acm.org\/citation.cfm?id=314464.314497"},{"key":"3_CR20","doi-asserted-by":"publisher","unstructured":"Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 585\u2013594. ACM (2003). https:\/\/doi.org\/10.1145\/780542.780628","DOI":"10.1145\/780542.780628"},{"issue":"2","key":"3_CR21","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). https:\/\/doi.org\/10.1006\/JCSS.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"3_CR22","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). https:\/\/doi.org\/10.1006\/JCSS.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"3_CR23","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/S004930170004","volume":"21","author":"K Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized steiner network problem. Comb. 21(1), 39\u201360 (2001). https:\/\/doi.org\/10.1007\/S004930170004","journal-title":"Comb."},{"key":"3_CR24","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems, pp. 85\u2013103. Springer US, Boston, MA (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"3_CR25","doi-asserted-by":"publisher","unstructured":"Klein, P.N., Marx, D.: Solving planar k -terminal cut in $$o(n^{c\\sqrt{k}})$$ time. In: Czumaj, A., Mehlhorn, K., Pitts, A.M., Wattenhofer, R. (eds.) Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings, Part I. LNCS, vol.\u00a07391, pp. 569\u2013580. Springer, Cham (2012).https:\/\/doi.org\/10.1007\/978-3-642-31594-7_48","DOI":"10.1007\/978-3-642-31594-7_48"},{"key":"3_CR26","doi-asserted-by":"publisher","unstructured":"Klein, P.N., Marx, D.: A subexponential parameterized algorithm for subset tsp on planar graphs. In: Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1812\u20131830 (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.131","DOI":"10.1137\/1.9781611973402.131"},{"issue":"2","key":"3_CR27","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1002\/NET.22005","volume":"77","author":"I Ljubic","year":"2021","unstructured":"Ljubic, I.: Solving steiner trees: recent advances, challenges, and perspectives. Networks 77(2), 177\u2013204 (2021). https:\/\/doi.org\/10.1002\/NET.22005","journal-title":"Networks"},{"key":"3_CR28","doi-asserted-by":"publisher","unstructured":"Marx, D.: A tight lower bound for planar multiway cut with fixed number of terminals. In: Czumaj, A., Mehlhorn, K., Pitts, A.M., Wattenhofer, R. (eds.) Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings, Part I. LNCS, vol.\u00a07391, pp. 677\u2013688. Springer, Cham (2012). https:\/\/doi.org\/10.1007\/978-3-642-31594-7_57","DOI":"10.1007\/978-3-642-31594-7_57"},{"key":"3_CR29","doi-asserted-by":"publisher","unstructured":"Marx, D.: The square root phenomenon in planar graphs. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M.Z., Peleg, D. (eds.) Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II. LNCS, vol.\u00a07966, p.\u00a028. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-642-39212-2_4","DOI":"10.1007\/978-3-642-39212-2_4"},{"key":"3_CR30","doi-asserted-by":"publisher","unstructured":"Marx, D., Pilipczuk, M., Pilipczuk, M.: On subexponential parameterized algorithms for steiner tree and directed subset TSP on planar graphs. In: Thorup, M. (ed.) 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pp. 474\u2013484. IEEE Computer Society (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00052","DOI":"10.1109\/FOCS.2018.00052"},{"key":"3_CR31","doi-asserted-by":"publisher","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using voronoi diagrams. In: Bansal, N., Finocchi, I. (eds.) Algorithms - ESA 2015 - 23rd Annual European Symposium, Proceedings. LNCS, vol.\u00a09294, pp. 865\u2013877. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_72","DOI":"10.1007\/978-3-662-48350-3_72"},{"key":"3_CR32","doi-asserted-by":"publisher","unstructured":"Pilipczuk, M., Pilipczuk, M., Sankowski, P., van Leeuwen, E.J.: Subexponential-time parameterized algorithm for steiner tree on planar graphs. In: 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013. LIPIcs, vol.\u00a020, pp. 353\u2013364. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2013). https:\/\/doi.org\/10.4230\/LIPICS.STACS.2013.353","DOI":"10.4230\/LIPICS.STACS.2013.353"},{"issue":"4","key":"3_CR33","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1109\/TCT.1969.1083004","volume":"16","author":"K Steiglitz","year":"1969","unstructured":"Steiglitz, K., Weiner, P., Kleitman, D.: The design of minimum-cost survivable networks. IEEE Trans. Circuit Theory 16(4), 455\u2013460 (1969). https:\/\/doi.org\/10.1109\/TCT.1969.1083004","journal-title":"IEEE Trans. Circuit Theory"},{"issue":"4","key":"3_CR34","doi-asserted-by":"publisher","first-page":"2560","DOI":"10.1109\/TVT.2007.912605","volume":"57","author":"D Yang","year":"2008","unstructured":"Yang, D., Liao, W.: On multicast routing using rectilinear steiner trees for LEO satellite networks. IEEE Trans. Veh. Technol. 57(4), 2560\u20132569 (2008). https:\/\/doi.org\/10.1109\/TVT.2007.912605","journal-title":"IEEE Trans. Veh. Technol."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-04700-7_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T23:45:46Z","timestamp":1758498346000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-04700-7_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,11]]},"ISBN":["9783032046994","9783032047007"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-04700-7_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,11]]},"assertion":[{"value":"11 September 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FCT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Fundamentals of Computation Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Wroc\u0142aw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fct2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/fct.ii.uni.wroc.pl","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}