TY - JOUR

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

AU - Giannopoulou, Archontia

AU - Pilipczuk, Michal

AU - Raymond, Jean Florent

AU - Thilikos, Dimitrios M.

AU - Wrochna, Marcin

N1 - Publisher Copyright:
© 2021 Archontia Giannopoulou, Michal Pilipczuk.

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Edge-deletion distance

KW - Graph modification problems

KW - Immersions

KW - Kernelization

KW - Tree-cut width

UR - http://www.scopus.com/inward/record.url?scp=85101201313&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85101201313&partnerID=8YFLogxK

U2 - 10.1137/18M1228839

DO - 10.1137/18M1228839

M3 - Article

AN - SCOPUS:85101201313

SN - 0895-4801

VL - 35

SP - 105

EP - 151

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -