LINEAR KERNELS FOR EDGE DELETION PROBLEMS TO IMMERSION-CLOSED GRAPH CLASSES.

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