{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:45:31Z","timestamp":1787323531194,"version":"build-2736575974"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"name":"Graph Algorithms for Parameterized Approximation","award":["38593YJ PHC"],"award-info":[{"award-number":["38593YJ PHC"]}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-17-CE40-0022"],"award-info":[{"award-number":["ANR-17-CE40-0022"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004794","name":"Centre National de la Recherche Scientifique","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004794","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>In Defective Coloring we are given a graph $G=(V,E)$ and two integers ${\\chi_d},\\Delta^*$ and are asked if we can partition $V$ into ${\\chi_d}$ color classes, so that each class induces a graph of maximum degree $\\Delta^*$. We investigate the complexity of this generalization of Coloring with respect to several well-studied graph parameters and show that the problem is W-hard parameterized by treewidth, pathwidth, tree-depth, or feedback vertex set if ${\\chi_d}=2$. As expected, this hardness can be extended to larger values of ${\\chi_d}$ for most of these parameters, with one surprising exception: we show that the problem is fixed parameter tractable (FPT) and parameterized by feedback vertex set for any ${\\chi_d}\\neq 2$, and hence 2-coloring is the only hard case for this parameter. In addition to the above, we give an exponential time hypothesis-based lower bound for treewidth and pathwidth, showing that no algorithm can solve the problem in $n^{o({{pw}})}$, essentially matching the complexity of an algorithm obtained with standard techniques. We complement these results by considering the problem's approximability and show that, with respect to $\\Delta^*$, the problem admits an algorithm which for any $\\epsilon&gt;0$ runs in time $({{tw}}\/\\epsilon)^{O({{tw}})}$ and returns a solution with exactly the desired number of colors that approximates the optimal $\\Delta^*$ within $(1+\\epsilon)$. We also give a $({{tw}})^{O({{tw}})}$ algorithm which achieves the desired $\\Delta^*$ exactly while 2-approximating the minimum value of ${\\chi_d}$. We show that this is close to optimal, by establishing that no FPT algorithm can (under standard assumptions) achieve a better than 3\/2-approximation to ${\\chi_d}$, even when an extra constant additive error is also allowed.<\/jats:p>","DOI":"10.1137\/18m1223666","type":"journal-article","created":{"date-parts":[[2020,4,21]],"date-time":"2020-04-21T15:13:19Z","timestamp":1587481999000},"page":"1084-1106","source":"Crossref","is-referenced-by-count":8,"title":["Parameterized (Approximate) Defective Coloring"],"prefix":"10.1137","volume":"34","author":[{"given":"R\u00e9my","family":"Belmonte","sequence":"first","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"}]}],"member":"351","published-online":{"date-parts":[[2020,4,21]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2010.08.013"},{"key":"atypb2","first-page":"33","volume":"47","author":"Andrews J. A.","year":"1985","journal-title":"Congr. Numer."},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"E. Angel, E. Bampis, B. Escoffier, and M. Lampis,\n                      Parameterized power vertex cover\n                      , Discrete Math. Theor. Comput. Sci., 20 (2018),http:\/\/dmtcs.episciences.org\/4873.","DOI":"10.23638\/DMTCS-20-2-10"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00418"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2012.07.001"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190110408"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.11.018"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2015.05.007"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"R. Belmonte, M. Lampis, and V. Mitsou,\n                      Defective Coloring on Classes of Perfect Graphs\n                      , e-print, 2017,http:\/\/arxiv.org\/abs\/1702.08903.","DOI":"10.1007\/978-3-319-68705-6_9"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830910000747"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289859"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm037"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2013.07.014"},{"key":"atypb14","unstructured":"I. Choi and L. Esperet,\n                      Improper Coloring of Graphs on Surfaces\n                      , e-print, 2016,https:\/\/arxiv.org\/abs\/1603.02841."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190100207"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, Cham, 2015,https:\/\/doi.org\/10.1007\/978-3-319-21275-3.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Texts Comput. Sci., Springer, Cham, 2013,https:\/\/doi.org\/10.1007\/978-1-4471-5559-1.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1587"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.11.026"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"J. Flum and M. Grohe,\n                      Parameterized Complexity Theory\n                      , Texts Theoret. Comput. Sci. EATCS Ser., Springer, Cham, 2006,https:\/\/doi.org\/10.1007\/3-540-29953-X.","DOI":"10.1007\/3-540-29953-X"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70374-1"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)90260-7"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"J. Gajarsk\u00fd, M. Lampis, and S. Ordyniak,\n                      Parameterized algorithms for modular-width\n                      , in Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, G. Gutin and S. Szeider, eds., Lecture Notes in Comput. Sci. 8246, Springer, Cham, 2013, pp. 163-176,https:\/\/doi.org\/10.1007\/978-3-319-03898-8_15.","DOI":"10.1007\/978-3-319-03898-8_15"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21868"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2016.03.013"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1002\/net.20318"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20155"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"L. Jaffke and B. M. P. Jansen,\n                      Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems\n                      , e-print, 2017,http:\/\/arxiv.org\/abs\/1701.06985.","DOI":"10.1007\/978-3-319-57586-5_29"},{"key":"atypb32","unstructured":"R. J. Kang,\n                      Improper Colourings of Graphs\n                      , Ph.D. thesis, University of Oxford, UK, 2008,http:\/\/ora.ox.ac.uk\/objects\/uuid:a93d8303-0eeb-4d01-9b77-364113b81a63."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990216"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"I. Katsikarelis, M. Lampis, and V. T. Paschos,\n                      Structurally parameterized d-scattered set\n                      , in Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings, A. Brandst\u00e4dt, E. K\u00f6hler, and K. Meer, eds., Lecture Notes Comput. Sci. 11159, Springer, Cham, 2018, pp. 292-305,https:\/\/doi.org\/10.1007\/978-3-030-00256-5_24.","DOI":"10.1007\/978-3-030-00256-5_24"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.11.002"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2014.05.003"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21886"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9554-x"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"M. Lampis,\n                      Parameterized approximation schemes using graph widths\n                      , in Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, J. Esparza, P. Fraigniaud, T. Husfeldt, and E. Koutsoupias, eds., Lecture Notes Comput. Sci. 8572, Springer, Cham, 2014, pp. 775-786,https:\/\/doi.org\/10.1007\/978-3-662-43948-7_64.","DOI":"10.1007\/978-3-662-43948-7_64"},{"key":"atypb40","unstructured":"M. Lampis,\n                      Finer tight bounds for coloring on clique-width\n                      , in 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, I. Chatzigiannakis, C. Kaklamanis, D. Marx, and D. Sannella, eds., LIPIcs. Leibniz Int. Proc. Inform. 107, 2018, pp. 86:1-86:14,https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.86."},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"D. Lokshtanov, D. Marx, and S. Saurabh,\n                      Known algorithms on graphs on bounded treewidth are probably optimal\n                      , in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, CA, January 23-25, 2011, D. Randall, ed., SIAM, 2011, pp. 777-789,https:\/\/doi.org\/10.1137\/1.9781611973082.61.","DOI":"10.1137\/1.9781611973082.61"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.01.010"},{"key":"atypb43","doi-asserted-by":"crossref","unstructured":"R. Niedermeier,\n                      Invitation to Fixed-Parameter Algorithms\n                      , Oxford Lecture Ser. Math. Appl., Oxford University Press, Oxford, UK, 2006.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1223666","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:07:49Z","timestamp":1787321269000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1223666"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/18M1223666"],"URL":"https:\/\/doi.org\/10.1137\/18m1223666","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}