Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: A Polynomial Kernel for Distance-Hereditary Vertex Deletion   A graph is distance-hereditary if for any pair of vertices, their distance in
every connected induced subgraph containing both vertices is the same as their
distance in the original graph. The Distance-Hereditary Vertex Deletion problem
asks, given a graph $G$ on $n$ vertices and an integer $k$, whether there is a
set $S$ of at most $k$ vertices in $G$ such that $G-S$ is distance-hereditary.
This problem is important due to its connection to the graph parameter
rank-width that distance-hereditary graphs are exactly graphs of rank-width at
most $1$. Eiben, Ganian, and Kwon (MFCS' 16) proved that Distance-Hereditary
Vertex Deletion can be solved in time $2^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$,
and asked whether it admits a polynomial kernelization. We show that this
problem admits a polynomial kernel, answering this question positively. For
this, we use a similar idea for obtaining an approximate solution for Chordal
Vertex Deletion due to Jansen and Pilipczuk (SODA' 17) to obtain an approximate
solution with $\mathcal{O}(k^3\log n)$ vertices when the problem is a
YES-instance, and we exploit the structure of split decompositions of
distance-hereditary graphs to reduce the total size.

3
The categories of this paper are: physics
28
The categories of this paper are: alg-geom
13
The categories of this paper are: quant-ph
14
The categories of this paper are: math-ph
10
The categories of this paper are: q-bio
31
The categories of this paper are: ao-sci
7
The categories of this paper are: hep-th
32
The categories of this paper are: atom-ph
15
The categories of this paper are: nucl-ex
20
The categories of this paper are: acc-phys
26
The categories of this paper are: bayes-an
0
The categories of this paper are: hep-ph
25
The categories of this paper are: patt-sol
9
The categories of this paper are: nlin
35
The categories of this paper are: mtrl-th
37
The categories of this paper are: supr-con