{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T21:50:33Z","timestamp":1785016233976,"version":"3.55.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,8,1]],"date-time":"2014-08-01T00:00:00Z","timestamp":1406851200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["306992"],"award-info":[{"award-number":["306992"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2014,8]]},"abstract":"<jats:p>\n            Many graph problems were first shown to be fixed-parameter tractable using the results of Robertson and Seymour on graph minors. We show that the combination of finite, computable obstruction sets and efficient order tests is not just one way of obtaining strongly uniform FPT algorithms, but that all of FPT may be captured in this way. Our new characterization of FPT has a strong connection to the theory of kernelization, as we prove that problems with polynomial kernels can be characterized by obstruction sets whose elements have polynomial size. Consequently we investigate the interplay between the sizes of problem kernels and the sizes of the elements of such obstruction sets, obtaining several examples of how results in one area yield new insights in the other. We show how exponential-size minor-minimal obstructions for pathwidth\n            <jats:italic>k<\/jats:italic>\n            form the crucial ingredient in a novel\n            <jats:sc>or<\/jats:sc>\n            -cross-composition for\n            <jats:italic>k<\/jats:italic>\n            -\n            <jats:sc>Pathwidth<\/jats:sc>\n            , complementing the trivial\n            <jats:sc>and<\/jats:sc>\n            -composition that is known for this problem. In the other direction, we show that\n            <jats:sc>or<\/jats:sc>\n            -cross-compositions into a parameterized problem can be used to rule out the existence of efficiently generated quasi-orders on its instances that characterize the\n            <jats:sc>no<\/jats:sc>\n            -instances by polynomial-size obstructions.\n          <\/jats:p>","DOI":"10.1145\/2635820","type":"journal-article","created":{"date-parts":[[2014,8,21]],"date-time":"2014-08-21T12:19:12Z","timestamp":1408623552000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["FPT is characterized by useful obstruction sets"],"prefix":"10.1145","volume":"6","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[{"name":"Charles Darwin University, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bart M. P.","family":"Jansen","sequence":"additional","affiliation":[{"name":"University of Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1328-0"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1747997"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of 28th STACS. 165--176","author":"Bodlaender Hans L.","year":"2011","unstructured":"Hans L. Bodlaender , Bart M. P. Jansen , and Stefan Kratsch . 2011 . Cross-composition: a new technique for kernelization lower bounds . In Proceedings of 28th STACS. 165--176 . Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. 2011. Cross-composition: a new technique for kernelization lower bounds. In Proceedings of 28th STACS. 165--176."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31155-0_31"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/120903518"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0049"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0406014"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00300-9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1186"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411511"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_22"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095122"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806725"},{"key":"e_1_2_1_18_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2010. Graph Theory 4 th Ed. Springer-Verlag , Heidelberg . Reinhard Diestel. 2010. Graph Theory 4th Ed. Springer-Verlag, Heidelberg.","edition":"4"},{"key":"e_1_2_1_19_1","first-page":"1199","article-title":"Too many minor order obstructions","volume":"3","author":"Dinneen Michael J.","year":"1997","unstructured":"Michael J. Dinneen . 1997 . Too many minor order obstructions . J. Univers. Comput. Sci. 3 , 1199 -- 1206 . Michael J. Dinneen. 1997. Too many minor order obstructions. J. Univers. Comput. Sci. 3, 1199--1206.","journal-title":"J. Univers. Comput. Sci."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00083-2"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.01.003"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.v41:3"},{"key":"e_1_2_1_23_1","volume-title":"Fellows","author":"Downey Rod","year":"1999","unstructured":"Rod Downey and Michael R . Fellows . 1999 . Parameterized Complexity. Springer , New York. Rod Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer, New York."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.71"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.09.014"},{"key":"e_1_2_1_26_1","first-page":"181","article-title":"On the minimal number of vertices representing the edges of a graph","volume":"6","author":"Erd\u0151s Paul","year":"1961","unstructured":"Paul Erd\u0151s and Tibor Gallai . 1961 . On the minimal number of vertices representing the edges of a graph . Publ. Math. Inst. Hung. Acad. Sci., Ser. A 6 , 181 -- 203 . Paul Erd\u0151s and Tibor Gallai. 1961. On the minimal number of vertices representing the edges of a graph. Publ. Math. Inst. Hung. Acad. Sci., Ser. A 6, 181--203.","journal-title":"Publ. Math. Inst. Hung. Acad. Sci., Ser. A"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2012.04.008"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/44483.44491"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63528"},{"key":"e_1_2_1_30_1","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer-Verlag , New York . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag, New York."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.09.004"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.62"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"e_1_2_1_34_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company , New York. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/060668092"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095125"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03898-8_19"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2013.08.005"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90234-M"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095126"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2635808"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31155-0_32"},{"key":"e_1_2_1_44_1","unstructured":"Stefan Kratsch and Magnus Wahlstr\u00f6m. 2011. The AND-conjecture may be necessary. In Parameterized Complexity Newsletter. FPT Wiki Darwin.  Stefan Kratsch and Magnus Wahlstr\u00f6m. 2011. The AND-conjecture may be necessary. In Parameterized Complexity Newsletter . FPT Wiki Darwin."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.46"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1788"},{"key":"e_1_2_1_47_1","first-page":"1","article-title":"On the size of minimal unsatisfiable formulas","volume":"16","author":"Lee Choongbum","year":"2009","unstructured":"Choongbum Lee . 2009 . On the size of minimal unsatisfiable formulas . Electr. J. Comb. 16 , 1 . Choongbum Lee. 2009. On the size of minimal unsatisfiable formulas. Electr. J. Comb. 16, 1.","journal-title":"Electr. J. Comb."},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Daniel Lokshtanov Neeldhara Misra and Saket Saurabh. 2012. Kernelization - preprocessing with a guarantee. In The Multivariate Algorithmic Revolution and Beyond 129--161.  Daniel Lokshtanov Neeldhara Misra and Saket Saurabh. 2012. Kernelization - preprocessing with a guarantee. In The Multivariate Algorithmic Revolution and Beyond 129--161.","DOI":"10.1007\/978-3-642-30891-8_10"},{"key":"e_1_2_1_49_1","volume-title":"Plummer","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1986","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz and Michael D . Plummer . 1986 . Matching Theory. Annals of Discrete Mathematics, Vol. 29 . North-Holland Publishing Co. , Amsterdam, The Netherlands. L\u00e1szl\u00f3 Lov\u00e1sz and Michael D. Plummer. 1986. Matching Theory. Annals of Discrete Mathematics, Vol. 29. North-Holland Publishing Co., Amsterdam, The Netherlands."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90079-5"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.09.018"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)90092-2"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90020-8"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2635820","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2635820","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:03:44Z","timestamp":1750273424000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2635820"}},"subtitle":["Connecting algorithms, kernels, and quasi-orders"],"short-title":[],"issued":{"date-parts":[[2014,8]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["10.1145\/2635820"],"URL":"https:\/\/doi.org\/10.1145\/2635820","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8]]},"assertion":[{"value":"2013-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}