Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Preprocessing for Outerplanar Vertex Deletion: An Elementary Kernel of
  Quartic Size   In the $\mathcal{F}$-Minor-Free Deletion problem one is given an undirected
graph $G$, an integer $k$, and the task is to determine whether there exists a
vertex set $S$ of size at most $k$, so that $G-S$ contains no graph from the
finite family $\mathcal{F}$ as a minor. It is known that whenever $\mathcal{F}$
contains at least one planar graph, then $\mathcal{F}$-Minor-Free Deletion
admits a polynomial kernel, that is, there is a polynomial-time algorithm that
outputs an equivalent instance of size $k^{\mathcal{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
$k$ vertices from a graph to make it outerplanar. This is a special case of
$\mathcal{F}$-Minor-Free Deletion for the family $\mathcal{F} = \{K_4,
K_{2,3}\}$. The class of outerplanar graphs is arguably the simplest class of
graphs for which no explicit kernelization size bounds are known. By exploiting
the combinatorial properties of outerplanar graphs we present elementary
reduction rules decreasing the size of a graph. This yields a constructive
kernel with $\mathcal{O}(k^4)$ vertices and edges. As a corollary, we derive
that any minor-minimal obstruction to having an outerplanar deletion set of
size $k$ has $\mathcal{O}(k^4)$ vertices and edges.

5
The categories of this paper are: gr-qc
2
The categories of this paper are: math
37
The categories of this paper are: supr-con
34
The categories of this paper are: chem-ph
21
The categories of this paper are: adap-org
15
The categories of this paper are: nucl-ex
19
The categories of this paper are: eess
22
The categories of this paper are: chao-dyn
13
The categories of this paper are: quant-ph
24
The categories of this paper are: dg-ga
11
The categories of this paper are: hep-lat
26
The categories of this paper are: bayes-an
12
The categories of this paper are: nucl-th
4
The categories of this paper are: cond-mat
20
The categories of this paper are: acc-phys
29
The categories of this paper are: funct-an