Linear kernels for edge deletion problems to immersion-closed graph classes

Archontia Giannopoulou, Michal Pilipczuk, Jean Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna

Research output: Contribution to journalArticlepeer-review


Suppose F is a finite family of graphs. We consider the following meta-problem, called 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 F as an immersion. This problem is a close relative of the 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 F . We prove that whenever all graphs from F are connected and at least one graph of F is planar and subcubic, then the F-Immersion Deletion problem admits a constant-factor approximation algorithm running in time O (m3 · n3 · log m), a linear kernel that can be computed in time O (m4 · n3 · log m), and a O (2O (k) + m4 · n3 · 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 F-Minor Deletion, under the assumption that at least one graph from F is planar. An important difference is that we are able to obtain a linear kernel for F-Immersion Deletion, while the exponent of the kernel of Fomin et al. for F-Minor Deletion depends heavily on the family 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 F-Immersion Deletion is quite different from that of F-Minor Deletion.

Original languageEnglish (US)
Pages (from-to)105-151
Number of pages47
JournalSIAM Journal on Discrete Mathematics
Issue number1
StatePublished - 2021


  • Edge-deletion distance
  • Graph modification problems
  • Immersions
  • Kernelization
  • Tree-cut width

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'Linear kernels for edge deletion problems to immersion-closed graph classes'. Together they form a unique fingerprint.

Cite this