2026-08-08T06:28:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10956 2024-03-06T10:46:54Z ddc:004 open_access

Cluster Deletion on Interval Graphs and Split Related Graphs Konstantinidis, Athanasios L. Papadopoulos, Charis Cluster deletion interval graphs split graphs In the Cluster Deletion problem the goal is to remove the minimum number of edges of a given graph, such that every connected component of the resulting graph constitutes a clique. It is known that the decision version of Cluster Deletion is NP-complete on (P_5-free) chordal graphs, whereas Cluster Deletion is solved in polynomial time on split graphs. However, the existence of a polynomial-time algorithm of Cluster Deletion on interval graphs, a proper subclass of chordal graphs, remained a well-known open problem. Our main contribution is that we settle this problem in the affirmative, by providing a polynomial-time algorithm for Cluster Deletion on interval graphs. Moreover, despite the simple formulation of the algorithm on split graphs, we show that Cluster Deletion remains NP-complete on a natural and slight generalization of split graphs that constitutes a proper subclass of P_5-free chordal graphs. Although the later result arises from the already-known reduction for P_5-free chordal graphs, we give an alternative proof showing an interesting connection between edge-weighted and vertex-weighted variations of the problem. To complement our results, we provide faster and simpler polynomial-time algorithms for Cluster Deletion on subclasses of such a generalization of split graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Athanasios L. Konstantinidis and Charis Papadopoulos 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.12 urn:nbn:de:0030-drops-109568 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.12 eng https://creativecommons.org/licenses/by/3.0/legalcode