Abstract
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 [19]; distance-hereditary graphs are exactly the 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.
O. Kwon is supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (ERC consolidator grant DISTRUCT, agreement No. 648527).
Access provided by CONRICYT-eBooks. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Agrawal, A., Lokshtanov, D., Misra, P., Saurabh, S., Zehavi, M.: Feedback vertex set inspired kernel for chordal vertex deletion. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16–19, pp. 1383–1398 (2017)
Bandelt, H.J., Mulder, H.M.: Distance-hereditary graphs. J. Combin. Theory Ser. B 41(2), 182–208 (1986)
Bouchet, A.: Transforming trees by successive local complementations. J. Graph Theory 12(2), 195–207 (1988)
Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125–150 (2000)
Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1–3), 77–114 (2000)
Cunningham, W.H., Edmonds, J.: A combinatorial decomposition theory. Canad. J. Math. 32(3), 734–765 (1980)
Dahlhaus, E.: Parallel algorithms for hierarchical clustering, and applications to split decomposition and parity graph recognition. Journal of Algorithms 36(2), 205–240 (2000)
Diestel, R.: Graph Theory. No. 173 in Graduate Texts in Mathematics, 3rd edn. Springer (2005)
Eiben, E., Ganian, R., Kwon, O.: A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion. In: Faliszewski, P., Muscholl, A., Niedermeier, R. (eds.) MFCS 2016, vol. 58, pp. 34:1–34:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016)
Feige, U., Hajiaghayi, M., Lee, J.R.: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput. 38(2), 629–657 (2008)
Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar F-Deletion: approximation, kernelization and optimal FPT algorithms. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science–FOCS 2012, pp. 470–479. IEEE Computer Soc., Los Alamitos (2012)
Giannopoulou, Archontia C., Jansen, Bart M.P., Lokshtanov, Daniel, Saurabh, Saket: Uniform kernelization complexity of hitting forbidden minors. In: Halldórsson, Magnús M., Iwama, Kazuo, Kobayashi, Naoki, Speckmann, Bettina (eds.) ICALP 2015. LNCS, vol. 9134, pp. 629–641. Springer, Heidelberg (2015). doi:10.1007/978-3-662-47672-7_51
Gioan, E., Paul, C.: Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs. Discrete Appl. Math. 160(6), 708–733 (2012)
Gupta, A.: Improved results for directed multicut. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2003, January 12–14, 2003, Baltimore, Maryland, USA, pp. 454–455 (2003)
Jansen, B.M.P., Pilipczuk, M.: Approximation and kernelization for chordal vertex deletion. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, January 16–19, 2017, Barcelona, Spain (2017). (to appear)
Kanté, M.M., Kim, E.J., Kwon, O., Paul, C.: An fpt algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion. Algorithmica 1–30 (2016)
Kim, E.J., Langer, A., Paul, C., Reidl, F., Rossmanith, P., Sau, I., Sikdar, S.: Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Trans. Algorithms 12(2), Art. 21, 41 (2016)
Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219–230 (1980)
Oum, S.: Rank-width and vertex-minors. J. Combin. Theory Ser. B 95(1), 79–100 (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Kim, E.J., Kwon, OJ. (2017). A Polynomial Kernel for Distance-Hereditary Vertex Deletion. In: Ellen, F., Kolokolova, A., Sack, JR. (eds) Algorithms and Data Structures. WADS 2017. Lecture Notes in Computer Science(), vol 10389. Springer, Cham. https://doi.org/10.1007/978-3-319-62127-2_43
Download citation
DOI: https://doi.org/10.1007/978-3-319-62127-2_43
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-62126-5
Online ISBN: 978-3-319-62127-2
eBook Packages: Computer ScienceComputer Science (R0)