{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:48:17Z","timestamp":1770994097877,"version":"3.50.1"},"reference-count":105,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T00:00:00Z","timestamp":1736035200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T00:00:00Z","timestamp":1736035200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>For a set of graphs <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$${\\mathcal {H}}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>H<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, a graph <jats:italic>G<\/jats:italic> is <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$${\\mathcal {H}}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>H<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-subgraph-free if <jats:italic>G<\/jats:italic> does not contain any graph from\u00a0<jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$${{{\\mathcal {H}}}}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>H<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> as a subgraph. We propose general and easy-to-state conditions on graph problems that explain a large set of results for <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$${\\mathcal {H}}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>H<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-subgraph-free graphs. Namely, a graph problem must be efficiently solvable on graphs of bounded treewidth, computationally hard on subcubic graphs, and computational hardness must be preserved under edge subdivision of subcubic graphs. Our meta-classification says that if a graph problem\u00a0<jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Pi $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03a0<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> satisfies all three conditions, then for every finite set <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$${{{\\mathcal {H}}}}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>H<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, it is \u201cefficiently solvable\u201d on <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$${{{\\mathcal {H}}}}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>H<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-subgraph-free graphs if <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$${\\mathcal {H}}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>H<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> contains a disjoint union of one or more paths and subdivided claws, and <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Pi $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03a0<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> is \u201ccomputationally hard\u201d otherwise. We apply our <jats:italic>meta-classification<\/jats:italic> on many well-known partitioning, covering and packing problems, network design problems and width parameter problems to obtain a dichotomy between polynomial-time solvability and -completeness. For distance-metric problems, we obtain a dichotomy between almost-linear-time solvability and having no subquadratic-time algorithm (conditioned on some hardness hypotheses). Apart from capturing a large number of explicitly and implicitly known results in the literature, we also prove a number of new results. Moreover, we perform an extensive comparison between the subgraph framework and the existing frameworks for the minor and topological minor relations, and pose several new open problems and research directions.\n<\/jats:p>","DOI":"10.1007\/s00453-024-01289-2","type":"journal-article","created":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T01:50:06Z","timestamp":1736041806000},"page":"429-464","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Complexity\u00a0Framework\u00a0for\u00a0Forbidden\u00a0Subgraphs I: The Framework"],"prefix":"10.1007","volume":"87","author":[{"given":"Matthew","family":"Johnson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barnaby","family":"Martin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jelle J.","family":"Oostveen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sukanya","family":"Pandey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siani","family":"Smith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik Jan","family":"van Leeuwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,5]]},"reference":[{"key":"1289_CR1","first-page":"377","volume":"2016","author":"A Abboud","year":"2016","unstructured":"Abboud, A., Williams, V.V., Wang, J.R.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. Proc. SODA 2016, 377\u2013391 (2016)","journal-title":"Proc. SODA"},{"key":"1289_CR2","doi-asserted-by":"crossref","unstructured":"Abrishami, T., Alecu, B., Chudnovsky, M., Hajebi, S., Spirkl, S.: Induced subgraphs and tree-decompositions VII. Basic obstructions in $${H}$$-free graphs. J. Combin. Theory, Ser. B 164, 443\u2013472 (2024)","DOI":"10.1016\/j.jctb.2023.10.008"},{"key":"1289_CR3","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/j.jctb.2022.05.009","volume":"157","author":"T Abrishami","year":"2022","unstructured":"Abrishami, T., Chudnovsky, M., Vu\u0161kovi\u0107, K.: Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree. J. Combin. Theory Ser. B 157, 144\u2013175 (2022)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1289_CR4","doi-asserted-by":"crossref","first-page":"R26","DOI":"10.37236\/1779","volume":"11","author":"MO Albertson","year":"2004","unstructured":"Albertson, M.O., Chappell, G.G., Kierstead, H.K., K\u00fcndgen, A., Ramamurthi, R.: Coloring with no 2-Colored $$P_4$$\u2019s. Electron. J. Combin. 11, R26 (2004)","journal-title":"Electron. J. Combin."},{"key":"1289_CR5","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0166-218X(03)00387-1","volume":"132","author":"VE Alekseev","year":"2003","unstructured":"Alekseev, V.E.: On easy and hard hereditary classes of graphs with respect to the independent set problem. Discret. Appl. Math. 132, 17\u201326 (2003)","journal-title":"Discret. Appl. Math."},{"key":"1289_CR6","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/j.tcs.2007.09.013","volume":"389","author":"VE Alekseev","year":"2007","unstructured":"Alekseev, V.E., Boliac, R., Korobitsyn, D.V., Lozin, V.V.: NP-hard graph problems and boundary classes of graphs. Theor. Comput. Sci. 389, 219\u2013236 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"1289_CR7","first-page":"34","volume":"4","author":"VE Alekseev","year":"1992","unstructured":"Alekseev, V.E., Korobitsyn, D.V.: Complexity of some problems on hereditary graph classes. Diskret. Mat. 4, 34\u201340 (1992)","journal-title":"Diskret. Mat."},{"key":"1289_CR8","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12, 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"1289_CR9","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial $$k$$-trees. Discret. Appl. Math. 23, 11\u201324 (1989)","journal-title":"Discret. Appl. Math."},{"issue":"21","key":"1289_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2027216.2027219","volume":"58","author":"M Bateni","year":"2011","unstructured":"Bateni, M., Hajiaghayi, M.T., Marx, D.: Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. J. ACM 58(21), 1\u201321 (2011)","journal-title":"J. ACM"},{"key":"1289_CR11","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0095-8956(91)90068-U","volume":"52","author":"D Bienstock","year":"1991","unstructured":"Bienstock, D., Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a forest. J. Combin. Theory Ser. B 52, 274\u2013283 (1991)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1289_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jagm.1993.1001","volume":"14","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: On linear time minor tests with depth-first search. J. Algorithms 14, 1\u201323 (1993)","journal-title":"J. Algorithms"},{"key":"1289_CR13","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"1289_CR14","unstructured":"Bodlaender, H.L., Bonnet, \u00c9., Jaffke, L., Knop, D., Lima, P.T., Milani\u010d, M., Ordyniak, S., Pandey, S., Such\u00fd, O.: Treewidth is NP-complete on cubic graphs. Proc. IPEC 2023, LIPIcs 285, 7:1\u20137:13 (2023)"},{"key":"1289_CR15","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/j.tcs.2021.03.012","volume":"867","author":"HL Bodlaender","year":"2021","unstructured":"Bodlaender, H.L., Brettell, N., Johnson, M., Paesani, G., Paulusma, D., van Leeuwen, E.J.: Steiner trees for hereditary graph classes: A treewidth perspective. Theoret. Comput. Sci. 867, 30\u201339 (2021)","journal-title":"Theoret. Comput. Sci."},{"issue":"44","key":"1289_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2973749","volume":"63","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) Kernelization. J. ACM 63(44), 1\u201344 (2016)","journal-title":"J. ACM"},{"key":"1289_CR17","doi-asserted-by":"crossref","first-page":"3566","DOI":"10.1007\/s00453-020-00737-z","volume":"82","author":"HL Bodlaender","year":"2020","unstructured":"Bodlaender, H.L., Hanaka, T., Kobayashi, Y., Kobayashi, Y., Okamoto, Y., Otachi, Y., van der Zanden, T.C.: Subgraph isomorphism on graph classes that exclude a substructure. Algorithmica 82, 3566\u20133587 (2020)","journal-title":"Algorithmica"},{"key":"1289_CR18","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Johnson, M., Martin, B., Oostveen, J.J., Pandey, S., Paulusma, D., Smith, S., van Leeuwen, E.J.: Complexity framework for forbidden subgraphs IV: The Steiner Forest problem. Proc. IWOCA 2024, LNCS 14764, 206\u2013217 (2024)","DOI":"10.1007\/978-3-031-63021-7_16"},{"key":"1289_CR19","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21, 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"key":"1289_CR20","unstructured":"Bok, J., Jedlickov\u00e1 N., Martin B., Ochem, P., Paulusma D., Smith S.: Acyclic, Star and Injective Colouring: A complexity picture for $$H$$-free graphs, CoRR abs\/2008.09415 (full version of Proc. ESA 2020, LIPIcs 173, 22:1\u201322:22 (2020))"},{"key":"1289_CR21","doi-asserted-by":"crossref","unstructured":"Boliac, R., Lozin, V.V.: On the clique-width of graphs in hereditary classes. Proc. ISAAC 2022, LNCS 2518, 44\u201354 (2002)","DOI":"10.1007\/3-540-36136-7_5"},{"key":"1289_CR22","doi-asserted-by":"crossref","unstructured":"Bonnet, \u00c9., Chakraborty, D., Duron, J.: Cutting Barnette graphs perfectly is hard. Proc. WG 2023, LNCS 14093, 116\u2013129 (2023)","DOI":"10.1007\/978-3-031-43380-1_9"},{"key":"1289_CR23","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1002\/jgt.20390","volume":"62","author":"PS Bonsma","year":"2009","unstructured":"Bonsma, P.S.: The complexity of the matching-cut problem for planar graphs and other graph classes. J. Graph Theory 62, 109\u2013126 (2009)","journal-title":"J. Graph Theory"},{"key":"1289_CR24","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"RL Brook","year":"1941","unstructured":"Brook, R.L.: On colouring the nodes of a network. Math. Proc. Cambridge Philos. Soc. 37, 194\u2013197 (1941)","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"key":"1289_CR25","first-page":"319","volume":"2017","author":"AA Bulatov","year":"2017","unstructured":"Bulatov, A.A.: A dichotomy theorem for nonuniform CSPs. Proc. FOCS 2017, 319\u2013330 (2017)","journal-title":"Proc. FOCS"},{"key":"1289_CR26","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.tcs.2017.09.033","volume":"705","author":"N Chiarelli","year":"2018","unstructured":"Chiarelli, N., Hartinger, T.R., Johnson, M., Milanic, M., Paulusma, D.: Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity. Theoret. Comput. Sci. 705, 75\u201383 (2018)","journal-title":"Theoret. Comput. Sci."},{"key":"1289_CR27","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1137\/050629276","volume":"21","author":"M Chleb\u00edk","year":"2007","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: The complexity of combinatorial optimization problems on $$d$$-dimensional boxes. SIAM J. Discret. Math. 21, 158\u2013169 (2007)","journal-title":"SIAM J. Discret. Math."},{"key":"1289_CR28","doi-asserted-by":"crossref","unstructured":"Chudnovsky, M., Huang, S., Rza\u0327\u017cewski, P.R., Spirkl, S., Zhong M.: Complexity of $${C}_k$$-coloring in hereditary classes of graphs. Inf. Comput.292, 105015 (2023)","DOI":"10.1016\/j.ic.2023.105015"},{"key":"1289_CR29","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1002\/jgt.3190080106","volume":"8","author":"V Chv\u00e1tal","year":"1984","unstructured":"Chv\u00e1tal, V.: Recognizing decomposable graphs. J. Graph Theory 8, 51\u201353 (1984)","journal-title":"J. Graph Theory"},{"key":"1289_CR30","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"BN Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discret. Math. 86, 165\u2013177 (1990)","journal-title":"Discret. Math."},{"key":"1289_CR31","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85, 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"1289_CR32","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1093\/comjnl\/bxv096","volume":"59","author":"KK Dabrowski","year":"2016","unstructured":"Dabrowski, K.K., Paulusma, D.: Clique-width of graph classes defined by two forbidden induced subgraphs. Comput. J. 59, 650\u2013666 (2016)","journal-title":"Comput. J."},{"key":"1289_CR33","doi-asserted-by":"crossref","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. 23, 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"1289_CR34","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0012-365X(80)90236-8","volume":"30","author":"DP Dailey","year":"1980","unstructured":"Dailey, D.P.: Uniqueness of colorability and colorability of planar $$4$$-regular graphs are NP-complete. Discret. Math. 30, 289\u2013293 (1980)","journal-title":"Discret. Math."},{"key":"1289_CR35","doi-asserted-by":"crossref","first-page":"979","DOI":"10.1142\/S0129054118500168","volume":"29","author":"A Darmann","year":"2018","unstructured":"Darmann, A., D\u00f6cker, J., Dorn, B.: The Monotone Satisfiability problem with bounded variable appearances. Int. J. Found. Comput. Sci. 29, 979\u2013993 (2018)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"1289_CR36","first-page":"411","volume":"2006","author":"A Dawar","year":"2006","unstructured":"Dawar, A., Grohe, M., Kreutzer, S., Schweikardt, N.: Approximation schemes for first-order definable optimisation problems. Proc. LICS 2006, 411\u2013420 (2006)","journal-title":"Proc. LICS"},{"key":"1289_CR37","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/0004-3702(89)90037-4","volume":"38","author":"R Dechter","year":"1989","unstructured":"Dechter, R., Pearl, J.: Tree clustering for constraint networks. Artif. Intell. 38, 353\u2013366 (1989)","journal-title":"Artif. Intell."},{"key":"1289_CR38","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Subexponential parameterized algorithms on bounded-genus graphs and $${H}$$-minor-free graphs. J. ACM 52, 866\u2013893 (2005)","journal-title":"J. ACM"},{"key":"1289_CR39","doi-asserted-by":"crossref","unstructured":"Deng, X., Lin, B., Zhang, C.: Multi-multiway cut problem on graphs of bounded branch width. Proc. FAW-AAIM 2013, LNCS 7924, 315\u2013324 (2013)","DOI":"10.1007\/978-3-642-38756-2_32"},{"key":"1289_CR40","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 3rd edition. Springer (2005)","DOI":"10.1007\/978-3-642-14279-6_7"},{"key":"1289_CR41","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1006\/inco.1994.1064","volume":"113","author":"JA Ellis","year":"1994","unstructured":"Ellis, J.A., Sudborough, I.H., Turner, J.S.: The vertex separation and search number of a graph. Inf. Comput. 113, 50\u201379 (1994)","journal-title":"Inf. Comput."},{"key":"1289_CR42","unstructured":"Evald, J., Dahlgaard, S.: Tight hardness results for distance and centrality problems in constant degree graphs. CoRR abs\/1609.08403 (2016)"},{"key":"1289_CR43","unstructured":"Feghali, C., Lucke, F., Paulusma, D., Ries, B.: Matching cuts in graphs of high girth and $$H$$-free graphs, Proc. ISAAC 2023, LIPIcs 283, 31:1\u201331:16 (2023)"},{"key":"1289_CR44","doi-asserted-by":"crossref","first-page":"1175","DOI":"10.1016\/j.dam.2007.08.013","volume":"156","author":"S Fiorini","year":"2008","unstructured":"Fiorini, S., Hardy, N., Reed, B.A., Vetta, A.: Planar graph bipartization in linear time. Discret. Appl. Math. 156, 1175\u20131180 (2008)","journal-title":"Discret. Appl. Math."},{"issue":"10","key":"1289_CR45","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3154833","volume":"65","author":"FV Fomin","year":"2018","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S.: Excluded grid minors and efficient polynomial-time approximation schemes. J. ACM 65(10), 1\u201310 (2018)","journal-title":"J. ACM"},{"key":"1289_CR46","doi-asserted-by":"crossref","DOI":"10.1016\/j.ipl.2021.106121","volume":"170","author":"F Foucaud","year":"2021","unstructured":"Foucaud, F., Hocquard, H., Lajou, D.: Complexity and algorithms for injective edge-coloring in graphs. Inf. Process. Lett. 170, 106121 (2021)","journal-title":"Inf. Process. Lett."},{"key":"1289_CR47","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/S0012-365X(00)00009-1","volume":"222","author":"A Galluccio","year":"2000","unstructured":"Galluccio, A., Hell, P., Ne\u0161et\u0159il, J.: The complexity of $${H}$$-colouring of bounded degree graphs. Discret. Math. 222, 101\u2013109 (2000)","journal-title":"Discret. Math."},{"key":"1289_CR48","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The Rectilinear Steiner Tree problem is NP complete. J. SIAM Appl. Math. 32, 826\u2013834 (1977)","journal-title":"J. SIAM Appl. Math."},{"key":"1289_CR49","first-page":"47","volume":"1974","author":"MR Garey","year":"1974","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete problems. Proc. STOC 1974, 47\u201363 (1974)","journal-title":"Some simplified NP-complete problems. Proc. STOC"},{"key":"1289_CR50","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Tarjan, R.E.: The Planar Hamiltonian Circuit problem is NP-complete. SIAM J. Comput. 5, 704\u2013714 (1976)","journal-title":"SIAM J. Comput."},{"key":"1289_CR51","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA (1979)"},{"key":"1289_CR52","doi-asserted-by":"crossref","unstructured":"Gartland, P., Lokshtanov, D., Masa\u0159\u00edk, T., Pilipczuk, M., Pilipczuk, M., Rza\u0327\u017cewski P.: Maximum Weight Independent Set in graphs with no long claws in quasi-polynomial time. Proc. STOC 2024, 683\u2013691 (2023)","DOI":"10.1145\/3618260.3649791"},{"key":"1289_CR53","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1137\/18M1193402","volume":"50","author":"P Gawrychowski","year":"2021","unstructured":"Gawrychowski, P., Kaplan, H., Mozes, S., Sharir, M., Weimann, O.: Voronoi diagrams on planar graphs, and computing the diameter in deterministic $${\\tilde{O}}(n^{5\/3})$$ time. SIAM J. Comput. 50, 509\u2013554 (2021)","journal-title":"SIAM J. Comput."},{"key":"1289_CR54","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1145\/1412700.1412710","volume":"39","author":"O Goldreich","year":"2008","unstructured":"Goldreich, O.: Computational complexity: A conceptual perspective. SIGACT News 39, 35\u201339 (2008)","journal-title":"SIGACT News"},{"key":"1289_CR55","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/j.dam.2013.10.010","volume":"166","author":"PA Golovach","year":"2014","unstructured":"Golovach, P.A., Paulusma, D.: List coloring in the absence of two subgraphs. Discret. Appl. Math. 166, 123\u2013130 (2014)","journal-title":"Discret. Appl. Math."},{"key":"1289_CR56","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/j.dam.2014.08.008","volume":"180","author":"PA Golovach","year":"2015","unstructured":"Golovach, P.A., Paulusma, D., Ries, B.: Coloring graphs characterized by a forbidden subgraph. Discret. Appl. Math. 180, 101\u2013110 (2015)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"1289_CR57","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1206035.1206036","volume":"54","author":"M Grohe","year":"2007","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54(1), 1\u20131 (2007)","journal-title":"J. ACM"},{"key":"1289_CR58","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1137\/120892234","volume":"44","author":"M Grohe","year":"2015","unstructured":"Grohe, M., Marx, D.: Structure theorem and isomorphism test for graphs with excluded topological subgraphs. SIAM J. Comput. 44, 114\u2013159 (2015)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1289_CR59","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3414473","volume":"18","author":"A Grzesik","year":"2022","unstructured":"Grzesik, A., Klimosov\u00e1, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for Maximum Weight Independent set on $${P}_6$$-free graphs. ACM Trans. Algorithms 18(4), 1\u20134 (2022)","journal-title":"ACM Trans. Algorithms"},{"key":"1289_CR60","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F Hadlock","year":"1975","unstructured":"Hadlock, F.: Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput. 4, 221\u2013225 (1975)","journal-title":"SIAM J. Comput."},{"key":"1289_CR61","unstructured":"Harary, F.: Graph theory. Addison-Wesley (1991)"},{"key":"1289_CR62","doi-asserted-by":"crossref","first-page":"237","DOI":"10.37236\/11364","volume":"30","author":"R Hickingbotham","year":"2023","unstructured":"Hickingbotham, R.: Induced subgraphs and path decompositions. Electron. J. Combin. 30, 237 (2023)","journal-title":"Electron. J. Combin."},{"key":"1289_CR63","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.dam.2019.06.026","volume":"278","author":"L Jaffke","year":"2020","unstructured":"Jaffke, L., Kwon, O., Telle, J.A.: Mim-width I. induced path problems. Discrete Appl. Math. 278, 153\u2013168 (2020)","journal-title":"Discrete Appl. Math."},{"key":"1289_CR64","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0166-218X(96)00085-6","volume":"75","author":"K Jansen","year":"1997","unstructured":"Jansen, K., Scheffler, P.: Generalized coloring for tree-like graphs. Discret. Appl. Math. 75, 135\u2013155 (1997)","journal-title":"Discret. Appl. Math."},{"key":"1289_CR65","unstructured":"Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., van Leeuwen, E.J.: Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs. Proc. SWAT 2024, LIPIcs 294, 29:1\u201329:17 (2024)"},{"key":"1289_CR66","unstructured":"Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., van Leeuwen, E.J.: Complexity framework for forbidden subgraphs III: When problems are tractable on subcubic graphs. Proc. MFCS 2023, LIPIcs 272, 57:1-57:15 (2023)"},{"key":"1289_CR67","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/j.tcs.2012.02.036","volume":"438","author":"M Kami\u0144ski","year":"2012","unstructured":"Kami\u0144ski, M.: Max-Cut and containment relations in graphs. Theoret. Comput. Sci. 438, 89\u201395 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"1289_CR68","unstructured":"Kern, W., Paulusma, D.: Contracting to a longest path in $${H}$$-free graphs. Proc. ISAAC 2020, LIPIcs 181, 22:1\u201322:18 (2020)"},{"key":"1289_CR69","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/0020-0190(92)90234-M","volume":"42","author":"NG Kinnersley","year":"1992","unstructured":"Kinnersley, N.G.: The vertex separation number of a graph equals its path-width. Inf. Process. Lett. 42, 345\u2013350 (1992)","journal-title":"Inf. Process. Lett."},{"key":"1289_CR70","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1137\/080715482","volume":"23","author":"J Kneis","year":"2009","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: A bound on the pathwidth of sparse graphs with applications to exact algorithms. SIAM J. Discrete Math. 23, 407\u2013427 (2009)","journal-title":"SIAM J. Discrete Math."},{"key":"1289_CR71","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/j.jctb.2023.01.002","volume":"160","author":"T Korhonen","year":"2023","unstructured":"Korhonen, T.: Grid induced minor theorem for graphs of small degree. J. Combin. Theory Ser. B 160, 206\u2013214 (2023)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1289_CR72","doi-asserted-by":"crossref","first-page":"3545","DOI":"10.1016\/j.tcs.2011.03.001","volume":"412","author":"N Korpelainen","year":"2011","unstructured":"Korpelainen, N., Lozin, V.V., Malyshev, D.S., Tiskin, A.: Boundary properties of graphs for algorithmic graph problems. Theoret. Comput. Sci. 412, 3545\u20133554 (2011)","journal-title":"Theoret. Comput. Sci."},{"key":"1289_CR73","first-page":"177","volume":"379","author":"S Kreutzer","year":"2011","unstructured":"Kreutzer, S.: Algorithmic meta-theorems. London Math. Soc. Lecture Note Ser. 379, 177\u2013270 (2011)","journal-title":"London Math. Soc. Lecture Note Ser."},{"key":"1289_CR74","doi-asserted-by":"crossref","unstructured":"Le, V.B., Telle, J.A.: The Perfect Matching Cut problem revisited. Proc. WG 2021, LNCS 12911, 182\u2013194 (2021)","DOI":"10.1007\/978-3-030-86838-3_14"},{"key":"1289_CR75","unstructured":"Lozin, V.V., Martin, B., Pandey, S., Paulusma, D., Siggers, M., Smith, S., van Leeuwen, E.J.: Complexity framework for forbidden subgraphs II: Edge subdivision and the \u201cH\u201d-graphs. Proc. ISAAC 2024, LIPIcs, to appear"},{"key":"1289_CR76","doi-asserted-by":"crossref","DOI":"10.1016\/j.ejc.2022.103517","volume":"103","author":"VV Lozin","year":"2022","unstructured":"Lozin, V.V., Razgon, I.: Tree-width dichotomy. Eur. J. Comb. 103, 103517 (2022)","journal-title":"Eur. J. Comb."},{"key":"1289_CR77","doi-asserted-by":"crossref","first-page":"5729","DOI":"10.1016\/j.disc.2008.05.016","volume":"309","author":"G MacGillivray","year":"2009","unstructured":"MacGillivray, G., Siggers, M.H.: On the complexity of $${H}$$-colouring planar graphs. Discret. Math. 309, 5729\u20135738 (2009)","journal-title":"Discret. Math."},{"key":"1289_CR78","doi-asserted-by":"crossref","DOI":"10.1016\/j.ipl.2021.106213","volume":"174","author":"B Martin","year":"2022","unstructured":"Martin, B., Paulusma, D., Smith, S.: Hard problems that quickly become very easy. Inf. Process. Lett. 174, 106213 (2022)","journal-title":"Inf. Process. Lett."},{"key":"1289_CR79","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF01202792","volume":"13","author":"M Middendorf","year":"1993","unstructured":"Middendorf, M., Pfeiffer, F.: On the complexity of the disjoint Paths problem. Combinatorica 13, 97\u2013107 (1993)","journal-title":"Combinatorica"},{"key":"1289_CR80","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1006\/jctb.2000.2026","volume":"82","author":"B Mohar","year":"2001","unstructured":"Mohar, B.: Face covers and the genus problem for apex graphs. J. Combin. Theory, Ser.B 82, 102\u2013117 (2001)","journal-title":"J. Combin. Theory, Ser.B"},{"key":"1289_CR81","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0304-3975(88)90028-X","volume":"58","author":"B Monien","year":"1988","unstructured":"Monien, B., Sudborough, I.H.: Min Cut is NP-complete for edge weighted treees. Theoret. Comput. Sci. 58, 209\u2013229 (1988)","journal-title":"Theoret. Comput. Sci."},{"key":"1289_CR82","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1016\/j.tcs.2017.06.012","volume":"692","author":"A Munaro","year":"2017","unstructured":"Munaro, A.: Boundary classes for graph problems involving non-local properties. Theoret. Comput. Sci. 692, 46\u201371 (2017)","journal-title":"Theoret. Comput. Sci."},{"key":"1289_CR83","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1016\/j.ejc.2011.01.006","volume":"32","author":"J Ne\u0161et\u0159il","year":"2011","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: On nowhere dense graphs. Eur. J. Comb. 32, 600\u2013617 (2011)","journal-title":"Eur. J. Comb."},{"key":"1289_CR84","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., de\u00a0Mendez, P.O.: Sparsity - Graphs, Structures, and Algorithms, Algorithms and combinatorics, vol.\u00a028. Springer (2012)","DOI":"10.1007\/978-3-642-27875-4"},{"key":"1289_CR85","first-page":"307","volume":"15","author":"S Poljak","year":"1974","unstructured":"Poljak, S.: A note on stable sets and colorings of graphs. Comment. Math. Univ. Carol. 15, 307\u2013309 (1974)","journal-title":"Comment. Math. Univ. Carol."},{"key":"1289_CR86","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width. J. Combin. Theory Ser. B 36, 49\u201364 (1984)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1289_CR87","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. V. Excluding a planar graph. J. Combin. Theory Ser. B 41, 92\u2013114 (1986)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1289_CR88","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Combin. Theory Ser. B 92, 325\u2013357 (2004)","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"1289_CR89","unstructured":"Scheffler, P.: A practical linear time algorithm for disjoint paths in graphs with bounded tree-width. Preprint\u00a0396, Technische Universit\u00e4t Berlin, Institut f\u00fcr Mathematik (1994)"},{"key":"1289_CR90","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1017\/S0960129500070079","volume":"6","author":"D Seese","year":"1996","unstructured":"Seese, D.: Linear time computable problems and first-order descriptions. Math. Struct. Comput. Sci. 6, 505\u2013526 (1996)","journal-title":"Math. Struct. Comput. Sci."},{"key":"1289_CR91","unstructured":"Siebertz, S.: Nowhere dense graph classes and algorithmic applications. A tutorial at Highlights of Logic, Games and Automata 2019. CoRR 1909.06752 (2019)"},{"key":"1289_CR92","unstructured":"Speckenmeyer, E.: Untersuchungen zum Feedback Vertex Set Problem in ungerichteten Graphen. Ph.D. thesis, Paderborn (1983)"},{"key":"1289_CR93","doi-asserted-by":"crossref","first-page":"1179","DOI":"10.1587\/transfun.E98.A.1179","volume":"98","author":"Y Tamura","year":"2015","unstructured":"Tamura, Y., Ito, T., Zhou, X.: Algorithms for the independent feedback vertex set problem. IEICE Trans Fundamentals Electron. Commun. Comput. Sci. 98, 1179\u20131188 (2015)","journal-title":"IEICE Trans Fundamentals Electron. Commun. Comput. Sci."},{"key":"1289_CR94","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"JA Telle","year":"1997","unstructured":"Telle, J.A., Proskurowski, A.: Algorithms for vertex partitioning problems on partial $$k$$-trees. SIAM J. Discret. Math. 10, 529\u2013550 (1997)","journal-title":"SIAM J. Discret. Math."},{"key":"1289_CR95","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.tcs.2018.10.030","volume":"770","author":"JA Telle","year":"2019","unstructured":"Telle, J.A., Villanger, Y.: FPT algorithms for domination in sparse graphs and beyond. Theoret. Comput. Sci. 770, 62\u201368 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"1289_CR96","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0012-365X(88)90226-9","volume":"72","author":"S Ueno","year":"1988","unstructured":"Ueno, S., Kajitani, Y., Gotoh, S.: On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discret. Math. 72, 355\u2013360 (1988)","journal-title":"Discret. Math."},{"key":"1289_CR97","unstructured":"Vatshelle, M.: New Width Parameters of Graphs. Ph.D. thesis, University of Bergen (2012)"},{"key":"1289_CR98","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1016\/j.jctb.2019.04.004","volume":"139","author":"D Wei\u00dfauer","year":"2019","unstructured":"Wei\u00dfauer, D.: In absence of long chordless cycles, large tree-width becomes a local phenomenon. J. Combin. Theory, Ser. B 139, 342\u2013352 (2019)","journal-title":"J. Combin. Theory, Ser. B"},{"key":"1289_CR99","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal $$2$$-constraint satisfaction and its implications. Theoret. Comput. Sci. 348, 357\u2013365 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"1289_CR100","first-page":"3447","volume":"2018","author":"VV Williams","year":"2018","unstructured":"Williams, V.V.: On some fine-grained questions in algorithms and complexity. Proc. ICM 2018, 3447\u20133487 (2018)","journal-title":"Proc. ICM"},{"key":"1289_CR101","unstructured":"Wolle, T.: Computational Aspects of Treewidth: Lower Bounds and Network Reliability, Ph.D. thesis, Utrecht University (2005)"},{"key":"1289_CR102","doi-asserted-by":"crossref","first-page":"694","DOI":"10.1007\/s10878-021-00708-2","volume":"41","author":"W Xi","year":"2021","unstructured":"Xi, W., Lin, W.: On maximum $${P}_3$$-packing in claw-free subcubic graphs. J. Comb. Optim. 41, 694\u2013709 (2021)","journal-title":"J. Comb. Optim."},{"key":"1289_CR103","first-page":"253","volume":"1978","author":"M Yannakakis","year":"1978","unstructured":"Yannakakis, M.: Node and edge deletion NP-complete problems. Proc. STOC 1978, 253\u2013264 (1978)","journal-title":"Proc. STOC"},{"key":"1289_CR104","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M Yannakakis","year":"1980","unstructured":"Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38, 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."},{"key":"1289_CR105","doi-asserted-by":"crossref","unstructured":"Zhuk, D.: A proof of the CSP dichotomy conjecture. Journal of the ACM 67, 30:1\u201330:78 (2020)","DOI":"10.1145\/3402029"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01289-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01289-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01289-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T08:49:48Z","timestamp":1740041388000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01289-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,5]]},"references-count":105,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["1289"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01289-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,5]]},"assertion":[{"value":"28 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Decalarations"}},{"value":"The authors have no Conflict of interest as defined by Springer, or other interests that might be perceived to influence the results and\/or discussion reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest."}}]}}