{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T20:20:17Z","timestamp":1773433217414,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:00:00Z","timestamp":1730678400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:00:00Z","timestamp":1730678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Norwegian School Of Economics"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing <jats:italic>W<\/jats:italic>[1]-hardness proofs for these problems, since XNLP-hardness implies <jats:italic>W<\/jats:italic>[<jats:italic>t<\/jats:italic>]-hardness for all <jats:italic>t<\/jats:italic>. It also indicates, via a conjecture by Pilipczuk and Wrochna (ACM Trans Comput Theory 9:1\u201336, 2018), that any XP algorithm for such problems is likely to require XP space. In particular, we show XNLP-completeness for natural problems parameterized by pathwidth, linear clique-width, and linear mim-width. The problems we consider are <jats:sc>Independent Set<\/jats:sc>, <jats:sc>Dominating Set<\/jats:sc>, <jats:sc>Odd Cycle Transversal<\/jats:sc>, <jats:sc>(<\/jats:sc>\n            <jats:italic>q<\/jats:italic>\n            <jats:sc>-)Coloring<\/jats:sc>, <jats:sc>Max Cut<\/jats:sc>, <jats:sc>Maximum Regular Induced Subgraph<\/jats:sc>, <jats:sc>Feedback Vertex Set<\/jats:sc>, <jats:sc>Capacitated (Red-Blue) Dominating Set<\/jats:sc>, <jats:sc>Capacitated Vertex Cover<\/jats:sc> and <jats:sc>Bipartite Bandwidth<\/jats:sc>.<\/jats:p>","DOI":"10.1007\/s00453-024-01274-9","type":"journal-article","created":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T15:03:06Z","timestamp":1730732586000},"page":"465-506","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure"],"prefix":"10.1007","volume":"87","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carla","family":"Groenland","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hugo","family":"Jacob","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lars","family":"Jaffke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paloma T.","family":"Lima","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,11,4]]},"reference":[{"key":"1274_CR1","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Cornelissen, G., Wegen, M.: Problems hard for treewidth but easy for stable gonality. In: Bekos, M.A., Kaufmann, M. (eds.) Proceedings 48th international workshop on graph-theoretic concepts in computer science (WG 2022). Lecture notes in computer science, vol. 13453, pp. 84\u201397 (2022). https:\/\/doi.org\/10.1007\/978-3-031-15914-5_7","DOI":"10.1007\/978-3-031-15914-5_7"},{"key":"1274_CR2","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Groenland, C., Jacob, H., Pilipczuk, M., Pilipczuk, M.: On the complexity of problems on tree-structured graphs. In: Dell, H., Nederlof, J. (eds.) 17th international symposium on parameterized and exact computation (IPEC 2022). Leibniz international proceedings in informatics (LIPIcs), vol. 249, pp. 6\u20131617. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2022). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2022.6 . https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2022\/17362","DOI":"10.4230\/LIPIcs.IPEC.2022.6"},{"key":"1274_CR3","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Groenland, C., Jacob, H., Jaffke, L., Lima, P.T.: XNLP-Completeness for parameterized problems on graphs with a linear structure. In: Dell, H., Nederlof, J. (eds.) 17th international symposium on parameterized and exact computation (IPEC 2022). Leibniz international proceedings in informatics (LIPIcs), vol. 249, pp. 8:1\u20138:18. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2022). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2022.8","DOI":"10.4230\/LIPIcs.IPEC.2022.8"},{"key":"1274_CR4","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Groenland, C., Nederlof, J., Swennenhuis, C.M.F.: Parameterized problems complete for nondeterministic FPT time and logarithmic space. In: Proceedings 62nd IEEE annual symposium on foundations of computer science, FOCS 2021, pp. 193\u2013204 (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00027","DOI":"10.1109\/FOCS52979.2021.00027"},{"key":"1274_CR5","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Lokshtanov, D., Penninkx, E.: Planar capacitated dominating set is W[1]-hard. In: Chen, J., Fomin, F.V. (eds.) Proceedings 4th international workshop on parameterized and exact computation, IWPEC 2009. Lecture notes in computer science, vol. 5917, pp. 50\u201360. Springer (2009). https:\/\/doi.org\/10.1007\/978-3-642-11269-0_4","DOI":"10.1007\/978-3-642-11269-0_4"},{"key":"1274_CR6","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L.: Parameterized complexity of bandwidth of caterpillars and weighted path emulation. In: Kowalik, L., Pilipczuk, M., Rzazewski, P. (eds.) Proceedings of the 47th international workshop on graph-theoretic concepts in computer science (WG 2021). Lecture notes in computer science, vol. 12911, pp. 15\u201327. Springer (2021). https:\/\/doi.org\/10.1007\/978-3-030-86838-3_2","DOI":"10.1007\/978-3-030-86838-3_2"},{"key":"1274_CR7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2021.106168","volume":"173","author":"N Brettell","year":"2022","unstructured":"Brettell, N., Horsfield, J., Munaro, A., Paulusma, D.: List $$k$$-colouring $${P}_t$$-free graphs: a mim-width perspective. Inf. Process. Lett. 173, 106168 (2022). https:\/\/doi.org\/10.1016\/j.ipl.2021.106168","journal-title":"Inf. Process. Lett."},{"key":"1274_CR8","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.tcs.2013.03.008","volume":"485","author":"H Broersma","year":"2013","unstructured":"Broersma, H., Golovach, P.A., Patel, V.: Tight complexity bounds for FPT subgraph problems parameterized by the clique-width. Theor. Comput. Sci. 485, 69\u201384 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2013.03.008","journal-title":"Theor. Comput. Sci."},{"key":"1274_CR9","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2013.01.009","volume":"511","author":"B Bui-Xuan","year":"2013","unstructured":"Bui-Xuan, B., Telle, J.A., Vatshelle, M.: Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor. Comput. Sci. 511, 66\u201376 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2013.01.009","journal-title":"Theor. Comput. Sci."},{"key":"1274_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"1274_CR11","doi-asserted-by":"publisher","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated domination and covering: a parameterized perspective. In: Grohe, M., Niedermeier, R. (eds.) Proceedings 3rd international workshop on parameterized and exact computation, IWPEC 2008. Lecture notes in computer science, vol. 5018, pp. 78\u201390. Springer (2008). https:\/\/doi.org\/10.1007\/978-3-540-79723-4_9","DOI":"10.1007\/978-3-540-79723-4_9"},{"key":"1274_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer, New York (1999)"},{"issue":"3","key":"1274_CR13","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/s00453-014-9944-y","volume":"71","author":"M Elberfeld","year":"2015","unstructured":"Elberfeld, M., Stockhusen, C., Tantau, T.: On the space and circuit complexity of parameterized problems: classes and completeness. Algorithmica 71(3), 661\u2013701 (2015). https:\/\/doi.org\/10.1007\/s00453-014-9944-y","journal-title":"Algorithmica"},{"issue":"5","key":"1274_CR14","doi-asserted-by":"publisher","first-page":"1941","DOI":"10.1137\/080742270","volume":"39","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Intractability of clique-width parameterizations. SIAM J. Comput. 39(5), 1941\u20131956 (2010). https:\/\/doi.org\/10.1137\/080742270","journal-title":"SIAM J. Comput."},{"issue":"5","key":"1274_CR15","doi-asserted-by":"publisher","first-page":"1541","DOI":"10.1137\/130910932","volume":"43","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Almost optimal lower bounds for problems parameterized by clique-width. SIAM J. Comput. 43(5), 1541\u20131563 (2014). https:\/\/doi.org\/10.1137\/130910932","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1274_CR16","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/3280824","volume":"15","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S., Zehavi, M.: Clique-width III: Hamiltonian cycle and the odd case of graph coloring. ACM Trans. Algorithms 15(1), 9\u20131927 (2019). https:\/\/doi.org\/10.1145\/3280824","journal-title":"ACM Trans. Algorithms"},{"issue":"9","key":"1274_CR17","doi-asserted-by":"publisher","first-page":"2432","DOI":"10.1007\/s00453-020-00692-9","volume":"82","author":"FV Fomin","year":"2020","unstructured":"Fomin, F.V., Golovach, P.A., Raymond, J.: On the tractability of optimization problems on H-graphs. Algorithmica 82(9), 2432\u20132473 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00692-9","journal-title":"Algorithmica"},{"issue":"1","key":"1274_CR18","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.disopt.2010.08.003","volume":"8","author":"S Guillemot","year":"2011","unstructured":"Guillemot, S.: Parameterized complexity and approximability of the longest compatible sequence problem. Discret. Optim. 8(1), 50\u201360 (2011). https:\/\/doi.org\/10.1016\/j.disopt.2010.08.003","journal-title":"Discret. Optim."},{"issue":"22","key":"1274_CR19","doi-asserted-by":"publisher","first-page":"2734","DOI":"10.1016\/j.disc.2007.01.020","volume":"307","author":"F Gurski","year":"2007","unstructured":"Gurski, F., Wanke, E.: Line graphs of bounded clique-width. Discret. Math. 307(22), 2734\u20132754 (2007). https:\/\/doi.org\/10.1016\/j.disc.2007.01.020","journal-title":"Discret. Math."},{"key":"1274_CR20","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/s00453-019-00607-3","volume":"82","author":"L Jaffke","year":"2020","unstructured":"Jaffke, L., Kwon, O.-J., Telle, J.A.: Mim-width. II The feedback vertex set problem. Algorithmica 82, 118\u2013145 (2020)","journal-title":"Algorithmica"},{"key":"1274_CR21","unstructured":"Johansson, O.: Graph decompositions using node labels. PhD thesis, KTH Stockholm, Sweden (2001)"},{"issue":"2\u20133","key":"1274_CR22","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(02)00198-1","volume":"126","author":"D Kobler","year":"2003","unstructured":"Kobler, D., Rotics, U.: Edge dominating set and colorings on graphs with fixed clique-width. Discret. Appl. Math. 126(2\u20133), 197\u2013221 (2003). https:\/\/doi.org\/10.1016\/S0166-218X(02)00198-1","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"1274_CR23","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/3170442","volume":"14","author":"D Lokshtanov","year":"2018","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms 14(2), 13\u201311330 (2018). https:\/\/doi.org\/10.1145\/3170442","journal-title":"ACM Trans. Algorithms"},{"key":"1274_CR24","unstructured":"Mathieson, L., Szeider, S.: The parameterized complexity of regular subgraph problems and generalizations. In: Harland, J., Manyem, P. (eds.) Proceedings 14th computing: the Australasian theory symposium, CATS 2008. CRPIT, vol. 77, pp. 79\u201386. Australian Computer Society (2008). http:\/\/crpit.scem.westernsydney.edu.au\/abstracts\/CRPITV77Mathieson.html"},{"issue":"2","key":"1274_CR25","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.jda.2008.09.005","volume":"7","author":"H Moser","year":"2009","unstructured":"Moser, H., Thilikos, D.M.: Parameterized complexity of finding regular induced subgraphs. J. Discret. Algorithms 7(2), 181\u2013190 (2009). https:\/\/doi.org\/10.1016\/j.jda.2008.09.005","journal-title":"J. Discret. Algorithms"},{"issue":"4","key":"1274_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3154856","volume":"9","author":"M Pilipczuk","year":"2018","unstructured":"Pilipczuk, M., Wrochna, M.: On space efficiency of algorithms working on structural decompositions of graphs. ACM Trans. Comput. Theory 9(4), 1\u201336 (2018). https:\/\/doi.org\/10.1145\/3154856","journal-title":"ACM Trans. Comput. Theory"},{"key":"1274_CR27","unstructured":"Vatshelle, M.: New width parameters of graphs. PhD thesis, University of Bergen, Norway (2012)"},{"issue":"2\u20133","key":"1274_CR28","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0166-218X(94)90026-4","volume":"54","author":"E Wanke","year":"1994","unstructured":"Wanke, E.: $$k$$-NLC graphs and polynomial algorithms. Discret. Appl. Math. 54(2\u20133), 251\u2013266 (1994). https:\/\/doi.org\/10.1016\/0166-218X(94)90026-4","journal-title":"Discret. Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01274-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01274-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01274-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,23]],"date-time":"2025-03-23T05:25:50Z","timestamp":1742707550000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01274-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,4]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["1274"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01274-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,4]]},"assertion":[{"value":"22 December 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}