Abstract
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 NPcomplete on (P_5free) chordal graphs, whereas Cluster Deletion is solved in polynomial time on split graphs. However, the existence of a polynomialtime algorithm of Cluster Deletion on interval graphs, a proper subclass of chordal graphs, remained a wellknown open problem. Our main contribution is that we settle this problem in the affirmative, by providing a polynomialtime algorithm for Cluster Deletion on interval graphs. Moreover, despite the simple formulation of the algorithm on split graphs, we show that Cluster Deletion remains NPcomplete on a natural and slight generalization of split graphs that constitutes a proper subclass of P_5free chordal graphs. Although the later result arises from the alreadyknown reduction for P_5free chordal graphs, we give an alternative proof showing an interesting connection between edgeweighted and vertexweighted variations of the problem. To complement our results, we provide faster and simpler polynomialtime algorithms for Cluster Deletion on subclasses of such a generalization of split graphs.
BibTeX  Entry
@InProceedings{konstantinidis_et_al:LIPIcs:2019:10956,
author = {Athanasios L. Konstantinidis and Charis Papadopoulos},
title = {{Cluster Deletion on Interval Graphs and Split Related Graphs}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {12:112:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771177},
ISSN = {18688969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and JoostPieter Katoen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10956},
URN = {urn:nbn:de:0030drops109568},
doi = {10.4230/LIPIcs.MFCS.2019.12},
annote = {Keywords: Cluster deletion, interval graphs, split graphs}
}
Keywords: 

Cluster deletion, interval graphs, split graphs 
Collection: 

44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) 
Issue Date: 

2019 
Date of publication: 

20.08.2019 