Preprocessing for Outerplanar Vertex Deletion: An Elementary Kernel of Quartic Size
Huib Donkers, Bart M. P. Jansen, Michał Włodarczyk · Algorithmica · 2022
Abstract In the $${\varvec{\mathcal {F}}}$$ F - Minor - Free Deletion problem one is given an undirected graph $${\varvec{G}}$$ G , an integer $${\varvec{k}}$$ k , and the task is to determine whether there exists a vertex set $${\varvec{S}}$$ S of size at most $${\varvec{k}}$$ k , so that $${\varvec{G}}-{\varvec{S}}$$ G - S contains no graph from the finite family $${\varvec{\mathcal {F}}}$$ F as a minor. It is known that whenever $${\varvec{\mathcal {F}}}$$ F contains at least one planar graph, then $${\varvec{\mathcal {F}}}$$ F - Minor - Free Deletion admits a polynomial kernel, that is, there is a polynomial-time algorithm that outputs an equivalent instance of size $${\varvec{k}}^{{\varvec{\mathcal {O}}}{} {\textbf {(1)}}}$$ k O ( 1 ) [Fomin, Lokshtanov, Misra, Saurabh; FOCS 2012]. However, this result relies on non-constructive arguments based on well-quasi-ordering and does not provide a concrete bound on the kernel size. We study the Outerplanar Deletion problem, in which we want to remove at most $${\varvec{k}}$$ k vertices from a graph to make it outerplanar. This is a special case of $${\varvec{\mathcal {F}}}$$ F - Minor - Free Deletion for the family $${\varvec{\mathcal {F}}} = \{{\varvec{K}}_{{\textbf {4}}}, {\varvec{K}}_{{{\textbf {2,3}}}}\}$$ F = { K 4 , K 2 , 3 } . The class of outerplanar graphs is arguably the simplest class of graphs