English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In the {\sc 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 {\sc Cluster Deletion} is NP-complete on ($P_5$-free) chordal graphs, whereas {\sc Cluster Deletion} is solved in polynomial time on split graphs. However, the existence of a polynomial-time algorithm of {\sc 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 {\sc Cluster Deletion} on interval graphs. Moreover, despite the simple formulation of the algorithm on split graphs, we show that {\sc 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. To complement our results, we provide two polynomial-time algorithms for {\sc Cluster Deletion} on subclasses of such generalizations of split graphs.

Cluster Deletion on Interval Graphs and Split Related Graphs