{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T22:59:30Z","timestamp":1743116370428,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642308901"},{"type":"electronic","value":"9783642308918"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-30891-8_19","type":"book-chapter","created":{"date-parts":[[2012,6,18]],"date-time":"2012-06-18T05:24:05Z","timestamp":1339997045000},"page":"457-468","source":"Crossref","is-referenced-by-count":2,"title":["FPT Suspects and Tough Customers: Open Problems of Downey and Fellows"],"prefix":"10.1007","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: The shortest vector problem in \n                    \n                      \n                    \n                    $\\ell_{\\mbox{2}}$\n                   is NP-hard for randomized reductions. In: STOC, pp. 10\u201319 (1998)","DOI":"10.1145\/276698.276705"},{"issue":"4","key":"19_CR2","doi-asserted-by":"publisher","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. Assoc. Comput. Mach.\u00a042(4), 844\u2013856 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1","key":"19_CR3","first-page":"49","volume":"11","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hallett, M.T., Wareham, H.T.: Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences\u00a011(1), 49\u201357 (1995)","journal-title":"Computer Applications in the Biosciences"},{"issue":"1, 2","key":"19_CR4","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0304-3975(94)00251-D","volume":"147","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Wareham, H.T.: The parameterized complexity of sequence alignment and consensus. Theor. Comput. Sci.\u00a0147(1, 2), 31\u201354 (1995)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"19_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-007-9130-6","volume":"55","author":"J. Chen","year":"2009","unstructured":"Chen, J., Liu, Y., Lu, S.: An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica\u00a055(1), 1\u201313 (2009)","journal-title":"Algorithmica"},{"issue":"5","key":"19_CR6","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/1411509.1411511","volume":"55","author":"J. Chen","year":"2008","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM\u00a055(5), Art. 21, 19 (2008)","journal-title":"J. ACM"},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. In: STOC, pp. 177\u2013186 (2008)","DOI":"10.1145\/1374376.1374404"},{"key":"19_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-28050-4_1","volume-title":"Parameterized and Exact Computation","author":"M. Cygan","year":"2012","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: On Multiway Cut Parameterized above Lower Bounds. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol.\u00a07112, pp. 1\u201312. Springer, Heidelberg (2012)"},{"issue":"4","key":"19_CR9","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput.\u00a023(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"19_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1007\/11533719_87","volume-title":"Computing and Combinatorics","author":"F. Dehne","year":"2005","unstructured":"Dehne, F., Fellows, M., Langston, M.A., Rosamond, F., Stevens, K.: An O(2O(k)n3) FPT Algorithm for the Undirected Feedback Vertex Set Problem. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 859\u2013869. Springer, Heidelberg (2005)"},{"issue":"4","key":"19_CR11","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: Basic results. SIAM J. Comput.\u00a024(4), 873\u2013921 (1995)","journal-title":"SIAM J. Comput."},{"issue":"1, 2","key":"19_CR12","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: On completeness for W[1]. Theor. Comput. Sci.\u00a0141(1, 2), 109\u2013131 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"19_CR13","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-1-4612-2566-9_7","volume-title":"Feasible Mathematics II","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized computational feasibility. In: Feasible Mathematics II, pp. 219\u2013244. Birkh\u00e4user, Boston (1995)"},{"key":"19_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer, New York (1999)"},{"issue":"1","key":"19_CR15","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF00396268","volume":"1","author":"M.H. El-Zahar","year":"1984","unstructured":"El-Zahar, M.H., Schmerl, J.H.: On the size of jump-critical ordered sets. Order\u00a01(1), 3\u20135 (1984)","journal-title":"Order"},{"key":"19_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/3-540-45678-3_26","volume-title":"Algorithms and Computation","author":"M.R. Fellows","year":"2001","unstructured":"Fellows, M.R.: Parameterized Complexity: The Main Ideas and Some Research Frontiers. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol.\u00a02223, pp. 291\u2013307. Springer, Heidelberg (2001)"},{"key":"19_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/3-540-56686-4_38","volume-title":"Applied Algebra, Algebraic Algorithms and Error-Correcting Codes","author":"M.R. Fellows","year":"1993","unstructured":"Fellows, M.R., Koblitz, N.: Fixed-Parameter Complexity and Cryptography. In: Moreno, O., Cohen, G., Mora, T. (eds.) AAECC 1993. LNCS, vol.\u00a0673, pp. 121\u2013131. Springer, Heidelberg (1993)"},{"key":"19_CR18","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"issue":"2","key":"19_CR19","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theoret. Comput. Sci.\u00a010(2), 111\u2013121 (1980)","journal-title":"Theoret. Comput. Sci."},{"issue":"6","key":"19_CR20","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1145\/504794.504798","volume":"48","author":"M. Frick","year":"2001","unstructured":"Frick, M., Grohe, M.: Deciding first-order properties of locally tree-decomposable structures. J. ACM\u00a048(6), 1184\u20131206 (2001)","journal-title":"J. ACM"},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"Grohe, M.: Computing crossing numbers in quadratic time. In: STOC, pp. 231\u2013236 (2001)","DOI":"10.1145\/380752.380805"},{"issue":"2","key":"19_CR22","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/j.jcss.2003.07.008","volume":"68","author":"M. Grohe","year":"2004","unstructured":"Grohe, M.: Computing crossing numbers in quadratic time. J. Comput. Syst. Sci.\u00a068(2), 285\u2013302 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"19_CR23","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kawarabayashi, K., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter tractable. In: Proceedings of the 43nd ACM Symposium on Theory of Computing, pp. 479\u2013488 (2011)","DOI":"10.1145\/1993636.1993700"},{"issue":"1","key":"19_CR24","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.disopt.2010.05.003","volume":"8","author":"S. Guillemot","year":"2011","unstructured":"Guillemot, S.: FPT algorithms for path-transversal and cycle-transversal problems. Discrete Optimization\u00a08(1), 61\u201371 (2011)","journal-title":"Discrete Optimization"},{"issue":"8","key":"19_CR25","doi-asserted-by":"publisher","first-page":"1386","DOI":"10.1016\/j.jcss.2006.02.001","volume":"72","author":"J. Guo","year":"2006","unstructured":"Guo, J., Gramm, J., H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci.\u00a072(8), 1386\u20131396 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"19_CR26","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1006\/jctb.1995.1045","volume":"65","author":"J. Gustedt","year":"1995","unstructured":"Gustedt, J.: Well quasi ordering finite posets and formal languages. J. Comb. Theory, Ser. B\u00a065(1), 111\u2013124 (1995)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"3","key":"19_CR27","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/S0166-218X(98)00036-5","volume":"85","author":"D. Hartvigsen","year":"1998","unstructured":"Hartvigsen, D.: The planar multiterminal cut problem. Discrete Applied Mathematics\u00a085(3), 203\u2013222 (1998)","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"19_CR28","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? Journal of Computer and System Sciences\u00a063(4), 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR29","doi-asserted-by":"crossref","unstructured":"Johnson, D.S.: A catalog of complexity classes. In: Handbook of Theoretical Computer Science. in Algorithms and Complexity, vol. (A), pp. 67\u2013161 (1990)","DOI":"10.1016\/B978-0-444-88071-0.50007-2"},{"key":"19_CR30","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Reed, B.A.: Computing crossing number in linear time. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007), pp. 382\u2013390. ACM (2007)","DOI":"10.1145\/1250790.1250848"},{"key":"19_CR31","doi-asserted-by":"crossref","unstructured":"Klein, P.N., Marx, D.: Solving planar k-terminal cut in \n                    \n                      \n                    \n                    ${O}(n^{c \\sqrt{k}})$\n                   time. To appear in ICALP 2012 (2012)","DOI":"10.1007\/978-3-642-31594-7_48"},{"issue":"1-3","key":"19_CR32","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/S0012-365X(97)00147-7","volume":"182","author":"M.A. Langston","year":"1998","unstructured":"Langston, M.A., Plaut, B.C.: On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory. Discrete Mathematics\u00a0182(1-3), 191\u2013196 (1998)","journal-title":"Discrete Mathematics"},{"key":"19_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1007\/978-3-642-22006-7_66","volume-title":"Automata, Languages and Programming","author":"D. Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D.: Clustering with Local Restrictions. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 785\u2013797. Springer, Heidelberg (2011)"},{"key":"19_CR34","doi-asserted-by":"crossref","unstructured":"Marx, D.: A tight lower bound for planar multiway cut with fixed number of terminals. To appear in ICALP 2012 (2012)","DOI":"10.1007\/978-3-642-31594-7_57"},{"issue":"3","key":"19_CR35","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theoret. Comput. Sci.\u00a0351(3), 394\u2013406 (2006)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"19_CR36","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/S0020-0190(00)00172-1","volume":"79","author":"C. McCartin","year":"2001","unstructured":"McCartin, C.: An improved algorithm for the jump number problem. Inf. Process. Lett.\u00a079(2), 87\u201392 (2001)","journal-title":"Inf. Process. Lett."},{"key":"19_CR37","series-title":"Oxford Lecture Series in Mathematics and its Applications","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and its Applications, vol.\u00a031. Oxford University Press, Oxford (2006)"},{"issue":"4","key":"19_CR38","doi-asserted-by":"publisher","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.\u00a067(4), 757\u2013771 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"19_CR39","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths proble. J. Combin. Theory Ser. B\u00a063(1), 65\u2013110 (1995)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"19_CR40","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.jctb.2009.07.003","volume":"100","author":"N. Robertson","year":"2010","unstructured":"Robertson, N., Seymour, P.D.: Graph minors XXIII. Nash-Williams\u2019 immersion conjecture. J. Comb. Theory, Ser. B\u00a0100(2), 181\u2013205 (2010)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"4","key":"19_CR41","doi-asserted-by":"publisher","first-page":"780","DOI":"10.1137\/S0097539792224061","volume":"23","author":"A. Schrijver","year":"1994","unstructured":"Schrijver, A.: Finding k disjoint paths in a directed planar graph. SIAM J. Comput.\u00a023(4), 780\u2013788 (1994)","journal-title":"SIAM J. Comput."},{"key":"19_CR42","unstructured":"Scott, A.: On the parameterized complexity of finding short winning strategies in combinatorial games. Ph.D. thesis, University of Victoria (2009)"},{"key":"19_CR43","doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S.: A quadratic kernel for feedback vertex set. ACM Trans. Algorithms 6(2) (2010)","DOI":"10.1145\/1721837.1721848"},{"key":"19_CR44","doi-asserted-by":"crossref","unstructured":"Vardy, A.: Algorithmic complexity in coding theory and the minimum distance problem. In: STOC, pp. 92\u2013109 (1997)","DOI":"10.1145\/258533.258559"},{"key":"19_CR45","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1017\/S0963548300000882","volume":"2","author":"D. Vertigan","year":"1993","unstructured":"Vertigan, D., Whittle, G.: Recognizing polymatroids associated with hypergraphs. Combinatorics, Probability & Computing\u00a02, 519\u2013530 (1993)","journal-title":"Combinatorics, Probability & Computing"}],"container-title":["Lecture Notes in Computer Science","The Multivariate Algorithmic Revolution and Beyond"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-30891-8_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T20:33:40Z","timestamp":1558298020000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-30891-8_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642308901","9783642308918"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-30891-8_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}