{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T06:41:29Z","timestamp":1777444889698,"version":"3.51.4"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,11,10]],"date-time":"2016-11-10T00:00:00Z","timestamp":1478736000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["267959"],"award-info":[{"award-number":["267959"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["267959"],"award-info":[{"award-number":["267959"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Government of the Russian Federation","award":["14.Z50.31.0030"],"award-info":[{"award-number":["14.Z50.31.0030"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s00224-016-9717-x","type":"journal-article","created":{"date-parts":[[2016,11,10]],"date-time":"2016-11-10T02:14:49Z","timestamp":1478744089000},"page":"795-819","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Parameterized Complexity of Secluded Connectivity Problems"],"prefix":"10.1007","volume":"61","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikolay","family":"Karpov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander S.","family":"Kulikov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,11,10]]},"reference":[{"key":"9717_CR1","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42, 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"9717_CR2","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V Bafna","year":"1999","unstructured":"Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discret. Math. 12, 289\u2013297 (1999)","journal-title":"SIAM J. Discret. Math."},{"key":"9717_CR3","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0004-3702(95)00004-6","volume":"83","author":"A Becker","year":"1996","unstructured":"Becker, A., Geiger, D.: Optimization of Pearl\u2019s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artif. Intell. 83, 167\u2013188 (1996)","journal-title":"Artif. Intell."},{"key":"9717_CR4","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets M\u00f6bius: fast subset convolution. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp 67\u201374. ACM, California, USA (2007)","DOI":"10.1145\/1250790.1250801"},{"key":"9717_CR5","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H. L., Downey, R. G., Fellows, M. R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75, 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9717_CR6","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H. L., Jansen, B. M. P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discret. Math. 28, 277\u2013305 (2014)","journal-title":"SIAM J. Discret. Math."},{"key":"9717_CR7","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1093\/comjnl\/bxm086","volume":"51","author":"L Cai","year":"2008","unstructured":"Cai, L.: Parameterized complexity of cardinality constrained optimization problems. Comput. J. 51, 102\u2013121 (2008)","journal-title":"Comput. J."},{"key":"9717_CR8","doi-asserted-by":"crossref","unstructured":"Cai, L., Chan, S. M., Chan, S. O.: Random separation: a new method for solving fixed-cardinality optimization problems. In: IWPEC, vol. 4169 of Lecture Notes in Computer Science, Springer, pp 239\u2013250 (2006)","DOI":"10.1007\/11847250_22"},{"key":"9717_CR9","doi-asserted-by":"crossref","unstructured":"Chechik, S., Johnson, M. P., Parter, M., Peleg, D.: Secluded connectivity problems. CoRR, abs\/1212, 6176 (2012)","DOI":"10.1007\/978-3-642-40450-4_26"},{"key":"9717_CR10","doi-asserted-by":"crossref","unstructured":"Chechik, S., Johnson, M. P., Parter, M., Peleg, D.: Secluded connectivity problems. In: Proceedings of the 21st Annual European Symposium Algorithms (ESA), vol. 8125 of Lecture Notes in Computer Science, pp 301\u2013312. Springer (2013)","DOI":"10.1007\/978-3-642-40450-4_26"},{"key":"9717_CR11","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized algorithms. Springer (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"9717_CR12","doi-asserted-by":"crossref","unstructured":"Downey, R. G., Fellows, M. R.: Fundamentals of parameterized complexity. Texts in Computer Science, Springer (2013)","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"9717_CR13","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"SE Dreyfus","year":"1971","unstructured":"Dreyfus, S. E., Wagner, R. A.: The Steiner problem in graphs. Networks 1, 195\u2013207 (1971)","journal-title":"Networks"},{"key":"9717_CR14","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M. R., Hermelin, D., Rosamond, F. A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410, 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9717_CR15","unstructured":"Fomin, F. V., Golovach, P. A., Karpov, N., Kulikov, A.S.: Parameterized complexity of secluded connectivity problems. In: FSTTCS 2015, vol. 45 of LIPIcs, pp 408\u2013419"},{"key":"9717_CR16","doi-asserted-by":"crossref","unstructured":"Fomin, F. V., Kratsch, D.: Exact exponential algorithms, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag (2010)","DOI":"10.1007\/978-3-642-16533-7"},{"key":"9717_CR17","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/s00493-012-2536-z","volume":"32","author":"FV Fomin","year":"2012","unstructured":"Fomin, F. V., Villanger, Y.: Treewidth computation and extremal combinatorics. Combinatorica 32, 289\u2013308 (2012)","journal-title":"Combinatorica"},{"key":"9717_CR18","doi-asserted-by":"crossref","unstructured":"Gao, J., Zhao, Q., Swami, A.: The thinnest path problem for secure communications: A directed hypergraph approach. In: Proceedings of the 50th Annual Allerton Conference on Communication, Control, and Computing, pp 847\u2013852. IEEE","DOI":"10.1109\/Allerton.2012.6483306"},{"key":"9717_CR19","unstructured":"Garey, M. R., Johnson, D. S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)"},{"key":"9717_CR20","volume-title":"Visibility domains and complexity","author":"A Gilbers","year":"2013","unstructured":"Gilbers, A.: Visibility domains and complexity. PhD thesis, Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn, Bonn (2013)"},{"key":"9717_CR21","doi-asserted-by":"crossref","first-page":"5744","DOI":"10.1016\/j.tcs.2011.06.018","volume":"412","author":"G Gutin","year":"2011","unstructured":"Gutin, G., Jones, M., Yeo, A.: Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems. Theor. Comput. Sci. 412, 5744\u20135751 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9717_CR22","doi-asserted-by":"crossref","unstructured":"Johnson, M. P., Liu, O., Rabanca, G.: Secluded path via shortest path. In: SIROCCO 2014, vol. 8576 of Lecture Notes in Computer Science, pp 108\u2013120. Springer (2014)","DOI":"10.1007\/978-3-319-09620-9_10"},{"key":"9717_CR23","doi-asserted-by":"crossref","unstructured":"Karp, R. M.: Reducibility among combinatorial problems. In: Proceedings of a symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, pp 85\u2013103. Plenum Press, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"9717_CR24","doi-asserted-by":"crossref","unstructured":"Naor, M., Schulman, L., Srinivasan, A.: Splitters and nearoptimal derandomization. In: 36th Annual Symposium on Foundations of Computer Science (FOCS 1995), pp 182\u2013191. IEEE (1995)","DOI":"10.1109\/SFCS.1995.492475"},{"key":"9717_CR25","doi-asserted-by":"crossref","first-page":"868","DOI":"10.1007\/s00453-012-9630-x","volume":"65","author":"J Nederlof","year":"2013","unstructured":"Nederlof, J.: Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica 65, 868\u2013884 (2013)","journal-title":"Algorithmica"},{"key":"9717_CR26","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci. 67, 757\u2013771 (2003)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9717-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9717-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9717-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T08:33:49Z","timestamp":1749717229000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9717-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,10]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["9717"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9717-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,10]]}}}