{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:37:10Z","timestamp":1787323030777,"version":"build-2736575974"},"reference-count":88,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["18-CE40-0025-01"],"award-info":[{"award-number":["18-CE40-0025-01"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["21-CE48-0022"],"award-info":[{"award-number":["21-CE48-0022"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18K11157"],"award-info":[{"award-number":["JP18K11157"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18K11168"],"award-info":[{"award-number":["JP18K11168"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18K11169"],"award-info":[{"award-number":["JP18K11169"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18H04091"],"award-info":[{"award-number":["JP18H04091"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:p>Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to understand the \u201cprice of generality\u201d of these widths: as we transition from more restrictive to more general notions, which are the problems that see their complexity status deteriorate from fixed-parameter tractable (FPT) to intractable? This type of question is by now very well studied, but somewhat strikingly, the algorithmic frontier between the two (arguably) most central width notions, treewidth and pathwidth, is still not understood: currently, no natural graph problem is known to be W-hard for one but FPT for the other. Indeed, a surprising development of the last few years has been the observation that, for many of the most paradigmatic problems, their complexities for the two parameters actually coincide exactly, despite the fact that treewidth is a much more general parameter. It would thus appear that the extra generality of treewidth over pathwidth often comes \u201cfor free.\u201d Our main contribution in this paper is to uncover the first natural example where this generality comes with a high price. We consider Grundy Coloring, a variation of coloring where one seeks to calculate the worst possible coloring that could be assigned to a graph by a greedy first-fit algorithm. We show that this well-studied problem is FPT parameterized by pathwidth; however, it becomes significantly harder (W[1]-hard) when parameterized by treewidth. Furthermore, we show that Grundy Coloring makes a second complexity jump for more general widths, as it becomes para-NP--hard for clique-width. Hence, Grundy Coloring nicely captures the complexity trade-offs between the three most well-studied parameters. Completing the picture, we show that Grundy Coloring is FPT parameterized by modular-width.<\/jats:p>","DOI":"10.1137\/20m1385779","type":"journal-article","created":{"date-parts":[[2022,7,28]],"date-time":"2022-07-28T15:01:47Z","timestamp":1659020507000},"page":"1761-1787","source":"Crossref","is-referenced-by-count":5,"title":["Grundy Distinguishes Treewidth from Pathwidth"],"prefix":"10.1137","volume":"36","author":[{"given":"R\u00e9my","family":"Belmonte","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6824-0516","authenticated-orcid":true,"given":"Eun Jung","family":"Kim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5791-0887","authenticated-orcid":true,"given":"Michael","family":"Lampis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Valia","family":"Mitsou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2022,7,28]]},"reference":[{"key":"atypb1","volume-title":"Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science, STACS 2020","author":"Aboulker P.","year":"2020"},{"key":"atypb2","doi-asserted-by":"crossref","first-page":"4256","DOI":"10.23638\/DMTCS-20-2-10","volume":"20","author":"Angel E.","year":"2018","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.08.016"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0252-6"},{"key":"atypb5","first-page":"694","volume-title":"Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018","author":"Aziz H.","year":"2018"},{"key":"atypb6","first-page":"43","volume-title":"IWOCA 2020","author":"Belmonte R.","year":"2020"},{"key":"atypb7","first-page":"1","volume-title":"43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), I. Potapov, P. G. Spirakis, and J. Worrell, eds., LIPIcs.Leibniz Int. Proc. Inform. 117","author":"Belmonte R.","year":"2018"},{"key":"atypb8","first-page":"38","volume-title":"CIAC 2019","author":"Belmonte R.","year":"2019"},{"key":"atypb9","first-page":"1","volume-title":"35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), R. Niedermeier and B. Vall\u00e9e, eds., LIPIcs.Leibniz Int. Proc. Inform. 96","author":"Belmonte R.","year":"2018"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.09.007"},{"key":"atypb11","volume-title":"Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters, preprint, arXiv:1910.03409","author":"Bentert M.","year":"2019"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.08.013"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-018-0342-2"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.12.022"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.09.009"},{"key":"atypb17","volume-title":"Metric Dimension Parameterized by Treewidth, preprint, arXiv:1907.08093","author":"Bonnet \u00c9.","year":"2019"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.03.008"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(79)90067-4"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch113"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb24","volume-title":"Discrete Math. Theor. Comput. Sci., 21","author":"Gomes G.","year":"2019"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0310-8"},{"key":"atypb26","first-page":"78","volume-title":"IWPEC 2008","author":"Dom M.","year":"2008"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/110855806"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0408-7"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0496-4"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/28"},{"key":"atypb31","first-page":"122","volume-title":"IWPEC 2009","author":"Enciso R.","year":"2009"},{"key":"atypb32","first-page":"1","volume-title":"15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), LIPIcs.Leibniz Int. Proc. Inform. 53","author":"Ene A.","year":"2016"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00184-5"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.11.026"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.065"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.10.043"},{"key":"atypb37","first-page":"1","volume-title":"24th Annual European Symposium on Algorithms (ESA 2016), LIPIcs. Leibniz Int. Proc. Inform. 57","author":"Fleszar K.","year":"2016"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.42"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/130910932"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1145\/3355629"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579200"},{"key":"atypb42","first-page":"163","volume-title":"IPEC 2013","author":"Gajarsk\u00fd J.","year":"2013"},{"key":"atypb43","first-page":"1","volume-title":"35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), R. Niedermeier and B. Vall\u00e9e, eds., LIPIcs.Leibniz. Int. Proc. Inform. 96","author":"Ganian R.","year":"2018"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2017.12.006"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523685"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2009.05.002"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1137\/15M1034337"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120212"},{"key":"atypb49","first-page":"1","volume-title":"16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), D. Eppstein, ed., LIPIcs.Leibniz Int. Proc. Inform. 101","author":"Hanaka T.","year":"2018"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9604-4"},{"key":"atypb51","volume-title":"On the Parameterized Complexity of Sparsest Cut and Small-Set Expansion Problems, preprint, arXiv:1910.12353","author":"Javadi R.","year":"2019"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.415"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00256-5_24"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.11.002"},{"key":"atypb55","first-page":"427","volume-title":"CALDAM 2020","author":"Kaur C.","year":"2016"},{"key":"atypb56","volume-title":"Parameterized Complexity of Geodetic Set, preprint, arXiv:2001.03098","author":"Kellerhals L.","year":"2020"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.05.002"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2015.05.015"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2018.04.012"},{"key":"atypb60","first-page":"1","volume-title":"44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), P. Rossmanith, P. Heggernes, and J. Katoen, eds., LIPIcs.Leibniz Int. Proc. Inform. 138","author":"Knop D.","year":"2019"},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.46298\/dmtcs.391"},{"key":"atypb62","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9554-x"},{"key":"atypb63","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.01.012"},{"key":"atypb64","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-10(1:18)2014"},{"key":"atypb65","first-page":"1","volume-title":"48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), N. Bansal, E. Merelli, and J. Worrell, eds., LIPIcs.Leibniz Int. Proc. Inform. 198","author":"Lampis M.","year":"2021"},{"key":"atypb66","first-page":"1","volume-title":"12th International Symposium on Parameterized and Exact Computation (IPEC 2017), D. Lokshtanov and N. Nishimura, eds., LIPIcs.Leibniz. Int. Proc. Inform. 89","author":"Lampis M.","year":"2017"},{"key":"atypb67","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"atypb68","volume-title":"Hardness of Metric Dimension in Graphs of Constant Treewidth, preprint, arXiv:2102.09791","author":"Li S.","year":"2021"},{"key":"atypb69","first-page":"1","volume":"14","author":"Lokshtanov D.","year":"2018","journal-title":"ACM Trans. Algorithms"},{"key":"atypb70","first-page":"542","volume-title":"31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), E. W. Mayr and N. Portier, eds., LIPIcs.Leibniz. Int. Proc. Inform. 25","author":"Marx D.","year":"2014"},{"key":"atypb71","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2016.08.001"},{"key":"atypb72","first-page":"1","volume-title":"13th International Symposium on Parameterized and Exact Computation (IPEC 2018), LIPIcs.Leibniz Int. Proc. Inform. 115","author":"Meeks K.","year":"2018"},{"key":"atypb73","doi-asserted-by":"publisher","DOI":"10.1137\/0607057"},{"key":"atypb74","doi-asserted-by":"publisher","DOI":"10.1007\/s11083-008-9076-6"},{"key":"atypb75","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.01.010"},{"key":"atypb76","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-012-0067-7"},{"key":"atypb77","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.12.039"},{"key":"atypb78","volume-title":"Proceedings of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning","author":"Razgon I.","year":"2014"},{"key":"atypb79","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.003"},{"key":"atypb80","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-009-9079-y"},{"key":"atypb81","volume-title":"Not So Easy Problems for Tree Decomposable Graphs, preprint, arXiv:1107.1177","author":"Szeider S.","year":"2011"},{"key":"atypb82","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-015-9981-8"},{"key":"atypb83","first-page":"634","volume-title":"ICALP 2008","author":"Tedder M.","year":"2008"},{"key":"atypb84","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194275825"},{"key":"atypb85","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_51"},{"key":"atypb86","first-page":"325","volume":"31","author":"Zaker M.","year":"2005","journal-title":"Australasian J. Combin."},{"key":"atypb87","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.06.044"},{"key":"atypb88","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.07.002"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1385779","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:38:02Z","timestamp":1787319482000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1385779"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,28]]},"references-count":88,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["10.1137\/20M1385779"],"URL":"https:\/\/doi.org\/10.1137\/20m1385779","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,28]]}}}