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

Original · EN

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. [FOCS 2012], 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(m³ · n³ · m); a linear kernel that can be computed in time O(m⁴ · n³ · m); and a O(2ᵒ⁽ᵏ⁾ + m⁴ · n³ · 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. [FOCS 2012], 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. [ICALP 2015]. This reveals that the kernelization complexity of F-Immersion Deletion is quite different than that of F-Minor Deletion.