{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:05:20Z","timestamp":1787317520518,"version":"build-2736575974"},"reference-count":84,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,4,19]],"date-time":"2021-04-19T00:00:00Z","timestamp":1618790400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007543","name":"Grantov\u00e1 Agentura, Univerzita Karlova","doi-asserted-by":"publisher","award":["UNCE\/SCI\/004"],"award-info":[{"award-number":["UNCE\/SCI\/004"]}],"id":[{"id":"10.13039\/100007543","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["2014-CoG 647557"],"award-info":[{"award-number":["2014-CoG 647557"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["19-27871X"],"award-info":[{"award-number":["19-27871X"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["897\/13"],"award-info":[{"award-number":["897\/13"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,4,30]]},"abstract":"<jats:p>\n                    The D\n                    <jats:sc>irected<\/jats:sc>\n                    S\n                    <jats:sc>teiner<\/jats:sc>\n                    N\n                    <jats:sc>etwork<\/jats:sc>\n                    (DSN) problem takes as input a directed graph\n                    <jats:italic>G<\/jats:italic>\n                    =(\n                    <jats:italic>V<\/jats:italic>\n                    ,\n                    <jats:italic>E<\/jats:italic>\n                    ) with non-negative edge-weights and a set\n                    <jats:italic>D<\/jats:italic>\n                    \u2286\n                    <jats:italic>V<\/jats:italic>\n                    \u00d7\n                    <jats:italic>V<\/jats:italic>\n                    of\n                    <jats:italic>k<\/jats:italic>\n                    demand pairs. The aim is to compute the cheapest network\n                    <jats:italic>N\u2286 G<\/jats:italic>\n                    for which there is an\n                    <jats:italic>s\\rightarrow t<\/jats:italic>\n                    path for each (\n                    <jats:italic>s<\/jats:italic>\n                    ,\n                    <jats:italic>t<\/jats:italic>\n                    )\u2208 D. It is known that this problem is notoriously hard, as there is no\n                    <jats:italic>k<\/jats:italic>\n                    <jats:sup>\n                      1\/4\u2212\n                      <jats:italic>o<\/jats:italic>\n                      (1)\n                    <\/jats:sup>\n                    -approximation algorithm under Gap-ETH, even when parametrizing the runtime by\n                    <jats:italic>k<\/jats:italic>\n                    [Dinur &amp; Manurangsi, ITCS 2018]. In light of this, we systematically study several special cases of DSN and determine their parameterized approximability for the parameter\n                    <jats:italic>k<\/jats:italic>\n                    .\n                  <\/jats:p>\n                  <jats:p>\n                    For the\n                    <jats:sc>bi<\/jats:sc>\n                    -DSNP\n                    <jats:sc>lanar<\/jats:sc>\n                    problem, the aim is to compute a solution\n                    <jats:italic>N\u2286 G<\/jats:italic>\n                    whose cost is at most that of an optimum planar solution in a bidirected graph\n                    <jats:italic>G<\/jats:italic>\n                    , i.e., for every edge\n                    <jats:italic>uv<\/jats:italic>\n                    of\n                    <jats:italic>G<\/jats:italic>\n                    the reverse edge\n                    <jats:italic>vu<\/jats:italic>\n                    exists and has the same weight. This problem is a generalization of several well-studied special cases. Our main result is that this problem admits a parameterized approximation scheme (PAS) for\u00a0\n                    <jats:italic>k<\/jats:italic>\n                    . We also prove that our result is tight in the sense that (a) the runtime of our PAS cannot be significantly improved, and (b) no PAS exists for any generalization of bi-DSNP\n                    <jats:sc>lanar<\/jats:sc>\n                    , under standard complexity assumptions. The techniques we use also imply a polynomial-sized approximate kernelization scheme (PSAKS). Additionally, we study several generalizations of\n                    <jats:sc>bi<\/jats:sc>\n                    -DSNP\n                    <jats:sc>lanar<\/jats:sc>\n                    and obtain upper and lower bounds on obtainable runtimes parameterized by\u00a0\n                    <jats:italic>k<\/jats:italic>\n                    .\n                  <\/jats:p>\n                  <jats:p>\n                    One important special case of DSN is the S\n                    <jats:sc>trongly<\/jats:sc>\n                    C\n                    <jats:sc>onnected<\/jats:sc>\n                    S\n                    <jats:sc>teiner<\/jats:sc>\n                    S\n                    <jats:sc>ubgraph<\/jats:sc>\n                    (SCSS) problem, for which the solution network\n                    <jats:italic>N\u2286 G<\/jats:italic>\n                    needs to strongly connect a given set of\n                    <jats:italic>k<\/jats:italic>\n                    terminals. It has been observed before that for SCSS a parameterized 2-approximation exists for parameter\u00a0\n                    <jats:italic>k<\/jats:italic>\n                    [Chitnis et\u00a0al., IPEC 2013]. We give a tight inapproximability result by showing that for\n                    <jats:italic>k<\/jats:italic>\n                    no parameterized (2 \u2212 \u03b5)-approximation algorithm exists under Gap-ETH. Additionally, we show that when restricting the input of SCSS to bidirected graphs, the problem remains NP-hard but becomes FPT for\n                    <jats:italic>k<\/jats:italic>\n                    .\n                  <\/jats:p>","DOI":"10.1145\/3447584","type":"journal-article","created":{"date-parts":[[2021,4,19]],"date-time":"2021-04-19T20:01:42Z","timestamp":1618862502000},"page":"1-68","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Parameterized Approximation Algorithms for Bidirected Steiner Network Problems"],"prefix":"10.1145","volume":"17","author":[{"given":"Rajesh","family":"Chitnis","sequence":"first","affiliation":[{"name":"University of Birmingham, Edgbaston, Birmingham, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas Emil","family":"Feldmann","sequence":"additional","affiliation":[{"name":"Charles University, Praha, Czechia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,4,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Benny Applebaum. 2017. Exponentially-hard gap-CSP and local PRG via local hardcore functions. In FOCS. 836--847.  Benny Applebaum. 2017. Exponentially-hard gap-CSP and local PRG via local hardcore functions. In FOCS. 836--847.","DOI":"10.1109\/FOCS.2017.82"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027219"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.007"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Andreas Bj\u00f6rklund Thore Husfeldt Petteri Kaski and Mikko Koivisto. 2007. Fourier meets M\u00f6bius: Fast subset convolution. In STOC. 67--74.  Andreas Bj\u00f6rklund Thore Husfeldt Petteri Kaski and Mikko Koivisto. 2007. Fourier meets M\u00f6bius: Fast subset convolution. In STOC. 67--74.","DOI":"10.1145\/1250790.1250801"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795281086"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1166869"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1042"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921664"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.20105"},{"key":"e_1_2_1_14_1","first-page":"1","article-title":"FPT inapproximability of directed cut and connectivity problems","volume":"8","author":"Chitnis Rajesh","year":"2019","unstructured":"Rajesh Chitnis and Andreas Emil Feldmann . 2019 . FPT inapproximability of directed cut and connectivity problems . In IPEC. 8 : 1 -- 8 :20. Rajesh Chitnis and Andreas Emil Feldmann. 2019. FPT inapproximability of directed cut and connectivity problems. In IPEC. 8:1--8:20.","journal-title":"IPEC."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Rajesh Chitnis MohammadTaghi Hajiaghayi and Guy Kortsarz. 2013. Fixed-parameter and approximation algorithms: A new look. In IPEC. 110--122.  Rajesh Chitnis MohammadTaghi Hajiaghayi and Guy Kortsarz. 2013. Fixed-parameter and approximation algorithms: A new look. In IPEC. 110--122.","DOI":"10.1007\/978-3-319-03898-8_11"},{"key":"e_1_2_1_16_1","first-page":"1","article-title":"Parameterized approximation algorithms for bidirected Steiner network problems","volume":"20","author":"Chitnis Rajesh","year":"2018","unstructured":"Rajesh Chitnis , Andreas Emil Feldmann , and Pasin Manurangsi . 2018 . Parameterized approximation algorithms for bidirected Steiner network problems . In ESA. 20 : 1 -- 20 :16. Rajesh Chitnis, Andreas Emil Feldmann, and Pasin Manurangsi. 2018. Parameterized approximation algorithms for bidirected Steiner network problems. In ESA. 20:1--20:16.","journal-title":"ESA."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M122371X"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.046"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502795"},{"key":"e_1_2_1_20_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_2_1_21_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2017. Graph Theory , 5 th Edition(Graduate Texts in Mathematics , Vol. 173). Springer. Reinhard Diestel. 2017. Graph Theory, 5th Edition(Graduate Texts in Mathematics, Vol. 173). Springer.","edition":"5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_2_1_23_1","volume-title":"Electron. Colloq. Comput. Complex. 23","author":"Dinur Irit","year":"2016","unstructured":"Irit Dinur . 2016 . Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover . Electron. Colloq. Comput. Complex. 23 (2016), 128. Irit Dinur. 2016. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electron. Colloq. Comput. Complex. 23 (2016), 128."},{"key":"e_1_2_1_24_1","first-page":"1","article-title":"ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network","volume":"36","author":"Dinur Irit","year":"2018","unstructured":"Irit Dinur and Pasin Manurangsi . 2018 . ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network . In ITCS. 36 : 1 -- 36 :20. Irit Dinur and Pasin Manurangsi. 2018. ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network. In ITCS. 36:1--36:20.","journal-title":"ITCS."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Yevgeniy Dodis and Sanjeev Khanna. 1999. Design networks with bounded pairwise distance. In STOC. 750--759.  Yevgeniy Dodis and Sanjeev Khanna. 1999. Design networks with bounded pairwise distance. In STOC. 750--759.","DOI":"10.1145\/301250.301447"},{"key":"e_1_2_1_26_1","article-title":"Kernelization lower bounds through colors and IDs","volume":"11","author":"Dom Michael","year":"2014","unstructured":"Michael Dom , Daniel Lokshtanov , and Saket Saurabh . 2014 . Kernelization lower bounds through colors and IDs . ACM Trans. Algor. 11 , 2 (2014), 13:1--13:20. Michael Dom, Daniel Lokshtanov, and Saket Saurabh. 2014. Kernelization lower bounds through colors and IDs. ACM Trans. Algor. 11, 2 (2014), 13:1--13:20.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_28_1","unstructured":"Ding-Zhu Du Yanjun Zhang and Qing Feng. 1991. On better heuristic for Euclidean Steiner minimum trees. In FOCS. 431--439.  Ding-Zhu Du Yanjun Zhang and Qing Feng. 1991. On better heuristic for Euclidean Steiner minimum trees. In FOCS. 431--439."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071B.032"},{"key":"e_1_2_1_30_1","first-page":"1","article-title":"Complexity of the Steiner network problem with respect to the number of terminals","volume":"25","author":"Eiben Eduard","year":"2019","unstructured":"Eduard Eiben , Dusan Knop , Fahad Panolan , and Ondrej Such\u00fd . 2019 . Complexity of the Steiner network problem with respect to the number of terminals . In STACS. 25 : 1 -- 25 :17. Eduard Eiben, Dusan Knop, Fahad Panolan, and Ondrej Such\u00fd. 2019. Complexity of the Steiner network problem with respect to the number of terminals. In STACS. 25:1--25:17.","journal-title":"STACS."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"David Eisenstat Philip Klein and Claire Mathieu. 2012. An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. In SODA. 626--638.  David Eisenstat Philip Klein and Claire Mathieu. 2012. An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. In SODA. 626--638.","DOI":"10.1137\/1.9781611973099.53"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Jittat Fakcharoenphol and Kunal Talwar. 2003. An improved decomposition theorem for graphs excluding a fixed minor. In APPROX-RANDOM. 36--46.  Jittat Fakcharoenphol and Kunal Talwar. 2003. An improved decomposition theorem for graphs excluding a fixed minor. In APPROX-RANDOM. 36--46.","DOI":"10.1007\/978-3-540-45198-3_4"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441241"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.05.009"},{"key":"e_1_2_1_35_1","first-page":"1","article-title":"The complexity landscape of fixed-parameter directed Steiner network problems","volume":"27","author":"Feldmann Andreas Emil","year":"2016","unstructured":"Andreas Emil Feldmann and D\u00e1niel Marx . 2016 . The complexity landscape of fixed-parameter directed Steiner network problems . In ICALP. 27 : 1 -- 27 :14. Andreas Emil Feldmann and D\u00e1niel Marx. 2016. The complexity landscape of fixed-parameter directed Steiner network problems. In ICALP. 27:1--27:14.","journal-title":"ICALP."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-0987-5"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.3390\/a13060146"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.065"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Fedor V. Fomin Daniel Lokshtanov D\u00e1niel Marx Marcin Pilipczuk Michal Pilipczuk and Saket Saurabh. 2016. Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering. In FOCS. 515--524.  Fedor V. Fomin Daniel Lokshtanov D\u00e1niel Marx Marcin Pilipczuk Michal Pilipczuk and Saket Saurabh. 2016. Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering. In FOCS. 515--524.","DOI":"10.1109\/FOCS.2016.62"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210019"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1324-4"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0116001"},{"key":"e_1_2_1_43_1","unstructured":"Fabrizio Grandoni Bundit Laekhanukit and Shi Li. 2019. O(log2 k \/ log log k)-approximation algorithm for directed Steiner tree: A tight quasi-polynomial-time algorithm. In STOC. 253--264.  Fabrizio Grandoni Bundit Laekhanukit and Shi Li. 2019. O (log 2 k \/ log log k )-approximation algorithm for directed Steiner tree: A tight quasi-polynomial-time algorithm. In STOC. 253--264."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/100794560"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Eran Halperin and Robert Krauthgamer. 2003. Polylogarithmic inapproximability. In STOC. 585--594.  Eran Halperin and Robert Krauthgamer. 2003. Polylogarithmic inapproximability. In STOC. 585--594.","DOI":"10.1145\/780542.780628"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Giuseppe F. Italiano Yahav Nussbaum Piotr Sankowski and Christian Wulff-Nilsen. 2011. Improved algorithms for min cut and max flow in undirected planar graphs. In STOC. 313--322.  Giuseppe F. Italiano Yahav Nussbaum Piotr Sankowski and Christian Wulff-Nilsen. 2011. Improved algorithms for min cut and max flow in undirected planar graphs. In STOC. 313--322.","DOI":"10.1145\/1993636.1993679"},{"key":"e_1_2_1_49_1","volume-title":"Complexity of Computer Computations","author":"Karp Richard M.","unstructured":"Richard M. Karp . 1972. Reducibility among combinatorial problems . In Complexity of Computer Computations . Plenum , 85--103. Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. Plenum, 85--103."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009758919736"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/1071747.1071750"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Philip Klein Serge A. Plotkin and Satish Rao. 1993. Excluded minors network decomposition and multicommodity flow. In STOC. 682--690.  Philip Klein Serge A. Plotkin and Satish Rao. 1993. Excluded minors network decomposition and multicommodity flow. In STOC. 682--690.","DOI":"10.1145\/167088.167261"},{"key":"e_1_2_1_53_1","volume-title":"Klein and D\u00e1niel Marx","author":"Philip","year":"2012","unstructured":"Philip N. Klein and D\u00e1niel Marx . 2012 . Solving planar k -terminal cut in O(nc&sqrt; k) time. In ICALP. 569--580. Philip N. Klein and D\u00e1niel Marx. 2012. Solving planar k -terminal cut in O(nc&sqrt; k) time. In ICALP. 569--580."},{"key":"e_1_2_1_54_1","volume-title":"Klein and D\u00e1niel Marx","author":"Philip","year":"2014","unstructured":"Philip N. Klein and D\u00e1niel Marx . 2014 . A subexponential parameterized algorithm for Subset TSP on planar graphs. In SODA. 1812--1830. Philip N. Klein and D\u00e1niel Marx. 2014. A subexponential parameterized algorithm for Subset TSP on planar graphs. In SODA. 1812--1830."},{"key":"e_1_2_1_55_1","unstructured":"Guy Kortsarz and David Peleg. 1993. On choosing a dense subgraph (extended abstract). In FOCS. 692--701.  Guy Kortsarz and David Peleg. 1993. On choosing a dense subgraph (extended abstract). In FOCS. 692--701."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-013-9637-5"},{"key":"e_1_2_1_57_1","volume-title":"A simpler proof of the KPR theorem","author":"Lee James","year":"2012","unstructured":"James Lee . 2012. A simpler proof of the KPR theorem , 2012 . Retrieved from: https:\/\/tcsmath.wordpress.com\/2012\/01\/11\/a-simpler-proof-of-the-kpr-theorem\/. James Lee. 2012. A simpler proof of the KPR theorem, 2012. Retrieved from: https:\/\/tcsmath.wordpress.com\/2012\/01\/11\/a-simpler-proof-of-the-kpr-theorem\/."},{"key":"e_1_2_1_58_1","unstructured":"Daniel Lokshtanov Saket Saurabh and Magnus Wahlstr\u00f6m. 2012. Subexponential parameterized odd cycle transversal on planar graphs. In FSTTCS. 424--434.  Daniel Lokshtanov Saket Saurabh and Magnus Wahlstr\u00f6m. 2012. Subexponential parameterized odd cycle transversal on planar graphs. In FSTTCS. 424--434."},{"key":"e_1_2_1_59_1","doi-asserted-by":"crossref","unstructured":"Daniel Lokshtanov Fahad Panolan M. S. Ramanujan and Saket Saurabh. 2017. Lossy kernelization. In STOC. 224--237.  Daniel Lokshtanov Fahad Panolan M. S. Ramanujan and Saket Saurabh. 2017. Lossy kernelization. In STOC. 224--237.","DOI":"10.1145\/3055399.3055456"},{"key":"e_1_2_1_60_1","doi-asserted-by":"crossref","unstructured":"Daniel Lokshtanov M. S. Ramanujan Saket Saurabh and Meirav Zehavi. 2020. Parameterized complexity and approximability of directed odd cycle transversal. In SODA. 2181--2200.  Daniel Lokshtanov M. S. Ramanujan Saket Saurabh and Meirav Zehavi. 2020. Parameterized complexity and approximability of directed odd cycle transversal. In SODA. 2181--2200.","DOI":"10.1137\/1.9781611975994.134"},{"key":"e_1_2_1_61_1","doi-asserted-by":"crossref","unstructured":"Pasin Manurangsi. 2017. Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. In STOC. 954--961.  Pasin Manurangsi. 2017. Almost-polynomial ratio ETH-hardness of approximating densest k -subgraph. In STOC. 954--961.","DOI":"10.1145\/3055399.3055412"},{"key":"e_1_2_1_62_1","first-page":"1","article-title":"A birthday repetition theorem and complexity of approximating dense CSPs","volume":"78","author":"Manurangsi Pasin","year":"2017","unstructured":"Pasin Manurangsi and Prasad Raghavendra . 2017 . A birthday repetition theorem and complexity of approximating dense CSPs . In ICALP. 78 : 1 -- 78 :15. Pasin Manurangsi and Prasad Raghavendra. 2017. A birthday repetition theorem and complexity of approximating dense CSPs. In ICALP. 78:1--78:15.","journal-title":"ICALP."},{"key":"e_1_2_1_63_1","doi-asserted-by":"crossref","unstructured":"D\u00e1niel Marx. 2007. On the optimality of planar and geometric approximation schemes. In FOCS. 338--348.  D\u00e1niel Marx. 2007. On the optimality of planar and geometric approximation schemes. In FOCS. 338--348.","DOI":"10.1109\/FOCS.2007.26"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a005"},{"key":"e_1_2_1_65_1","doi-asserted-by":"crossref","unstructured":"D\u00e1niel Marx. 2012. A tight lower bound for planar multiway cut with fixed number of terminals. In ICALP. 677--688.  D\u00e1niel Marx. 2012. A tight lower bound for planar multiway cut with fixed number of terminals. In ICALP. 677--688.","DOI":"10.1007\/978-3-642-31594-7_57"},{"key":"e_1_2_1_66_1","doi-asserted-by":"crossref","unstructured":"D\u00e1niel Marx and Michal Pilipczuk. 2015. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In ESA. 865--877.  D\u00e1niel Marx and Michal Pilipczuk. 2015. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In ESA. 865--877.","DOI":"10.1007\/978-3-662-48350-3_72"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/110855247"},{"key":"e_1_2_1_68_1","doi-asserted-by":"crossref","unstructured":"D\u00e1niel Marx Marcin Pilipczuk and Michal Pilipczuk. 2018. On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs. In FOCS. 474--484.  D\u00e1niel Marx Marcin Pilipczuk and Michal Pilipczuk. 2018. On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs. In FOCS. 474--484.","DOI":"10.1109\/FOCS.2018.00052"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a007"},{"key":"e_1_2_1_70_1","unstructured":"Moni Naor Leonard J. Schulman and Aravind Srinivasan. 1995. Splitters and near-optimal derandomization. In FOCS. 182--191.  Moni Naor Leonard J. Schulman and Aravind Srinivasan. 1995. Splitters and near-optimal derandomization. In FOCS. 182--191."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9630-x"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00078-3"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3201775"},{"key":"e_1_2_1_74_1","unstructured":"Marcin Pilipczuk Michal Pilipczuk Piotr Sankowski and Erik Jan van Leeuwen. 2013. Subexponential-time parameterized algorithm for Steiner tree on planar graphs. In STACS. 353--364.  Marcin Pilipczuk Michal Pilipczuk Piotr Sankowski and Erik Jan van Leeuwen. 2013. Subexponential-time parameterized algorithm for Steiner tree on planar graphs. In STACS. 353--364."},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/3239560"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1086"},{"key":"e_1_2_1_77_1","unstructured":"Ram Ramanathan and Regina Rosales-Hain. 2000. Topology control of multihop wireless networks using transmit power adjustment. In INFOCOM.  Ram Ramanathan and Regina Rosales-Hain. 2000. Topology control of multihop wireless networks using transmit power adjustment. In INFOCOM."},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"},{"key":"e_1_2_1_79_1","volume-title":"Approximation Algorithms","author":"Vazirani Vijay V.","unstructured":"Vijay V. Vazirani . 2001. Approximation Algorithms . Springer . Vijay V. Vazirani. 2001. Approximation Algorithms. Springer."},{"key":"e_1_2_1_80_1","unstructured":"Adrian Vetta. 2001. Approximating the minimum strongly connected subgraph via a matching lower bound. In SODA.  Adrian Vetta. 2001. Approximating the minimum strongly connected subgraph via a matching lower bound. In SODA."},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.08.005"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.01.029"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02612335"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187035"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447584","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447584","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:28:37Z","timestamp":1750181317000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447584"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,19]]},"references-count":84,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4,30]]}},"alternative-id":["10.1145\/3447584"],"URL":"https:\/\/doi.org\/10.1145\/3447584","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,19]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}