{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T19:11:35Z","timestamp":1792782695673,"version":"4.5.0"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T00:00:00Z","timestamp":1787529600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T00:00:00Z","timestamp":1787529600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Humboldt-Universit\u00e4t zu Berlin","id":[{"id":"https:\/\/ror.org\/01hcx6992","id-type":"ROR","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,10]]},"abstract":"Abstract<\/jats:title>\n \n We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two important graph-parameters, cutwidth and pathwidth. These connections allow us to show that computing the locality number is\n \n \n $$\\textsf {NP}$$<\/jats:tex-math>\n \n NP<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -hard, but fixed-parameter tractable, if parameterised by the locality number or by the alphabet size, which has been formulated as open problems in the literature. Moreover, the locality number can be approximated with ratio\n \n \n $${{\\,\\textrm{O}\\,}}(\\sqrt{\\log ({{\\,\\mathrm{\\textsf {opt}}\\,}})} \\log (n))$$<\/jats:tex-math>\n \n \n \n \n O<\/mml:mtext>\n \n <\/mml:mrow>\n (<\/mml:mo>\n \n \n log<\/mml:mo>\n (<\/mml:mo>\n \n \n opt<\/mml:mi>\n \n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msqrt>\n log<\/mml:mo>\n \n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . An important aspect of our work \u2013 that is relevant in its own right and of independent interest \u2013 is that we identify connections between the string parameter of the locality number on the one hand, and the famous graph parameters of cutwidth and pathwidth, on the other hand. These two parameters have been jointly investigated in the literature and are arguably among the most central graph parameters that are based on \u201clinearisations\u201d of graphs. In this way, we also identify a direct approximation preserving reduction from cutwidth to pathwidth, which shows that any polynomial\n \n \n $$f({{\\,\\mathrm{\\textsf {opt}}\\,}},|V|)$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n (<\/mml:mo>\n \n \n opt<\/mml:mi>\n \n <\/mml:mrow>\n ,<\/mml:mo>\n |<\/mml:mo>\n V<\/mml:mi>\n |<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -approximation algorithm for pathwidth yields a polynomial\n \n \n $$2f(2{{\\,\\mathrm{\\textsf {opt}}\\,}},h)$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n f<\/mml:mi>\n (<\/mml:mo>\n 2<\/mml:mn>\n \n \n opt<\/mml:mi>\n \n <\/mml:mrow>\n ,<\/mml:mo>\n h<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -approximation algorithm for cutwidth on multigraphs (where\n h<\/jats:italic>\n is the number of edges). In particular, this translates known approximation ratios for pathwidth into new approximation ratios for cutwidth, namely\n \n \n $${{\\,\\textrm{O}\\,}}(\\sqrt{\\log ({{\\,\\mathrm{\\textsf {opt}}\\,}})} \\log (h))$$<\/jats:tex-math>\n \n \n \n \n O<\/mml:mtext>\n \n <\/mml:mrow>\n (<\/mml:mo>\n \n \n log<\/mml:mo>\n (<\/mml:mo>\n \n \n opt<\/mml:mi>\n \n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msqrt>\n log<\/mml:mo>\n \n (<\/mml:mo>\n h<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and\n \n \n $${{\\,\\textrm{O}\\,}}(\\sqrt{\\log ({{\\,\\mathrm{\\textsf {opt}}\\,}})} {{\\,\\mathrm{\\textsf {opt}}\\,}})$$<\/jats:tex-math>\n \n \n \n \n O<\/mml:mtext>\n \n <\/mml:mrow>\n (<\/mml:mo>\n \n \n log<\/mml:mo>\n (<\/mml:mo>\n \n \n opt<\/mml:mi>\n \n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msqrt>\n \n \n opt<\/mml:mi>\n \n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for (multi) graphs with\n h<\/jats:italic>\n edges.\n <\/jats:p>","DOI":"10.1007\/s00453-026-01404-5","type":"journal-article","created":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T15:58:57Z","timestamp":1787587137000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality\u00a0Number"],"prefix":"10.1007","volume":"88","author":[{"given":"Katrin","family":"Casel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joel D.","family":"Day","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pamela","family":"Fleischmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tomasz","family":"Kociumaka","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6094-3324","authenticated-orcid":false,"given":"Florin","family":"Manea","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5137-1504","authenticated-orcid":false,"given":"Markus L.","family":"Schmid","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,8,24]]},"reference":[{"issue":"1\u20132","key":"1404_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial $$k$$-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209(1\u20132), 1\u201345 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(97)00228-4","journal-title":"Theoret. Comput. Sci."},{"key":"1404_CR2","doi-asserted-by":"publisher","unstructured":"Kloks, T. (ed.): Treewidth, Computations and Approximations. LNCS, vol. 842. Springer, (1994). https:\/\/doi.org\/10.1007\/BFb0045375","DOI":"10.1007\/BFb0045375"},{"issue":"1\u20132","key":"1404_CR3","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernet. 11(1\u20132), 1\u201321 (1993)","journal-title":"Acta Cybernet."},{"issue":"3","key":"1404_CR4","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1145\/568522.568523","volume":"34","author":"J D\u00edaz","year":"2002","unstructured":"D\u00edaz, J., Petit, J., Serna, M.: A survey of graph layout problems. ACM Comput. Surv. 34(3), 313\u2013356 (2002). https:\/\/doi.org\/10.1145\/568522.568523","journal-title":"ACM Comput. Surv."},{"key":"1404_CR5","first-page":"177","volume":"105","author":"J Petit","year":"2011","unstructured":"Petit, J.: Addenda to the survey of layout problems. Bull. EATCS 105, 177\u2013201 (2011)","journal-title":"Bull. EATCS"},{"key":"1404_CR6","doi-asserted-by":"publisher","unstructured":"Day, J.D., Fleischmann, P., Manea, F., Nowotka, D.: Local patterns. In: Lokam, S.V., Ramanujam, R. (eds.) Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017. LIPIcs, vol. 93, pp. 24\u201312414. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, (2017). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2017.24","DOI":"10.4230\/LIPIcs.FSTTCS.2017.24"},{"issue":"3","key":"1404_CR7","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1145\/337244.337255","volume":"47","author":"J Karhum\u00e4ki","year":"2000","unstructured":"Karhum\u00e4ki, J., Mignosi, F., Plandowski, W.: The expressibility of languages and relations by word equations. J. ACM 47(3), 483\u2013505 (2000). https:\/\/doi.org\/10.1145\/337244.337255","journal-title":"J. ACM"},{"key":"1404_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/cbo9781107326019","volume-title":"Algebraic Combinatorics on Words","year":"2002","unstructured":"Lothaire, M. (ed.): Algebraic Combinatorics on Words. Cambridge University Press, UK (2002). https:\/\/doi.org\/10.1017\/cbo9781107326019"},{"issue":"3","key":"1404_CR9","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jda.2006.10.001","volume":"5","author":"A Amir","year":"2007","unstructured":"Amir, A., Nor, I.: Generalized function matching. J. Discrete Alg. 5(3), 514\u2013523 (2007). https:\/\/doi.org\/10.1016\/j.jda.2006.10.001","journal-title":"J. Discrete Alg."},{"issue":"1","key":"1404_CR10","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/0022-0000(80)90041-0","volume":"21","author":"D Angluin","year":"1980","unstructured":"Angluin, D.: Finding patterns common to a set of strings. J. Comput. Syst. Sci. 21(1), 46\u201362 (1980). https:\/\/doi.org\/10.1016\/0022-0000(80)90041-0","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1404_CR11","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/s0304-3975(00)00136-5","volume":"261","author":"T Erlebach","year":"2001","unstructured":"Erlebach, T., Rossmanith, P., Stadtherr, H., Steger, A., Zeugmann, T.: Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries. Theoret. Comput. Sci. 261(1), 119\u2013156 (2001). https:\/\/doi.org\/10.1016\/s0304-3975(00)00136-5","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20133","key":"1404_CR12","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/j.tcs.2008.02.028","volume":"397","author":"YK Ng","year":"2008","unstructured":"Ng, Y.K., Shinohara, T.: Developments from enquiries into the learnability of the pattern languages from positive data. Theoret. Comput. Sci. 397(1\u20133), 150\u2013165 (2008). https:\/\/doi.org\/10.1016\/j.tcs.2008.02.028","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20133","key":"1404_CR13","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.tcs.2008.02.029","volume":"397","author":"D Reidenbach","year":"2008","unstructured":"Reidenbach, D.: Discontinuities in pattern inference. Theoret. Comput. Sci. 397(1\u20133), 166\u2013193 (2008). https:\/\/doi.org\/10.1016\/j.tcs.2008.02.029","journal-title":"Theoret. Comput. Sci."},{"key":"1404_CR14","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/b978-0-08-094829-4.50007-6","volume-title":"Computational Learning Theory, COLT 1989","author":"M Kearns","year":"1989","unstructured":"Kearns, M., Pitt, L.: A polynomial-time algorithm for learning $$k$$-variable pattern languages from examples. In: Rivest, R.L., Haussler, D., Warmuth, M.K. (eds.) Computational Learning Theory, COLT 1989, pp. 57\u201371. Morgan Kaufmann, Burlington, Massachusetts (1989). https:\/\/doi.org\/10.1016\/b978-0-08-094829-4.50007-6"},{"key":"1404_CR15","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.tcs.2018.04.035","volume":"733","author":"H Fernau","year":"2018","unstructured":"Fernau, H., Manea, F., Merca\u015f, R., Schmid, M.L.: Revisiting Shinohara\u2019s algorithm for computing descriptive patterns. Theoret. Comput. Sci. 733, 44\u201354 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2018.04.035","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"1404_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2389241.2389250","volume":"37","author":"P Barcel\u00f3","year":"2012","unstructured":"Barcel\u00f3, P., Libkin, L., Lin, A.W., Wood, P.T.: Expressive languages for path queries over graph-structured data. ACM Trans. Database Syst. 37(4), 1\u201346 (2012). https:\/\/doi.org\/10.1145\/2389241.2389250","journal-title":"ACM Trans. Database Syst."},{"issue":"2","key":"1404_CR17","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s00224-012-9389-0","volume":"53","author":"DD Freydenberger","year":"2013","unstructured":"Freydenberger, D.D.: Extended regular expressions: Succinctness and decidability. Theory Computing Syst. 53(2), 159\u2013193 (2013). https:\/\/doi.org\/10.1007\/s00224-012-9389-0","journal-title":"Theory Computing Syst."},{"key":"1404_CR18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.04.001","author":"DD Freydenberger","year":"2019","unstructured":"Freydenberger, D.D., Schmid, M.L.: Deterministic regular expressions with back-references. J. Comput. Syst. Sci. (2019). https:\/\/doi.org\/10.1016\/j.jcss.2019.04.001","journal-title":"J. Comput. Syst. Sci."},{"key":"1404_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2016.02.003","volume":"249","author":"ML Schmid","year":"2016","unstructured":"Schmid, M.L.: Characterising REGEX languages by regular languages equipped with factor-referencing. Inf. Comput. 249, 1\u201317 (2016). https:\/\/doi.org\/10.1016\/j.ic.2016.02.003","journal-title":"Inf. Comput."},{"key":"1404_CR20","volume-title":"Mastering Regular Expressions","author":"JEF Friedl","year":"2006","unstructured":"Friedl, J.E.F.: Mastering Regular Expressions, 3rd edn. O\u2019Reilly, Sebastopol, CA (2006)","edition":"3"},{"key":"1404_CR21","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/j.ic.2015.03.006","volume":"242","author":"H Fernau","year":"2015","unstructured":"Fernau, H., Schmid, M.L.: Pattern matching with variables: A multivariate complexity analysis. Inf. Comput. 242, 287\u2013305 (2015). https:\/\/doi.org\/10.1016\/j.ic.2015.03.006","journal-title":"Inf. Comput."},{"key":"1404_CR22","doi-asserted-by":"publisher","unstructured":"Fernau, H., Manea, F., Mercas, R., Schmid, M.L.: Pattern matching with variables: Fast algorithms and new hardness results. In: Mayr, E.W., Ollinger, N. (eds.) Symposium on Theoretical Aspects of Computer Science, STACS 2015. LIPIcs, vol. 30, pp. 302\u2013315. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, (2015). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2015.302","DOI":"10.4230\/LIPIcs.STACS.2015.302"},{"issue":"1","key":"1404_CR23","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/s00224-015-9635-3","volume":"59","author":"H Fernau","year":"2016","unstructured":"Fernau, H., Schmid, M.L., Villanger, Y.: On the parameterised complexity of string morphism problems. Theory Computing Syst. 59(1), 24\u201351 (2016). https:\/\/doi.org\/10.1007\/s00224-015-9635-3","journal-title":"Theory Computing Syst."},{"key":"1404_CR24","doi-asserted-by":"publisher","unstructured":"Manea, F., Schmid, M.L.: Matching patterns with variables. In: Combinatorics on Words - 12th International Conference, WORDS 2019, Loughborough, UK, September 9-13, 2019, Proceedings, , pp. 1\u201327 (2019). https:\/\/doi.org\/10.1007\/978-3-030-28796-2_1","DOI":"10.1007\/978-3-030-28796-2_1"},{"key":"1404_CR25","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.ic.2014.08.010","volume":"239","author":"D Reidenbach","year":"2014","unstructured":"Reidenbach, D., Schmid, M.L.: Patterns with bounded treewidth. Inf. Comput. 239, 87\u201399 (2014). https:\/\/doi.org\/10.1016\/j.ic.2014.08.010","journal-title":"Inf. Comput."},{"key":"1404_CR26","unstructured":"Shinohara, T.: Polynomial time inference of pattern languages and its application. In: 7th IBM Symposium on Mathematical Foundations of Computer Science, pp. 191\u2013209. (1982)"},{"key":"1404_CR27","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/978-3-319-98654-8_22","volume-title":"Developments in Language Theory, DLT 2018","author":"JD Day","year":"2018","unstructured":"Day, J.D., Fleischmann, P., Manea, F., Nowotka, D., Schmid, M.L.: On matching generalised repetitive patterns. In: Hoshi, M., Seki, S. (eds.) Developments in Language Theory, DLT 2018. LNCS, vol. 11088, pp. 269\u2013281. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-319-98654-8_22"},{"key":"1404_CR28","doi-asserted-by":"publisher","unstructured":"Casel, K., Day, J.D., Fleischmann, P., Kociumaka, T., Manea, F., Schmid, M.L.: Graph and string parameters: Connections between pathwidth, cutwidth and the locality number. In: 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, , pp. 109\u2013110916 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.109","DOI":"10.4230\/LIPIcs.ICALP.2019.109"},{"issue":"5","key":"1404_CR29","doi-asserted-by":"publisher","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(5), 1305\u20131317 (1996). https:\/\/doi.org\/10.1137\/s0097539793251219","journal-title":"SIAM J. Comput."},{"key":"1404_CR30","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L.: Fixed-parameter tractability of treewidth and pathwidth. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) The Multivariate Algorithmic Revolution and Beyond. LNCS, vol. 7370, pp. 196\u2013227. (2012). https:\/\/doi.org\/10.1007\/978-3-642-30891-8_12","DOI":"10.1007\/978-3-642-30891-8_12"},{"issue":"1","key":"1404_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jalgor.2004.12.001","volume":"56","author":"DM Thilikos","year":"2005","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Cutwidth I: A linear time fixed parameter algorithm. J. Algorithms 56(1), 1\u201324 (2005). https:\/\/doi.org\/10.1016\/j.jalgor.2004.12.001","journal-title":"J. Algorithms"},{"issue":"2","key":"1404_CR32","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1137\/05064299x","volume":"38","author":"U Feige","year":"2008","unstructured":"Feige, U., HajiAghayi, M., Lee, J.R.: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput. 38(2), 629\u2013657 (2008). https:\/\/doi.org\/10.1137\/05064299x","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1404_CR33","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/3576044","volume":"19","author":"C Groenland","year":"2023","unstructured":"Groenland, C., Joret, G., Nadara, W., Walczak, B.: Approximating pathwidth for graphs of small treewidth. ACM Trans. Algorithms 19(2), 16\u201311619 (2023). https:\/\/doi.org\/10.1145\/3576044","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"1404_CR34","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/1502793.1502794","volume":"56","author":"S Arora","year":"2009","unstructured":"Arora, S., Rao, S., Vazirani, U.V.: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2), 5\u20131537 (2009). https:\/\/doi.org\/10.1145\/1502793.1502794","journal-title":"J. ACM"},{"issue":"6","key":"1404_CR35","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"T Leighton","year":"1999","unstructured":"Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787\u2013832 (1999). https:\/\/doi.org\/10.1145\/331524.331526","journal-title":"J. ACM"},{"key":"1404_CR36","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1613\/JAIR.4030","volume":"49","author":"YL Wu","year":"2014","unstructured":"Wu, Y.L., Austrin, P., Pitassi, T., Liu, D.: Inapproximability of treewidth and related problems. J. Artif. Intell. Res 49, 569\u2013600 (2014). https:\/\/doi.org\/10.1613\/JAIR.4030","journal-title":"J. Artif. Intell. Res"},{"key":"1404_CR37","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Germany (2006). https:\/\/doi.org\/10.1007\/3-540-29953-X"},{"key":"1404_CR38","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Germany (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"key":"1404_CR39","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1","author":"G Ausiello","year":"1999","unstructured":"Ausiello, G., Marchetti-Spaccamela, A., Crescenzi, P., Gambosi, G., Protasi, M., Kann, V.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer (1999). https:\/\/doi.org\/10.1007\/978-3-642-58412-1","journal-title":"Springer"},{"issue":"1","key":"1404_CR40","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/bf01442866","volume":"6","author":"C Hierholzer","year":"1873","unstructured":"Hierholzer, C., Wiener, C.: \u00dcber die M\u00f6glichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Math. Ann. 6(1), 30\u201332 (1873). https:\/\/doi.org\/10.1007\/bf01442866","journal-title":"Math. Ann."},{"issue":"3","key":"1404_CR41","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1137\/0606044","volume":"6","author":"F Makedon","year":"1985","unstructured":"Makedon, F., Papadimitriou, C.H., Sudborough, I.H.: Topological bandwidth. SIAM J. Algeb. Discrete Methods 6(3), 418\u2013444 (1985). https:\/\/doi.org\/10.1137\/0606044","journal-title":"SIAM J. Algeb. Discrete Methods"},{"issue":"3","key":"1404_CR42","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/s00224-011-9312-0","volume":"50","author":"HL Bodlaender","year":"2012","unstructured":"Bodlaender, H.L., Fomin, F.V., Koster, A.M.C.A., Kratsch, D., Thilikos, D.M.: A note on exact algorithms for vertex ordering problems on graphs. Theory C0omputing Syst. 50(3), 420\u2013432 (2012). https:\/\/doi.org\/10.1007\/s00224-011-9312-0","journal-title":"Theory C0omputing Syst."},{"key":"1404_CR43","doi-asserted-by":"publisher","unstructured":"Raghavendra, P., Steurer, D.: Graph expansion and the unique games conjecture. In: Schulman, L.J. (ed.) 42nd ACM Symposium on Theory of Computing, STOC 2010, pp. 755\u2013764. ACM, (2010). https:\/\/doi.org\/10.1145\/1806689.1806792","DOI":"10.1145\/1806689.1806792"},{"key":"1404_CR44","doi-asserted-by":"publisher","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Reif, J.H. (ed.) 34th Annual ACM Symposium on Theory of Computing, STOC 2002, pp. 767\u2013775. ACM, (2002). https:\/\/doi.org\/10.1145\/509907.510017","DOI":"10.1145\/509907.510017"},{"key":"1404_CR45","doi-asserted-by":"publisher","unstructured":"Raghavendra, P., Steurer, D., Tulsiani, M.: Reductions between expansion problems. In: Computational Complexity, CCC 2012, pp. 64\u201373. IEEE, (2012). https:\/\/doi.org\/10.1109\/CCC.2012.43","DOI":"10.1109\/CCC.2012.43"},{"key":"1404_CR46","doi-asserted-by":"publisher","unstructured":"Khot, S.: On the unique games conjecture (invited survey). In: Computational Complexity, CCC 2010, pp. 99\u2013121. IEEE, (2010). https:\/\/doi.org\/10.1109\/CCC.2010.19","DOI":"10.1109\/CCC.2010.19"},{"issue":"5","key":"1404_CR47","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1145\/2775105","volume":"62","author":"S Arora","year":"2015","unstructured":"Arora, S., Barak, B., Steurer, D.: Subexponential algorithms for unique games and related problems. J. ACM 62(5), 42\u201314225 (2015). https:\/\/doi.org\/10.1145\/2775105","journal-title":"J. ACM"},{"key":"1404_CR48","doi-asserted-by":"publisher","unstructured":"Barak, B., Raghavendra, P., Steurer, D.: Rounding semidefinite programming hierarchies via global correlation. In: Ostrovsky, R. (ed.) 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2011, pp. 472\u2013481. IEEE, (2011). https:\/\/doi.org\/10.1109\/focs.2011.95","DOI":"10.1109\/focs.2011.95"},{"key":"1404_CR49","doi-asserted-by":"publisher","unstructured":"Guruswami, V., Sinop, A.K.: Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with PSD objectives. In: Ostrovsky, R. (ed.) 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2011, pp. 482\u2013491. IEEE, (2011). https:\/\/doi.org\/10.1109\/FOCS.2011.36","DOI":"10.1109\/FOCS.2011.36"},{"key":"1404_CR50","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/978-3-642-11269-0_27","volume-title":"Parameterized and Exact Computation, IWPEC 2009","author":"K Suchan","year":"2009","unstructured":"Suchan, K., Villanger, Y.: Computing pathwidth faster than $$2^n$$. In: Chen, J., Fomin, F.V. (eds.) Parameterized and Exact Computation, IWPEC 2009. LNCS, vol. 5917, pp. 324\u2013335. Springer, Germany (2009). https:\/\/doi.org\/10.1007\/978-3-642-11269-0_27"},{"issue":"1","key":"1404_CR51","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2851494","volume":"21","author":"D Coudert","year":"2016","unstructured":"Coudert, D., Mazauric, D., Nisse, N.: Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth. ACM J. Exp. Algorithmics 21(1), 1\u2013311323 (2016). https:\/\/doi.org\/10.1145\/2851494","journal-title":"ACM J. Exp. Algorithmics"},{"key":"1404_CR52","doi-asserted-by":"publisher","unstructured":"Dell, H., Komusiewicz, C., Talmon, N., Weller, M.: The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. In: Lokshtanov, D., Nishimura, N. (eds.) Parameterized and Exact Computation, IPEC 2017. LIPIcs, vol. 89, pp. 30\u201313012. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, (2017). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2017.30","DOI":"10.4230\/LIPIcs.IPEC.2017.30"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01404-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-026-01404-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01404-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T05:33:14Z","timestamp":1790659994000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-026-01404-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8,24]]},"references-count":52,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2026,10]]}},"alternative-id":["1404"],"URL":"https:\/\/doi.org\/10.1007\/s00453-026-01404-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,8,24]]},"assertion":[{"value":"21 June 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 August 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 August 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"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. The authors have no relevant financial or non-financial interests to disclose.","order":1,"name":"Ethics","label":"Conflict of interest","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"61"}}