{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T11:38:05Z","timestamp":1770896285912,"version":"3.50.1"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,11,16]],"date-time":"2018-11-16T00:00:00Z","timestamp":1542326400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme","award":["648527"],"award-info":[{"award-number":["648527"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,4,30]]},"abstract":"<jats:p>\n            Nowhere dense classes of graphs [21, 22] are very general classes of uniformly sparse graphs with several seemingly unrelated characterisations. From an algorithmic perspective, a characterisation of these classes in terms of\n            <jats:italic>uniform quasi-wideness<\/jats:italic>\n            , a concept originating in finite model theory, has proved to be particularly useful. Uniform quasi-wideness is used in many fpt-algorithms on nowhere dense classes. However, the existing constructions showing the equivalence of nowhere denseness and uniform quasi-wideness imply a non-elementary blow up in the parameter dependence of the fpt-algorithms, making them infeasible in practice. As a first main result of this article, we use tools from logic, in particular from a sub-field of model theory known as stability theory, to establish polynomial bounds for the equivalence of nowhere denseness and uniform quasi-wideness. A powerful method in parameterized complexity theory is to compute a problem kernel in a pre-computation step, that is, to reduce the input instance in polynomial time to a sub-instance of size bounded in the parameter only (independently of the input graph size). Our new tools allow us to obtain for every fixed radius\n            <jats:italic>r<\/jats:italic>\n            \u2208 N a polynomial kernel for the distance-\n            <jats:italic>r<\/jats:italic>\n            dominating set problem on nowhere dense classes of graphs. This result is particularly interesting, as it implies that for every class\n            <jats:italic>C<\/jats:italic>\n            of graphs that is closed under taking subgraphs, the distance-\n            <jats:italic>r<\/jats:italic>\n            dominating set problem admits a kernel on\n            <jats:italic>C<\/jats:italic>\n            for every value of\n            <jats:italic>r<\/jats:italic>\n            if, and only if, it already admits a polynomial kernel for every value of\n            <jats:italic>r<\/jats:italic>\n            (under the standard assumption of parameterized complexity theory that FPT \u2260 W[2]).\n          <\/jats:p>","DOI":"10.1145\/3274652","type":"journal-article","created":{"date-parts":[[2018,11,16]],"date-time":"2018-11-16T13:08:54Z","timestamp":1542373734000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes"],"prefix":"10.1145","volume":"15","author":[{"given":"Stephan","family":"Kreutzer","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}]},{"given":"Roman","family":"Rabinovich","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}]},{"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2018,11,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.06.048"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990309"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science 2009 (FOCS\u201909)","author":"Bodlaender Hans L.","unstructured":"Hans L. Bodlaender , Fedor V. Fomin , Daniel Lokshtanov , Eelko Penninkx , Saket Saurabh , and Dimitrios M. Thilikos . 2009. (Meta) kernelization . In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science 2009 (FOCS\u201909) . IEEE, 629--638. Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. 2009. (Meta) kernelization. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science 2009 (FOCS\u201909). IEEE, 629--638."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.10.005"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201909)","author":"Dawar Anuj","year":"2009","unstructured":"Anuj Dawar and Stephan Kreutzer . 2009 . Domination problems in nowhere-dense classes . In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201909) . 157--168. Anuj Dawar and Stephan Kreutzer. 2009. Domination problems in nowhere-dense classes. In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201909). 157--168."},{"key":"e_1_2_1_6_1","volume-title":"Demaine and MohammadTaghi Hajiaghayi","author":"Erik","year":"2004","unstructured":"Erik D. Demaine and MohammadTaghi Hajiaghayi . 2004 . Equivalence of local treewidth and linear local treewidth and its algorithmic applications. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 840--849. Erik D. Demaine and MohammadTaghi Hajiaghayi. 2004. Equivalence of local treewidth and linear local treewidth and its algorithmic applications. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 840--849."},{"key":"e_1_2_1_7_1","volume-title":"Graph Theory: Springer Graduate Text GTM 173.","author":"Diestel Reinhard","year":"2012","unstructured":"Reinhard Diestel . 2012 . Graph Theory: Springer Graduate Text GTM 173. Vol. 173 . Reinhard Diestel . Reinhard Diestel. 2012. Graph Theory: Springer Graduate Text GTM 173. Vol. 173. Reinhard Diestel."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916)","author":"Drange P\u00e5l Gr\u00f8n\u00e5s","year":"2016","unstructured":"P\u00e5l Gr\u00f8n\u00e5s Drange , Markus Sortland Dregi , Fedor V. Fomin , Stephan Kreutzer , Daniel Lokshtanov , Marcin Pilipczuk , Micha\u0142 Pilipczuk , Felix Reidl , Fernando Sanchez Villaamil , Saket Saurabh , Sebastian Siebertz , and Somnath Sikdar . 2016 . Kernelization and sparseness: The case of dominating set . In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916) . 31:1--31:14. P\u00e5l Gr\u00f8n\u00e5s Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Micha\u0142 Pilipczuk, Felix Reidl, Fernando Sanchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. 2016. Kernelization and sparseness: The case of dominating set. In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916). 31:1--31:14."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS'16)","author":"Drange P\u00e5l Gr\u00f8n\u00e5s","year":"2016","unstructured":"P\u00e5l Gr\u00f8n\u00e5s Drange , Markus S. Dregi , Fedor V. Fomin , Stephan Kreutzer , Daniel Lokshtanov , Marcin Pilipczuk , Micha\u0142 Pilipczuk , Felix Reidl , Saket Saurabh , Fernando S\u00e1nchez Villaamil , Saket Saurabh , Sebastian Siebertz , and Somnath Sikdar . 2016 . Kernelization and sparseness: The case of dominating set . In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS'16) . 31:1--31:14. https:\/\/arxiv.org\/abs\/1411.4575. P\u00e5l Gr\u00f8n\u00e5s Drange, Markus S. Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Micha\u0142 Pilipczuk, Felix Reidl, Saket Saurabh, Fernando S\u00e1nchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. 2016. Kernelization and sparseness: The case of dominating set. In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS'16). 31:1--31:14. https:\/\/arxiv.org\/abs\/1411.4575."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_11_1","volume-title":"Thilikos","author":"Fomin Fedor V.","year":"2010","unstructured":"Fedor V. Fomin , Daniel Lokshtanov , Saket Saurabh , and Dimitrios M . Thilikos . 2010 . Bidimensionality and kernels. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 503--510. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. 2010. Bidimensionality and kernels. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 503--510."},{"key":"e_1_2_1_12_1","volume-title":"Thilikos","author":"Fomin Fedor V.","year":"2012","unstructured":"Fedor V. Fomin , Daniel Lokshtanov , Saket Saurabh , and Dimitrios M . Thilikos . 2012 . Linear kernels for (connected) dominating set on H-minor-free graphs. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM , 82--93. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. 2012. Linear kernels for (connected) dominating set on H-minor-free graphs. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 82--93."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913)","author":"Fomin Fedor V.","unstructured":"Fedor V. Fomin , Daniel Lokshtanov , Saket Saurabh , and Dimitrios M. Thilikos . 2013. Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs . In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913) . 92--103. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. 2013. Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs. In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913). 92--103."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.09.002"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591851"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/120892234"},{"key":"e_1_2_1_17_1","volume-title":"Model Theory","author":"Hodges Wilfrid","unstructured":"Wilfrid Hodges . 1993. Model Theory . Vol. 42 . Cambridge University Press . Wilfrid Hodges. 1993. Model Theory. Vol. 42. Cambridge University Press."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2013-05820-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.013"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.014"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1278682204"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.01.006"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez. 2012. Sparsity. Springer.  Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez. 2012. Sparsity. Springer.","DOI":"10.1007\/978-3-642-27875-4"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-100-2-101-107"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90019-2"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1972.41.247"},{"key":"e_1_2_1_28_1","volume-title":"Classification Theory: And the Number of Non-isomorphic Models.","author":"Shelah Saharon","year":"1990","unstructured":"Saharon Shelah . 1990 . Classification Theory: And the Number of Non-isomorphic Models. Vol. 92 . Elsevier . Saharon Shelah. 1990. Classification Theory: And the Number of Non-isomorphic Models. Vol. 92. Elsevier."},{"key":"e_1_2_1_29_1","volume-title":"Chervonenkis","author":"Vapnik Vladimir N.","year":"2015","unstructured":"Vladimir N. Vapnik and Alexey Y . Chervonenkis . 2015 . On the uniform convergence of relative frequencies of events to their probabilities. In Measures of Complexity. Springer , 11--30. Vladimir N. Vapnik and Alexey Y. Chervonenkis. 2015. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of Complexity. Springer, 11--30."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274652","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3274652","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:56Z","timestamp":1750208276000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274652"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,16]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4,30]]}},"alternative-id":["10.1145\/3274652"],"URL":"https:\/\/doi.org\/10.1145\/3274652","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,16]]},"assertion":[{"value":"2017-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}