Document Open Access Logo

Vertex Deletion Problems on Chordal Graphs

Authors Yixin Cao, Yuping Ke, Yota Otachi, Jie You

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2017.22.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Yixin Cao
Yuping Ke
Yota Otachi
Jie You

Cite As Get BibTex

Yixin Cao, Yuping Ke, Yota Otachi, and Jie You. Vertex Deletion Problems on Chordal Graphs. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2017.22

Abstract

Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study.  The celebrated result of Lewis and Yannakakis gives a complete dichotomy of their complexity.  It however has nothing to say about the case when the input graph is also special.  This paper initiates a systematic study of  vertex deletion problems from one  subclass of chordal graphs to another.  We give polynomial-time algorithms or proofs of NP-completeness for most of the problems.  In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete.

Subject Classification

Keywords
  • vertex deletion problem
  • maximum subgraph
  • chordal graph
  • (unit) interval graph
  • split graph
  • hereditary property
  • NP-complete
  • polynomial-time algori

Metrics

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

References

  1. Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Feedback vertex set inspired kernel for chordal vertex deletion. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1383-1398. SIAM, 2017. Google Scholar
  2. Claude Berge. Some classes of perfect graphs. Internat. Computation Centre, 1966. Google Scholar
  3. Alan A. Bertossi. Dominating sets for split and bipartite graphs. Information processing letters, 19(1):37-40, 1984. Google Scholar
  4. Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk, and Yngve Villanger. Largest chordal and interval subgraphs faster than 2ⁿ. In European Symposium on Algorithms, pages 193-204. Springer, 2013. Google Scholar
  5. Hans L. Bodlaender and Klaus Jansen. On the complexity of the maximum cut problem. In Annual Symposium on Theoretical Aspects of Computer Science, pages 769-780. Springer, 1994. Google Scholar
  6. Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters, 58(4):171-176, 1996. Google Scholar
  7. Yixin Cao. Linear recognition of almost interval graphs. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1096-1115. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  8. Yixin Cao. Unit interval editing is fixed-parameter tractable. Information and Computation, 253:109-126, 2017. Google Scholar
  9. Yixin Cao and Dániel Marx. Interval deletion is fixed-parameter tractable. ACM Transactions on Algorithms (TALG), 11(3):21, 2015. Google Scholar
  10. Yixin Cao and Dániel Marx. Chordal editing is fixed-parameter tractable. Algorithmica, 75(1):118-137, 2016. Google Scholar
  11. Václav Chvátal and Peter L. Hammer. Aggregation of inequalities in integer programming. Annals of discrete mathematics, 1:145-162, 1977. Google Scholar
  12. Marek Cygan and Marcin Pilipczuk. Split vertex deletion meets vertex cover: new fixed-parameter and exact exponential-time algorithms. Information Processing Letters, 113(5):179-182, 2013. Google Scholar
  13. Gabriel Andrew Dirac. On rigid circuit graphs. In Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, volume 25, pages 71-76. Springer, 1961. Google Scholar
  14. Tinaz Ekim and Dominique de Werra. On split-coloring problems. Journal of Combinatorial Optimization, 10(3):211-225, 2005. Google Scholar
  15. Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh. Exact algorithms via monotone local search. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 764-775. ACM, 2016. Google Scholar
  16. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar F-deletion: Approximation and optimal FPT algorithms. FOCS’12, pages 470-479, 2012. Google Scholar
  17. Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Large induced subgraphs via triangulations and CMSO. SIAM Journal on Computing, 44(1):54-87, 2015. Google Scholar
  18. Michael R. Garey and David S. Johnson. The rectilinear steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics, 32(4):826-834, 1977. Google Scholar
  19. Michael R. Garey and David S. Johnson. Computers and intractability: a guide to the theory of NP-completeness. WH Free. Co., San Fr, pages 90-91, 1979. Google Scholar
  20. Michael R. Garey, David S. Johnson, and Larry Stockmeyer. Some simplified NP-complete graph problems. Theoretical computer science, 1(3):237-267, 1976. Google Scholar
  21. Fănică Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM Journal on Computing, 1(2):180-187, 1972. Google Scholar
  22. Martin Charles Golumbic. Trivially perfect graphs. Discrete Mathematics, 24(1):105-107, 1978. Google Scholar
  23. Jens Gusted. On the pathwidth of chordal graphs. Discrete Applied Mathematics, 45(3):233-248, 1993. Google Scholar
  24. András Hajnal and János Surányi. Über die auflösung von graphen in vollständige teilgraphen. Ann. Univ. Sci. Budapest, Eötvös Sect. Math, 1:113-121, 1958. Google Scholar
  25. Bart M.P. Jansen and Marcin Pilipczuk. Approximation and kernelization for chordal vertex deletion. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1399-1418. SIAM, 2017. Google Scholar
  26. John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences, 20(2):219-230, 1980. Google Scholar
  27. Carsten Lund and Mihalis Yannakakis. The approximation of maximum subgraph problems. Automata, Languages and Programming, pages 40-51, 1993. Google Scholar
  28. Haiko Müller. Hamiltonian circuits in chordal bipartite graphs. Discrete Mathematics, 156(1-3):291-298, 1996. Google Scholar
  29. René Van Bevern, Christian Komusiewicz, Hannes Moser, and Rolf Niedermeier. Measuring indifference: Unit interval vertex deletion. In WG, pages 232-243. Springer, 2010. Google Scholar
  30. Mihalis Yannakakis. Computing the minimum fill-in is NP-complete. SIAM Journal on Algebraic Discrete Methods, 2(1):77-79, 1981. Google Scholar
  31. Mihalis Yannakakis. Node-deletion problems on bipartite graphs. SIAM Journal on Computing, 10(2):310-327, 1981. Google Scholar
  32. Mihalis Yannakakis and Fănică Gavril. The maximum k-colorable subgraph problem for chordal graphs. Information Processing Letters, 24(2):133-137, 1987. Google Scholar
  33. Jie You, Jianxin Wang, and Yixin Cao. Approximate association via dissociation. Discrete Applied Mathematics, 219:202-209, 2017. Google Scholar
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 About DROPS Imprint Privacy Contact