Περίληψη:
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. © 2021 Archontia Giannopoulou, Michal Pilipczuk.
Συγγραφείς:
Giannopoulou, A.
Pilipczuk, M.
Raymond, J.-F.
Thilikos, D.M.
Wrochna, M.
Λέξεις-κλειδιά:
Approximation algorithms; Graph algorithms, Complexity assumptions; Constant-factor approximation algorithms; Fixed-parameter algorithms; Graph class; Input graphs; Kernelization; Linear kernel; Running-in, Graph theory
