{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:55:16Z","timestamp":1787324116809,"version":"build-2736575974"},"reference-count":44,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"name":"Warsaw Center of Mathematics and Computer Science"},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["DEMOGRAPH ANR-16-CE40-0028"],"award-info":[{"award-number":["DEMOGRAPH ANR-16-CE40-0028"]}],"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":["ESIGMA ANR-17-CE23-0010"],"award-info":[{"award-number":["ESIGMA ANR-17-CE23-0010"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["DISTRUCT-648527"],"award-info":[{"award-number":["DISTRUCT-648527"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Suppose ${\\mathcal{F}}$ is a finite family of graphs. We consider the following meta-problem, called $\\mathcal{F}$-Immersion Deletion: given a graph $G$ and integer $k$, decide whether the deletion of at most $k$ edges of $G$ can result in a graph that does not contain any graph from $\\mathcal{F}$ as an immersion. This problem is a close relative of the $\\mathcal{F}$-Minor Deletion problem studied by Fomin et al. [ Proceedings of FOCS, IEEE, 2012, pp. 470--479], where one deletes vertices in order to remove all minor models of graphs from $\\mathcal{F}$. We prove that whenever all graphs from $\\mathcal{F}$ are connected and at least one graph of $\\mathcal{F}$ is planar and subcubic, then the $\\mathcal{F}$-Immersion Deletion problem admits a constant-factor approximation algorithm running in time $\\mathcal{O}(m^3 \\cdot n^3 \\cdot \\log m)$, a linear kernel that can be computed in time $\\mathcal{O}(m^4 \\cdot n^3 \\cdot \\log m)$, and a $\\mathcal{O}(2^{\\mathcal{O}(k)} + m^4 \\cdot n^3 \\cdot \\log m)$-time fixed-parameter algorithm, where $n,m$ count the vertices and edges of the input graph. These results mirror the findings of Fomin et al., who obtained a similar set of algorithmic results for $\\mathcal{F}$-Minor Deletion, under the assumption that at least one graph from $\\mathcal{F}$ is planar. An important difference is that we are able to obtain a linear kernel for $\\mathcal{F}$-Immersion Deletion, while the exponent of the kernel of Fomin et al. for $\\mathcal{F}$-Minor Deletion depends heavily on the family $\\mathcal{F}$. In fact, this dependence is unavoidable under plausible complexity assumptions, as proven by Giannopoulou et al. [ ACM Trans. Algorithms, 13 (2017), p. 35]. This reveals that the kernelization complexity of $\\mathcal{F}$-Immersion Deletion is quite different from that of $\\mathcal{F}$-Minor Deletion.<\/jats:p>","DOI":"10.1137\/18m1228839","type":"journal-article","created":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T14:56:01Z","timestamp":1611240961000},"page":"105-151","source":"Crossref","is-referenced-by-count":11,"title":["Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes"],"prefix":"10.1137","volume":"35","author":[{"given":"Archontia","family":"Giannopoulou","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4646-7602","authenticated-orcid":true,"given":"Jean-Florent","family":"Raymond","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9346-2172","authenticated-orcid":true,"given":"Marcin","family":"Wrochna","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,1,21]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"atypb2","unstructured":"R. Belmonte, A. Giannopoulou, D. Lokshtanov, and D. M. Thilikos,\n                      The Structure of $W_4$-Immersion-Free Graphs\n                      ,arXiv:1602.02002, 2016."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"atypb4","first-page":"629","author":"Bodlaender H. L.","year":"2009","journal-title":"IEEE Computer Society"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/2973749"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0991"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0313-5"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2017.04.011"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/2820609"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032077"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746551"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy,\n                      Improved Bounds for the Excluded Grid Theorem\n                      ,arXiv:1602.02629, 2016.","DOI":"10.1145\/2746539.2746551"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"atypb14","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, New York, 2015,https:\/\/doi.org\/10.1007\/978-3-319-21275-3.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-2806-z"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21990"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22206"},{"key":"atypb18","unstructured":"J. Flum and M. Grohe,\n                      Parameterized Complexity Theory\n                      , Texts in Theoret. Comput. Sci., Springer-Verlag, Berlin, 2006."},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"F. V. Fomin, D. Lokshtanov, N. Misra, and S. Saurabh,\n                      Planar $\\mathcal{F}$-Deletion: Approximation and optimal FPT algorithms\n                      ,arXiv:1204.4230, 2012.","DOI":"10.1109\/FOCS.2012.62"},{"key":"atypb20","first-page":"470","author":"Fomin F. V.","year":"2012","journal-title":"IEEE Computer Society"},{"key":"atypb21","first-page":"503","author":"Fomin F. V.","year":"2010","journal-title":"Philadelphia"},{"key":"atypb22","first-page":"246","volume":"1983","author":"Gabow H. N.","year":"1983","journal-title":"Proceedings of STOC"},{"key":"atypb23","first-page":"348","author":"Ganian R.","year":"2015","journal-title":"New York"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1145\/3029051"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2017.05.009"},{"key":"atypb26","unstructured":"A. C. Giannopoulou, M. Pilipczuk, J.F. Raymond, D. M. Thilikos, and M. Wrochna,\n                      Linear kernels for edge deletion problems to immersion-closed graph classes\n                      , in Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, I. Chatzigiannakis, P. Indyk, F. Kuhn, and A. Muscholl, eds., LIPIcs. Leibniz Int. Proc. Inform. 80, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017, pp. 57:1-57:15,https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.57."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.07.008"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00080-7"},{"key":"atypb29","first-page":"479","volume":"2011","author":"Grohe M.","year":"2011","journal-title":"Proceedings of STOC"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90012-L"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1145\/2797140"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0245-5"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00029-8"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1137\/130924056"},{"key":"atypb36","first-page":"182","author":"Naor M.","year":"1995","journal-title":"IEEE Computer Society"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"R. Niedermeier,\n                      Invitation to Fixed-Parameter Algorithms\n                      , Oxford Lect. Ser. Math. Appl. 31, Oxford University Press, Oxford, UK, 2006.","DOI":"10.1093\/acprof:oso\/9780198566076.003.0004"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2009.07.003"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215352"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.12.001"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.07.003"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1228839","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:18:58Z","timestamp":1787321938000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1228839"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/18M1228839"],"URL":"https:\/\/doi.org\/10.1137\/18m1228839","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}