Document Open Access Logo

A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion

Authors Eduard Eiben, Robert Ganian, O-joung Kwon

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.34.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Eduard Eiben
Robert Ganian
O-joung Kwon

Cite AsGet BibTex

Eduard Eiben, Robert Ganian, and O-joung Kwon. A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.34

Abstract

Vertex deletion problems ask whether it is possible to delete at most k vertices from a graph so that the resulting graph belongs to a specified graph class. Over the past years, the parameterized complexity of vertex deletion to a plethora of graph classes has been systematically researched. Here we present the first single-exponential fixed-parameter algorithm for vertex deletion to distance-hereditary graphs, a well-studied graph class which is particularly important in the context of vertex deletion due to its connection to the graph parameter rank-width. We complement our result with matching asymptotic lower bounds based on the exponential time hypothesis.
Keywords
  • distance-hereditary graphs
  • fixed-parameter algorithms
  • rank-width

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Isolde Adler, Mamadou Moustapha Kanté, and O-joung Kwon. Linear rank-width of distance-hereditary graphs. In Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers, pages 42-55, 2014. URL: http://dx.doi.org/10.1007/978-3-319-12340-0_4.
  2. Akanksha Agrawal, Sudeshna Kolay, Daniel Lokshtanov, and Saket Saurabh. A faster FPT algorithm and a smaller kernel for block graph vertex deletion. In LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings, pages 1-13, 2016. Google Scholar
  3. Hans-Jürgen Bandelt and Henry M. Mulder. Distance-hereditary graphs. J. Combin. Theory Ser. B, 41(2):182-208, 1986. URL: http://dx.doi.org/10.1016/0095-8956(86)90043-2.
  4. André Bouchet. Transforming trees by successive local complementations. J. Graph Theory, 12(2):195-207, 1988. Google Scholar
  5. Liming Cai and David Juedes. On the existence of subexponential parameterized algorithms. Journal of Computer and System Sciences, 67(4):789 - 807, 2003. URL: http://dx.doi.org/10.1016/S0022-0000(03)00074-6.
  6. Serafino Cicerone and Gabriele Di Stefano. On the extension of bipartite to parity graphs. Discrete Applied Mathematics, 95(1-3):181-195, 1999. URL: http://dx.doi.org/10.1016/S0166-218X(99)00074-8.
  7. William H. Cunningham. Decomposition of directed graphs. SIAM J. Algebraic Discrete Methods, 3(2):214-228, 1982. Google Scholar
  8. William H. Cunningham and Jack Edmonds. A combinatorial decomposition theory. Canad. J. Math., 32(3):734-765, 1980. URL: http://dx.doi.org/10.4153/CJM-1980-057-7.
  9. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  10. Elias Dahlhaus. Parallel algorithms for hierarchical clustering, and applications to split decomposition and parity graph recognition. Journal of Algorithms, 36(2):205-240, 2000. URL: http://dx.doi.org/10.1006/jagm.2000.1090.
  11. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  12. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar f-deletion: Approximation, kernelization and optimal FPT algorithms. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 470-479, 2012. Google Scholar
  13. Csaba P. Gabor, Kenneth J. Supowit, and Wen Lian Hsu. Recognizing circle graphs in polynomial time. J. Assoc. Comput. Mach., 36(3):435-473, 1989. Google Scholar
  14. Emeric Gioan and Christophe Paul. Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs. Discrete Appl. Math., 160(6):708-733, 2012. URL: http://dx.doi.org/10.1016/j.dam.2011.05.007.
  15. Peter L. Hammer and Frédéric Maffray. Completely separable graphs. Discrete Applied Mathematics, 27(1-2):85-99, 1990. URL: http://dx.doi.org/10.1016/0166-218X(90)90131-U.
  16. Pinar Heggernes, Pim van ’t Hof, Bart M.P. Jansen, Stefan Kratsch, and Yngve Villanger. Parameterized complexity of vertex deletion into perfect graph classes. Theoretical Computer Science, 511:172 - 180, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2012.03.013.
  17. E. Howorka. A characterization of distance-hereditary graphs. In The Quarterly Journal of Mathematics, Oxford, Second Series, 28 (112):417-420, 1977. Google Scholar
  18. Falk Hüffner, Christian Komusiewicz, Hannes Moser, and Rolf Niedermeier. Fixed-parameter algorithms for cluster vertex deletion. Theory Comput. Syst., 47(1):196-217, 2010. URL: http://dx.doi.org/10.1007/s00224-008-9150-x.
  19. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512 - 530, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1774.
  20. Mamadou Moustapha Kanté, Eun Jung Kim, O-joung Kwon, and Christophe Paul. An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion. In Thore Husfeldt and Iyad Kanj, editors, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), volume 43 of Leibniz International Proceedings in Informatics (LIPIcs), pages 138-150, Dagstuhl, Germany, 2015. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.138.
  21. Eun Jung Kim and O-joung Kwon. A Polynomial Kernel for Block Graph Deletion. In Thore Husfeldt and Iyad Kanj, editors, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), volume 43 of Leibniz International Proceedings in Informatics (LIPIcs), pages 270-281, Dagstuhl, Germany, 2015. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.270.
  22. Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, pages 613-624, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39206-1_52.
  23. Sang-il Oum. Rank-width and vertex-minors. J. Comb. Theory, Ser. B, 95(1):79-100, 2005. URL: http://dx.doi.org/10.1016/j.jctb.2005.03.003,
  24. Sang-il Oum. Rank-width and well-quasi-ordering. SIAM J. Discrete Math., 22(2):666-682, 2008. URL: http://dx.doi.org/10.1137/050629616.
  25. Bruce Reed, Kaleigh Smith, and Adrian Vetta. Finding odd cycle transversals. Operations Research Letters, 32(4):299 - 301, 2004. URL: http://dx.doi.org/10.1016/j.orl.2003.10.009.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact