Document Open Access Logo

Complexity of the Cluster Vertex Deletion Problem on H-Free Graphs

Authors Hoang-Oanh Le, Van Bang Le

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.68.pdf
  • Filesize: 0.64 MB
  • 10 pages

Document Identifiers

Author Details

Hoang-Oanh Le
  • Independent Researcher, Berlin, Germany
Van Bang Le
  • Institut für Informatik, Universität Rostock, Germany

Cite As Get BibTex

Hoang-Oanh Le and Van Bang Le. Complexity of the Cluster Vertex Deletion Problem on H-Free Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 68:1-68:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.68

Abstract

The well-known Cluster Vertex Deletion problem (cluster-vd) asks for a given graph G and an integer k whether it is possible to delete at most k vertices of G such that the resulting graph is a cluster graph (a disjoint union of cliques). We give a complete characterization of graphs H for which cluster-vd on H-free graphs is polynomially solvable and for which it is NP-complete.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Graph theory
  • Mathematics of computing → Graph algorithms
Keywords
  • Cluster vertex deletion
  • Vertex cover
  • Computational complexity
  • Complexity dichotomy

Metrics

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

References

  1. Manuel Aprile, Matthew Drescher, Samuel Fiorini, and Tony Huynh. A tight approximation algorithm for the cluster vertex deletion problem. Math. Program., 2022. URL: https://doi.org/10.1007/s10107-021-01744-w.
  2. Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, and Marcin Pilipczuk. A fast branching algorithm for cluster vertex deletion. Theory Comput. Syst., 58(2):357-376, 2016. URL: https://doi.org/10.1007/s00224-015-9631-7.
  3. Yixin Cao, Yuping Ke, Yota Otachi, and Jie You. Vertex deletion problems on chordal graphs. Theor. Comput. Sci., 745:75-86, 2018. URL: https://doi.org/10.1016/j.tcs.2018.05.039.
  4. Dibyayan Chakraborty, L. Sunil Chandran, Sajith Padinhatteeri, and Raji R. Pillai. Algorithms and complexity of s-club cluster vertex deletion. In Paola Flocchini and Lucia Moura, editors, Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings, volume 12757 of Lecture Notes in Computer Science, pages 152-164. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-79987-8_11.
  5. Maria Chudnovsky, Gérard Cornuéjols, Xinming Liu, Paul D. Seymour, and Kristina Vuskovic. Recognizing berge graphs. Combinatorica, 25(2):143-186, 2005. URL: https://doi.org/10.1007/s00493-005-0012-8.
  6. Derek G. Corneil, H. Lerchs, and L. Stewart Burlingham. Complement reducible graphs. Discret. Appl. Math., 3(3):163-174, 1981. URL: https://doi.org/10.1016/0166-218X(81)90013-5.
  7. Derek G. Corneil, Yehoshua Perl, and Lorna K. Stewart. A linear recognition algorithm for cographs. SIAM J. Comput., 14(4):926-934, 1985. URL: https://doi.org/10.1137/0214065.
  8. Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst., 33(2):125-150, 2000. URL: https://doi.org/10.1007/s002249910009.
  9. Peter Gartland and Daniel Lokshtanov. Independent set on P_k-free graphs in quasi-polynomial time. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 613-624. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00063.
  10. Petr A. Golovach, Matthew Johnson, Daniël Paulusma, and Jian Song. A survey on the computational complexity of coloring graphs with forbidden subgraphs. J. Graph Theory, 84(4):331-363, 2017. URL: https://doi.org/10.1002/jgt.22028.
  11. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, 1988. URL: https://doi.org/10.1007/978-3-642-97881-4.
  12. Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, and Michal Pilipczuk. Polynomial-time algorithm for maximum weight independent set on P₆-free graphs. ACM Trans. Algorithms, 18(1):4:1-4:57, 2022. URL: https://doi.org/10.1145/3414473.
  13. Sun-Yuan Hsieh, Hoàng-Oanh Le, Van Bang Le, and Sheng-Lung Peng. On the d-claw vertex deletion problem. CoRR, abs/2203.06766, 2022. URL: https://doi.org/10.48550/arXiv.2203.06766.
  14. 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: https://doi.org/10.1007/s00224-008-9150-x.
  15. Daniel Král, Jan Kratochvíl, Zsolt Tuza, and Gerhard J. Woeginger. Complexity of coloring graphs without forbidden induced subgraphs. In Andreas Brandstädt and Van Bang Le, editors, Graph-Theoretic Concepts in Computer Science, 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14-16, 2001, Proceedings, volume 2204 of Lecture Notes in Computer Science, pages 254-262. Springer, 2001. URL: https://doi.org/10.1007/3-540-45477-2_23.
  16. John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci., 20(2):219-230, 1980. URL: https://doi.org/10.1016/0022-0000(80)90060-4.
  17. Owen J. Murphy. Computing independent sets in graphs with large girth. Discret. Appl. Math., 35(2):167-170, 1992. URL: https://doi.org/10.1016/0166-218X(92)90041-8.
  18. Ignasi Sau and Uéverton dos Santos Souza. Hitting forbidden induced subgraphs on bounded treewidth graphs. Inf. Comput., 281:104812, 2021. URL: https://doi.org/10.1016/j.ic.2021.104812.
  19. Dekel Tsur. Faster parameterized algorithm for cluster vertex deletion. Theory Comput. Syst., 65(2):323-343, 2021. URL: https://doi.org/10.1007/s00224-020-10005-w.
  20. Mihalis Yannakakis. Node- and edge-deletion np-complete problems. In Richard J. Lipton, Walter A. Burkhard, Walter J. Savitch, Emily P. Friedman, and Alfred V. Aho, editors, Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pages 253-264. ACM, 1978. URL: https://doi.org/10.1145/800133.804355.
  21. Mihalis Yannakakis. Node-deletion problems on bipartite graphs. SIAM J. Comput., 10(2):310-327, 1981. URL: https://doi.org/10.1137/0210022.
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