Giannopoulou, Archontia C. ;
Pilipczuk, Michal ;
Raymond, JeanFlorent ;
Thilikos, Dimitrios M. ;
Wrochna, Marcin
Linear Kernels for Edge Deletion Problems to ImmersionClosed Graph Classes
Abstract
Suppose F is a finite family of graphs. We consider the following metaproblem, 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 FMinor 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 FImmersion Deletion problem admits:
 a constantfactor approximation algorithm running in time O(m^3 n^3 log m)
 a linear kernel that can be computed in time O(m^4 n^3 log m) and
 a O(2^{O(k)} + m^4 n^3 log m)time fixedparameter 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 FMinor 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 FImmersion 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 FImmersion Deletion is quite different than that of FMinor Deletion.
BibTeX  Entry
@InProceedings{giannopoulou_et_al:LIPIcs:2017:7389,
author = {Archontia C. Giannopoulou and Michal Pilipczuk and JeanFlorent Raymond and Dimitrios M. Thilikos and Marcin Wrochna},
title = {{Linear Kernels for Edge Deletion Problems to ImmersionClosed Graph Classes}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {57:157:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7389},
URN = {urn:nbn:de:0030drops73891},
doi = {10.4230/LIPIcs.ICALP.2017.57},
annote = {Keywords: Kernelization, Approximation, Immersion, Protrusion, Treecut width}
}
07.07.2017
Keywords: 

Kernelization, Approximation, Immersion, Protrusion, Treecut width 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

07.07.2017 