{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:58:25Z","timestamp":1787385505878,"version":"build-2736575974"},"reference-count":50,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P26696"],"award-info":[{"award-number":["P26696"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["W1255-N23"],"award-info":[{"award-number":["W1255-N23"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["715744"],"award-info":[{"award-number":["715744"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["665778"],"award-info":[{"award-number":["665778"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["UMO-2015\/19\/P\/ST6\/03998"],"award-info":[{"award-number":["UMO-2015\/19\/P\/ST6\/03998"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>For $\\alpha &gt; 1$, an $\\alpha$-approximate (bi)kernel is a polynomial-time algorithm that takes as input an instance $(I, k)$ of a problem $\\mathcal{Q}$ and outputs an instance $(I',k')$ (of a problem $\\mathcal{Q}'$) of size bounded by a function of $k$ such that, for every $c\\geq 1$, a $c$-approximate solution for the new instance can be turned into a $(c\\cdot\\alpha)$-approximate solution of the original instance in polynomial time. This framework of lossy kernelization was recently introduced by Lokshtanov and co-authors. We study Connected Dominating Set (and its distance-$r$ variant) parameterized by solution size on sparse graph classes like biclique-free graphs, classes of bounded expansion, and nowhere dense classes. We prove that for every $\\alpha&gt;1$, Connected Dominating Set admits a polynomial-size $\\alpha$-approximate (bi)kernel on all the aforementioned classes. Our results are in sharp contrast to the kernelization complexity of Connected Dominating Set, which is known to not admit a polynomial kernel even on $2$-degenerate graphs and graphs of bounded expansion, unless ${NP} \\subseteq \\textsf{coNP\/poly}$. We complement our results by the following conditional lower bound. We show that if a class $\\mathcal{C}$ is somewhere dense and closed under taking subgraphs, then for some value of $r\\in \\mathbb{N}$ there cannot exist an $\\alpha$-approximate bi-kernel for the (Connected) Distance-$r$ Dominating Set problem on $\\mathcal{C}$ for any $\\alpha&gt;1$ (assuming ${FPT}\\neq{W}[1]$).<\/jats:p>","DOI":"10.1137\/18m1172508","type":"journal-article","created":{"date-parts":[[2019,9,26]],"date-time":"2019-09-26T13:29:31Z","timestamp":1569504571000},"page":"1743-1771","source":"Crossref","is-referenced-by-count":10,"title":["Lossy Kernels for Connected Dominating Set on Sparse Graphs"],"prefix":"10.1137","volume":"33","author":[{"given":"Eduard","family":"Eiben","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mithilesh","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amer E.","family":"Mouawad","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6347-1198","authenticated-orcid":true,"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,9,26]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990309"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9204-0"},{"key":"atypb3","first-page":"67","author":"Bj\u00f6rklund A.","year":"2007","journal-title":"New York"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, and D. M. Thilikos,\n                      (Meta) Kernelization\n                      , in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, pp. 629-638.","DOI":"10.1109\/FOCS.2009.46"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"A. Brandst\u00e4dt, V. B. Le, and J. P. Spinrad,\n                      Graph Classes: A Survey\n                      , SIAM, Philadelphia, 1999.","DOI":"10.1137\/1.9780898719796"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"P. Chalermsook, M. Cygan, G. Kortsarz, B. Laekhanukit, P. Manurangsi, D. Nanongkai, and L. Trevisan,\n                      From GAP-ETH to FPT-inapproximability: Clique, dominating set, and more\n                      , in Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017, pp. 743-754.","DOI":"10.1109\/FOCS.2017.74"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, \u0141. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Vol. 3, Springer, New York, 2015.","DOI":"10.1007\/978-3-319-21275-3_1"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. Grandoni, and D. Hermelin,\n                      Tight kernel bounds for problems on graphs with small degeneracy\n                      , in Proceedings of the 21st Annual European Symposium on Algorithms, 2013, pp. 361-372.","DOI":"10.1007\/978-3-642-40450-4_31"},{"key":"atypb9","unstructured":"A. Dawar and S. Kreutzer,\n                      Domination problems in nowhere-dense classes\n                      , in FSTTCS 2009, LIPIcs 4, Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2009, pp. 157-168."},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , 4th ed., Grad. Texts in Math. 173, Springer, New York, 2012.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Parameterized Complexity\n                      , Springer, New York, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Vol. 4, Springer, New York, 2013.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb13","unstructured":"P. G. Drange, M. S. Dregi, F. V. Fomin, S. Kreutzer, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, F. Reidl, F. S. Villaamil, S. Saurabh, S. Siebertz, and S. Sikdar,\n                      Kernelization and sparseness: The case of dominating set\n                      , in Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016, pp. 31:1-31:14."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2012.12.004"},{"key":"atypb15","unstructured":"K. Eickmeyer, A. C. Giannopoulou, S. Kreutzer, O. Kwon, M. Pilipczuk, R. Rabinovich, and S. Siebertz,\n                      Neighborhood complexity and kernelization for nowhere dense classes of graphs\n                      , in Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017, pp. 63:1-63:14."},{"key":"atypb16","unstructured":"G. Fabia\u0144ski, M. Pilipczuk, S. Siebertz, and S. Toru\u0144czyk,\n                      Progressive algorithms for domination and independence\n                      , in Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019, pp. 27:1-27:16."},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos,\n                      Bidimensionality and kernels\n                      , in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, pp. 503-510.","DOI":"10.1137\/1.9781611973075.43"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos,\n                      \n                        Linear kernels for (connected) dominating set on\n                        H\n                        -minor-free graphs\n                      \n                      , in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, 2012, pp. 82-93.","DOI":"10.1137\/1.9781611973099.7"},{"key":"atypb19","unstructured":"F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos,\n                      Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs\n                      , in Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013, pp. 92-103."},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi,\n                      Kernelization: Theory of Parameterized Preprocessing\n                      , Cambridge University Press, Cambridge, 2019.","DOI":"10.1017\/9781107415157"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.09.002"},{"key":"atypb22","first-page":"325","volume":"2015","author":"Grohe M.","year":"2015","journal-title":"WG"},{"key":"atypb23","first-page":"89","volume":"2014","author":"Grohe M.","year":"2014","journal-title":"STOC"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"S. Har-Peled and K. Quanrud,\n                      Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs\n                      , arXiv:1501.00721, 2015.","DOI":"10.1007\/978-3-662-48350-3_60"},{"key":"atypb25","first-page":"717","author":"Har-Peled S.","year":"2015","journal-title":"New York"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"C. S. Karthik, B. Laekhanukit, and P. Manurangsi,\n                      On the parameterized complexity of approximating dominating set\n                      , in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 1283-1296.","DOI":"10.1145\/3188745.3188896"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1023\/B:ORDE.0000026489.93166.cb"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1145\/2797140"},{"key":"atypb29","unstructured":"S. Kreutzer, M. Pilipczuk, R. Rabinovich, and S. Siebertz,\n                      The generalised colouring numbers on classes of bounded expansion\n                      , in Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016, pp. 85:1-85:13."},{"key":"atypb30","first-page":"1533","author":"Kreutzer S.","year":"2017","journal-title":"Philadelphia"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.10.045"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"D. Lokshtanov, A. E. Mouawad, F. Panolan, M. S. Ramanujan, and S. Saurabh,\n                      Reconfiguration on sparse graphs\n                      , in Proceedings of the 14th International Symposium on Algorithms and Data Structures, 2015, pp. 506-517.","DOI":"10.1007\/978-3-319-21840-3_42"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"D. Lokshtanov, F. Panolan, M. S. Ramanujan, and S. Saurabh,\n                      Lossy kernelization\n                      , in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 224-237.","DOI":"10.1145\/3055399.3055456"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11440-3_25"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.013"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.014"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.11.019"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1278682204"},{"key":"atypb39","unstructured":"J. Nesetril and P. Ossona de Mendez,\n                      From sparse graphs to nowhere dense structures: Decompositions, independence, dualities and limits\n                      , European Congress of Mathematics, 2010."},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.01.006"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"J. Ne\u0161et\u0159il and P. Ossona de Mendez,\n                      Sparsity-Graphs, Structures, and Algorithms\n                      , Algorithms Combin. 28, Springer, New York, 2012.","DOI":"10.1007\/978-3-642-27875-4"},{"key":"atypb42","first-page":"694","author":"Philip G.","year":"2009","journal-title":"New York"},{"key":"atypb43","first-page":"9","author":"Philip G.","year":"2012","journal-title":"ACM Trans. Algorithms"},{"key":"atypb44","first-page":"799","author":"Pilipczuk M.","year":"2018","journal-title":"Computer Science"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2018.08.001"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90019-2"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1972.41.247"},{"key":"atypb48","first-page":"802","author":"Telle J. A.","year":"2012","journal-title":"New York"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2015.06.072"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.03.024"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1172508","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:26:08Z","timestamp":1787318768000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1172508"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/18M1172508"],"URL":"https:\/\/doi.org\/10.1137\/18m1172508","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}