TY - GEN

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

AU - Giannopoulou, Archontia C.

AU - Pilipczuk, Michał

AU - Raymond, Jean Florent

AU - Thilikos, Dimitrios M.

AU - Wrochna, Marcin

N1 - Publisher Copyright:
© Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent, Dimitrios M. Thilikos, and Marcin Wrochna;.

PY - 2017/7/1

Y1 - 2017/7/1

N2 - Suppose F is a finite family of graphs. We consider the following meta-problem, called FImmersion Deletion: given a graph G and an 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(m3 · n3 · logm); a linear kernel that can be computed in time O(m4 · n3 · logm); and a O(2O(k) + m4 · n3 · logm)-time fixed-parameter algorithm, where n,m count the vertices and edges of the input graph. Our findings mirror those of Fomin et al. [FOCS 2012], who obtained similar 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. 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.

AB - Suppose F is a finite family of graphs. We consider the following meta-problem, called FImmersion Deletion: given a graph G and an 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(m3 · n3 · logm); a linear kernel that can be computed in time O(m4 · n3 · logm); and a O(2O(k) + m4 · n3 · logm)-time fixed-parameter algorithm, where n,m count the vertices and edges of the input graph. Our findings mirror those of Fomin et al. [FOCS 2012], who obtained similar 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. 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.

KW - Approximation

KW - Immersion

KW - Kernelization

KW - Protrusion

KW - Tree-cut width

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

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

U2 - 10.4230/LIPIcs.ICALP.2017.57

DO - 10.4230/LIPIcs.ICALP.2017.57

M3 - Conference contribution

AN - SCOPUS:85027258608

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017

A2 - Muscholl, Anca

A2 - Indyk, Piotr

A2 - Kuhn, Fabian

A2 - Chatzigiannakis, Ioannis

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017

Y2 - 10 July 2017 through 14 July 2017

ER -