2016/10/23 by Eun Jung Kim, Kim, Eun Jung, O‐joung Kwon +2
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems #cs.DS
paper · pdf · doi:10.48550/arxiv.1610.07229
37 pages, 6 figures; improved previous kernel size to O(k^{30} polylogk)
openalex publication_date 2016/10/23 · arxiv created 2017/02/20 · arxiv updated 2017/02/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
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 2O(k)nO(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 O(k3log 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.