{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:09Z","timestamp":1759639089273},"publisher-location":"Berlin, Heidelberg","reference-count":98,"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_20","type":"book-chapter","created":{"date-parts":[[2012,6,18]],"date-time":"2012-06-18T09:24:05Z","timestamp":1340011445000},"page":"469-496","source":"Crossref","is-referenced-by-count":6,"title":["What\u2019s Next? Future Directions in Parameterized Complexity"],"prefix":"10.1007","author":[{"given":"D\u00e1niel","family":"Marx","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"16","key":"20_CR1","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1016\/j.ipl.2010.04.020","volume":"110","author":"F.N. Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.N.: An improved kernelization algorithm for r-set packing. Inf. Process. Lett.\u00a0110(16), 621\u2013624 (2010)","journal-title":"Inf. Process. Lett."},{"issue":"7","key":"20_CR2","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1016\/j.jcss.2009.09.002","volume":"76","author":"F.N. Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.N.: A kernelization algorithm for d-hitting set. J. Comput. Syst. Sci.\u00a076(7), 524\u2013531 (2010)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"20_CR3","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.jalgor.2004.03.005","volume":"52","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fernau, H., Niedermeier, R.: Parameterized complexity: exponential speed-up for planar graph problems. J. Algorithms\u00a052(1), 26\u201356 (2004)","journal-title":"J. Algorithms"},{"issue":"2","key":"20_CR4","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.jalgor.2003.10.001","volume":"52","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fiala, J.: Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. J. Algorithms\u00a052(2), 134\u2013151 (2004)","journal-title":"J. Algorithms"},{"key":"20_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-3-642-02927-1_6","volume-title":"Automata, Languages and Programming","author":"N. Alon","year":"2009","unstructured":"Alon, N., Lokshtanov, D., Saurabh, S.: Fast FAST. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 49\u201358. Springer, Heidelberg (2009)"},{"issue":"4","key":"20_CR6","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. ACM\u00a042(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"issue":"2","key":"20_CR7","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00373-005-0627-y","volume":"22","author":"J. Bar\u00e1t","year":"2006","unstructured":"Bar\u00e1t, J.: Directed path-width and monotonicity in digraph searching. Graphs and Combinatorics\u00a022(2), 161\u2013172 (2006)","journal-title":"Graphs and Combinatorics"},{"key":"20_CR8","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1613\/jair.638","volume":"12","author":"A. Becker","year":"2000","unstructured":"Becker, A., Bar-Yehuda, R., Geiger, D.: Randomized algorithms for the loop cutset problem. J. Artif. Intell. Res. (JAIR)\u00a012, 219\u2013234 (2000)","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"key":"20_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1007\/11672142_43","volume-title":"STACS 2006","author":"D. Berwanger","year":"2006","unstructured":"Berwanger, D., Dawar, A., Hunter, P., Kreutzer, S.: DAG-Width and Parity Games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 524\u2013536. Springer, Heidelberg (2006)"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected hamiltonicity. In: Proceedings of the 51st Annual Symposium on Foundations of Computer Science, FOCS 2010, pp. 173\u2013182 (2010)","DOI":"10.1109\/FOCS.2010.24"},{"issue":"1","key":"20_CR11","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1142\/S0129054194000049","volume":"5","author":"H.L. Bodlaender","year":"1994","unstructured":"Bodlaender, H.L.: On disjoint cycles. Int. J. Found. Comput. Sci.\u00a05(1), 59\u201368 (1994)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"20_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-642-11269-0_2","volume-title":"Parameterized and Exact Computation","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L.: Kernelization: New Upper and Lower Bound Techniques. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 17\u201337. Springer, Heidelberg (2009)"},{"issue":"8","key":"20_CR13","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci.\u00a075(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. In: Proceedings of the 50th Annual Symposium on Foundations of Computer Science, FOCS 2009, pp. 629\u2013638 (2009)","DOI":"10.1109\/FOCS.2009.46"},{"issue":"4","key":"20_CR15","doi-asserted-by":"publisher","first-page":"817","DOI":"10.1007\/s00453-010-9421-1","volume":"61","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Heggernes, P., Villanger, Y.: Faster parameterized algorithms for minimum fill-in. Algorithmica\u00a061(4), 817\u2013838 (2011)","journal-title":"Algorithmica"},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Bousquet, N., Daligault, J., Thomass\u00e9, S.: Multicut is FPT. In: Proceedings of the 43rd Annual Symposium on Theory of Computing, STOC 2011, pp. 459\u2013468 (2011)","DOI":"10.1145\/1993636.1993698"},{"issue":"4","key":"20_CR17","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L. Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inform. Process. Lett.\u00a058(4), 171\u2013176 (1996)","journal-title":"Inform. Process. Lett."},{"key":"20_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-11269-0_6","volume-title":"Parameterized and Exact Computation","author":"C. Calabro","year":"2009","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: The Complexity of Satisfiability of Small Depth Circuits. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 75\u201385. Springer, Heidelberg (2009)"},{"key":"20_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/978-3-642-17493-3_9","volume-title":"Parameterized and Exact Computation","author":"K. Cechl\u00e1rov\u00e1","year":"2010","unstructured":"Cechl\u00e1rov\u00e1, K., Schlotter, I.: Computing the Deficiency of Housing Markets with Duplicate Houses. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol.\u00a06478, pp. 72\u201383. Springer, Heidelberg (2010)"},{"issue":"4","key":"20_CR20","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1137\/050646354","volume":"37","author":"J. Chen","year":"2007","unstructured":"Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. SIAM J. Comput.\u00a037(4), 1077\u20131106 (2007)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"20_CR21","doi-asserted-by":"publisher","first-page":"1188","DOI":"10.1016\/j.jcss.2008.05.002","volume":"74","author":"J. Chen","year":"2008","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci.\u00a074(7), 1188\u20131198 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"20_CR22","first-page":"212","volume-title":"Proceedings of the 36th Annual Symposium on Theory of Computing, STOC 2004","author":"J. Chen","year":"2004","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Linear FPT reductions and computational lower bounds. In: Proceedings of the 36th Annual Symposium on Theory of Computing, STOC 2004, pp. 212\u2013221. ACM, New York (2004)"},{"issue":"40-42","key":"20_CR23","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J. Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci.\u00a0411(40-42), 3736\u20133756 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/978-3-540-73951-7_43","volume-title":"Algorithms and Data Structures","author":"J. Chen","year":"2007","unstructured":"Chen, J., Liu, Y., Lu, S.: An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol.\u00a04619, pp. 495\u2013506. Springer, Heidelberg (2007)"},{"key":"20_CR25","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. J. ACM 55(5) (2008)","DOI":"10.1145\/1411509.1411511"},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"Chitnis, R., Hajiaghayi, M., Marx, D.: Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 1713\u20131725 (2012)","DOI":"10.1137\/1.9781611973099.136"},{"issue":"1","key":"20_CR27","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.jctb.2011.05.001","volume":"102","author":"M. Chudnovsky","year":"2012","unstructured":"Chudnovsky, M., Fradkin, A.O., Seymour, P.D.: Tournament immersion and cutwidth. J. Comb. Theory, Ser. B\u00a0102(1), 93\u2013101 (2012)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"20_CR28","unstructured":"Chudnovsky, M., Scott, A., Seymour, P.: Vertex disjoint paths in tournaments (manuscript)"},{"key":"20_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-3-642-25870-1_13","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M. Cygan","year":"2011","unstructured":"Cygan, M., Marx, D., Pilipczuk, M., Pilipczuk, M., Schlotter, I.: Parameterized Complexity of Eulerian Deletion Problems. In: Kolman, P., Kratochv\u00edl, J. (eds.) WG 2011. LNCS, vol.\u00a06986, pp. 131\u2013142. Springer, Heidelberg (2011)"},{"key":"20_CR30","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 150\u2013159 (2011)","DOI":"10.1109\/FOCS.2011.23"},{"key":"20_CR31","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)"},{"key":"20_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/978-3-642-21581-0_4","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2011","author":"E. Dantsin","year":"2011","unstructured":"Dantsin, E., Hirsch, E.A.: Satisfiability Certificates Verifiable in Subexponential Time. In: Sakallah, K.A., Simon, L. (eds.) SAT 2011. LNCS, vol.\u00a06695, pp. 19\u201332. Springer, Heidelberg (2011)"},{"issue":"3","key":"20_CR33","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s00224-007-1345-z","volume":"41","author":"F. Dehne","year":"2007","unstructured":"Dehne, F., Fellows, M., Langston, M., Rosamond, F., Stevens, K.: An \n                    \n                      \n                    \n                    $O(2\\sp{O(k)}n\\sp 3)$\n                   FPT algorithm for the undirected feedback vertex set problem. Theory Comput. Syst.\u00a041(3), 479\u2013492 (2007)","journal-title":"Theory Comput. Syst."},{"key":"20_CR34","doi-asserted-by":"crossref","unstructured":"Dell, H., Marx, D.: Kernelization of packing problems. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 68\u201381 (2012)","DOI":"10.1137\/1.9781611973099.6"},{"key":"20_CR35","doi-asserted-by":"crossref","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: Proceedings of the 42nd Annual Symposium on Theory of Computing, STOC 2010, pp. 251\u2013260 (2010)","DOI":"10.1145\/1806689.1806725"},{"issue":"3","key":"20_CR36","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1093\/comjnl\/bxm033","volume":"51","author":"E.D. Demaine","year":"2008","unstructured":"Demaine, E.D., Hajiaghayi, M.: The bidimensionality theory and its algorithmic applications. Comput. J.\u00a051(3), 292\u2013302 (2008)","journal-title":"Comput. J."},{"issue":"2","key":"20_CR37","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1137\/040616929","volume":"20","author":"E.D. Demaine","year":"2006","unstructured":"Demaine, E.D., Hajiaghayi, M., Thilikos, D.M.: The bidimensional theory of bounded-genus graphs. SIAM J. Discrete Math.\u00a020(2), 357\u2013371 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"20_CR38","unstructured":"Demaine, E.D., Hajiaghayi, M.T.: Bidimensionality: new connections between FPT algorithms and PTASs. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pp. 590\u2013601 (2005)"},{"key":"20_CR39","unstructured":"Dorn, F.: Planar subgraph isomorphism revisited. In: Proceedings 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010. Dagstuhl Seminar Proceedings, vol.\u00a05, pp. 263\u2013274. Leibniz-Zentrum f\u00fcr Informatik, Schloss Dagstuhl, Germany (2010)"},{"key":"20_CR40","unstructured":"Dorn, F., Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs. In: Proceedings 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, Dagstuhl Seminar Proceedings, vol.\u00a05, pp. 251\u2013262. Leibniz-Zentrum f\u00fcr Informatik, Schloss Dagstuhl, Germany (2010)"},{"key":"20_CR41","series-title":"LNCS","first-page":"91","volume-title":"Fellows Festschrift","author":"R. Downey","year":"2012","unstructured":"Downey, R.: A Basic Parameterized Complexity Primer. In: Bodlaender, H.L., et al. (eds.) Fellows Festschrift. LNCS, vol.\u00a07370, pp. 91\u2013128. Springer, Heidelberg (2012)"},{"key":"20_CR42","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness. In: Proceedings of the Twenty-first Manitoba Conference on Numerical Mathematics and Computing, Winnipeg, MB, vol.\u00a087, pp. 161\u2013178 (1992)"},{"key":"20_CR43","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-1-4612-2566-9_7","volume-title":"Proceedings of the Second Cornell Workshop on Feasible Mathematics, Feasible Mathematics II","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized computational feasibility. In: Clote, P., Remmel, J. (eds.) Proceedings of the Second Cornell Workshop on Feasible Mathematics, Feasible Mathematics II, pp. 219\u2013244. Birkh\u00e4user, Boston (1995)"},{"key":"20_CR44","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"20_CR45","doi-asserted-by":"crossref","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl. 3(3) (1999)","DOI":"10.7155\/jgaa.00014"},{"key":"20_CR46","unstructured":"Feige, U.: Faster FAST (feedback arc set in tournaments). CoRR, abs\/0911.5094 (2009)"},{"key":"20_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/978-3-642-02927-1_39","volume-title":"Automata, Languages and Programming","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Losievskaja, E., Rosamond, F.A., Saurabh, S.: Distortion Is Fixed Parameter Tractable. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 463\u2013474. Springer, Heidelberg (2009)"},{"issue":"2","key":"20_CR48","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.ic.2010.11.026","volume":"209","author":"M.R. Fellows","year":"2011","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F.A., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. Inf. Comput.\u00a0209(2), 143\u2013153 (2011)","journal-title":"Inf. Comput."},{"issue":"4","key":"20_CR49","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1137\/S0097539703427203","volume":"33","author":"J. Flum","year":"2004","unstructured":"Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM J. Comput.\u00a033(4), 892\u2013922 (2004)","journal-title":"SIAM J. Comput."},{"key":"20_CR50","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"20_CR51","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Algorithmic lower bounds for problems parameterized with clique-width. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 493\u2013502 (2010)","DOI":"10.1137\/1.9781611973075.42"},{"key":"20_CR52","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms, 1st edn. Springer (2010)","DOI":"10.1007\/978-3-642-16533-7_1"},{"key":"20_CR53","unstructured":"Fomin, F.V., Pilipzuk, M.: Jungles, bundles, and fixed parameter tractability. CoRR, abs\/1112. 1538 (2011)"},{"key":"20_CR54","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Villanger, Y.: Subexponential parameterized algorithm for minimum fill-in. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 1737\u20131746 (2012)","DOI":"10.1137\/1.9781611973099.138"},{"key":"20_CR55","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: Proceedings of the 40th Annual Symposium on Theory of Computing, STOC 2008, pp. 133\u2013142 (2008)","DOI":"10.1145\/1374376.1374398"},{"key":"20_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-17493-3_14","volume-title":"Parameterized and Exact Computation","author":"R. Ganian","year":"2010","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P., Kneis, J., Meister, D., Obdr\u017e\u00e1lek, J., Rossmanith, P., Sikdar, S.: Are There Any Good Digraph Width Measures? In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol.\u00a06478, pp. 135\u2013146. Springer, Heidelberg (2010)"},{"issue":"1","key":"20_CR57","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s00453-003-1028-3","volume":"37","author":"J. Gramm","year":"2003","unstructured":"Gramm, J., Niedermeier, R., Rossmanith, P.: Fixed-parameter algorithms for closest string and related problems. Algorithmica\u00a037(1), 25\u201342 (2003)","journal-title":"Algorithmica"},{"issue":"1","key":"20_CR58","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":"20_CR59","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. System Sci.\u00a072(8), 1386\u20131396 (2006)","journal-title":"J. Comput. System Sci."},{"key":"20_CR60","doi-asserted-by":"crossref","unstructured":"Hertli, T.: 3-SAT faster and simpler \u2014 Unique-SAT bounds for PPSZ hold in general. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 277\u2013284 (2011)","DOI":"10.1109\/FOCS.2011.22"},{"issue":"1","key":"20_CR61","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1093\/comjnl\/bxm040","volume":"51","author":"F. H\u00fcffner","year":"2008","unstructured":"H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Techniques for practical fixed-parameter algorithms. Comput. J.\u00a051(1), 7\u201325 (2008)","journal-title":"Comput. J."},{"issue":"3","key":"20_CR62","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/j.tcs.2008.02.038","volume":"399","author":"P. Hunter","year":"2008","unstructured":"Hunter, P., Kreutzer, S.: Digraph measures: Kelly decompositions, games, and orderings. Theor. Comput. Sci.\u00a0399(3), 206\u2013219 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"20_CR63","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. System Sci.\u00a063(4), 512\u2013530 (2001)","journal-title":"Comput. System Sci."},{"issue":"1","key":"20_CR64","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T. Johnson","year":"2001","unstructured":"Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed tree-width. J. Comb. Theory, Ser. B\u00a082(1), 138\u2013154 (2001)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"5","key":"20_CR65","doi-asserted-by":"publisher","first-page":"1906","DOI":"10.1137\/S0097539796303044","volume":"28","author":"H. Kaplan","year":"1999","unstructured":"Kaplan, H., Shamir, R., Tarjan, R.E.: Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J. Comput.\u00a028(5), 1906\u20131922 (1999)","journal-title":"SIAM J. Comput."},{"key":"20_CR66","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K.: Planarity allowing few error vertices in linear time. In: Proceedings of the 50th Annual Symposium on Foundations of Computer Science, FOCS 2009, pp. 639\u2013648 (2009)","DOI":"10.1109\/FOCS.2009.45"},{"issue":"2","key":"20_CR67","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1016\/S0304-3975(01)00414-5","volume":"289","author":"S. Khot","year":"2002","unstructured":"Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci.\u00a0289(2), 997\u20131008 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR68","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2\u2009\u2212\u2009\u03b5. In: 18th Annual IEEE Conference on Computational Complexity (CCC 2003), pp. 371\u2013378 (2003)"},{"key":"20_CR69","doi-asserted-by":"crossref","unstructured":"Kratsch, S.: Co-nondeterminism in compositions: A kernelization lower bound for a Ramsey-type problem. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 114\u2013122 (2012)","DOI":"10.1137\/1.9781611973099.10"},{"key":"20_CR70","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Pilipczuk, M., Pilipczuk, M., Wahlstr\u00f6m, M.: Fixed-parameter tractability of multicut in directed acyclic graphs. CoRR, abs\/1202.5749 (2012)","DOI":"10.1007\/978-3-642-31594-7_49"},{"issue":"35","key":"20_CR71","doi-asserted-by":"publisher","first-page":"4688","DOI":"10.1016\/j.tcs.2011.05.003","volume":"412","author":"S. Kreutzer","year":"2011","unstructured":"Kreutzer, S., Ordyniak, S.: Digraph decompositions and monotonicity in digraph searching. Theor. Comput. Sci.\u00a0412(35), 4688\u20134703 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR72","doi-asserted-by":"crossref","unstructured":"Kreutzer, S., Tazari, S.: Directed nowhere dense classes of graphs. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 1552\u20131562 (2012)","DOI":"10.1137\/1.9781611973099.123"},{"key":"20_CR73","series-title":"LNCS","first-page":"3","volume-title":"Fellows Festschrift","author":"M.A. Langston","year":"2012","unstructured":"Langston, M.A.: Fixed-Parameter Tractability, A Prehistory. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) Fellows Festschrift. LNCS, vol.\u00a07370, pp. 3\u201316. Springer, Heidelberg (2012)"},{"key":"20_CR74","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp. 777\u2013789 (2011)","DOI":"10.1137\/1.9781611973082.61"},{"key":"20_CR75","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Slightly superexponential parameterized problems. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp. 760\u2013776 (2011)","DOI":"10.1137\/1.9781611973082.60"},{"key":"20_CR76","series-title":"LNCS","first-page":"129","volume-title":"Fellows Festschrift","author":"D. Lokshtanov","year":"2012","unstructured":"Lokshtanov, D., Misra, N., Saurabh, S.: Kernelization \u2013 Preprocessing with a Guarantee. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) Fellows Festschrift. LNCS, vol.\u00a07370, pp. 129\u2013161. Springer, Heidelberg (2012)"},{"issue":"4","key":"20_CR77","doi-asserted-by":"publisher","first-page":"1432","DOI":"10.1137\/080739069","volume":"39","author":"B. Ma","year":"2009","unstructured":"Ma, B., Sun, X.: More efficient algorithms for closest string and substring problems. SIAM J. Comput.\u00a039(4), 1432\u20131443 (2009)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"20_CR78","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."},{"key":"20_CR79","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), pp. 338\u2013348 (2007)","DOI":"10.1109\/FOCS.2007.26"},{"issue":"4","key":"20_CR80","doi-asserted-by":"publisher","first-page":"1382","DOI":"10.1137\/060673898","volume":"38","author":"D. Marx","year":"2008","unstructured":"Marx, D.: Closest substring problems with small distances. SIAM Journal on Computing\u00a038(4), 1382\u20131410 (2008)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"20_CR81","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 of Computing\u00a06(1), 85\u2013112 (2010)","journal-title":"Theory of Computing"},{"key":"20_CR82","doi-asserted-by":"crossref","unstructured":"Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: Proceedings of the 43rd Annual Symposium on Theory of Computing, STOC 2011, pp. 469\u2013478 (2011)","DOI":"10.1145\/1993636.1993699"},{"key":"20_CR83","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1007\/s00453-010-9484-z","volume":"62","author":"D. Marx","year":"2012","unstructured":"Marx, D., Schlotter, I.: Obtaining a planar graph by vertex deletion. Algorithmica\u00a062, 807\u2013822 (2012)","journal-title":"Algorithmica"},{"issue":"1","key":"20_CR84","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.disopt.2010.10.001","volume":"8","author":"N. Misra","year":"2011","unstructured":"Misra, N., Raman, V., Saurabh, S.: Lower bounds on kernelization. Discrete Optimization\u00a08(1), 110\u2013128 (2011)","journal-title":"Discrete Optimization"},{"key":"20_CR85","series-title":"North-Holland Math. Stud","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0304-0208(08)73110-4","volume-title":"Analysis and design of algorithms for combinatorial problems (Udine, 1982)","author":"B. Monien","year":"1985","unstructured":"Monien, B.: How to find long paths efficiently. In: Analysis and design of algorithms for combinatorial problems (Udine, 1982). North-Holland Math. Stud, vol.\u00a0109, pp. 239\u2013254. North-Holland, Amsterdam (1985)"},{"key":"20_CR86","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G.L. Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter Jr., L.E.: Vertex packings: structural properties and algorithms. Math. Programming\u00a08, 232\u2013248 (1975)","journal-title":"Math. Programming"},{"key":"20_CR87","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)"},{"key":"20_CR88","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Williams, R.: On the possibility of faster SAT algorithms. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 1065\u20131075 (2010)","DOI":"10.1137\/1.9781611973075.86"},{"key":"20_CR89","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudl\u00e1k, P.: On the complexity of circuit satisfiability. In: Proceedings of the 42nd Annual Symposium on Theory of Computing, STOC 2010, pp. 241\u2013250 (2010)","DOI":"10.1145\/1806689.1806724"},{"issue":"3","key":"20_CR90","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1016\/j.tcs.2005.10.010","volume":"351","author":"V. Raman","year":"2006","unstructured":"Raman, V., Saurabh, S.: Parameterized algorithms for feedback set problems and their duals in tournaments. Theor. Comput. Sci.\u00a0351(3), 446\u2013458 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"8","key":"20_CR91","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/j.jcss.2009.04.002","volume":"75","author":"I. Razgon","year":"2009","unstructured":"Razgon, I., O\u2019Sullivan, B.: Almost 2-SAT is fixed-parameter tractable. J. Comput. Syst. Sci.\u00a075(8), 435\u2013450 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"20_CR92","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B. Reed","year":"2004","unstructured":"Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Operations Research Letters\u00a032(4), 299\u2013301 (2004)","journal-title":"Operations Research Letters"},{"issue":"1","key":"20_CR93","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 problem. J. Combin. Theory Ser. B\u00a063(1), 65\u2013110 (1995)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"20_CR94","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N. Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Combin. Theory Ser. B\u00a092(2), 325\u2013357 (2004)","journal-title":"J. Combin. Theory Ser. B"},{"key":"20_CR95","unstructured":"Scheffler, P.: A practical linear time algorithm for disjoint paths in graphs with bounded tree-width. Tech. Rep. 396\/1994, Technical University of Berlin (1994)"},{"key":"20_CR96","series-title":"LNCS","first-page":"228","volume-title":"Fellows Festschrift","author":"D.M. Thilikos","year":"2012","unstructured":"Thilikos, D.M.: Graph Minors and Parameterized Algorithm Design. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) Fellows Festschrift. LNCS, vol.\u00a07370, pp. 228\u2013256. Springer, Heidelberg (2012)"},{"issue":"6","key":"20_CR97","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ipl.2008.11.004","volume":"109","author":"R. Williams","year":"2009","unstructured":"Williams, R.: Finding paths of length k in O*(2\n                    k\n                  ) time. Inf. Process. Lett.\u00a0109(6), 315\u2013318 (2009)","journal-title":"Inf. Process. Lett."},{"key":"20_CR98","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C.K. Yap","year":"1983","unstructured":"Yap, C.K.: Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci.\u00a026, 287\u2013300 (1983)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","The Multivariate Algorithmic Revolution and Beyond"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-30891-8_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T08:46:40Z","timestamp":1556873200000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-30891-8_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642308901","9783642308918"],"references-count":98,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-30891-8_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}