A polynomial-time algorithm for cluster deletion on (diamond, Butterfly)-free graphs

Abstract

The cluster deletion (CD) problem consists of transforming an input graph into a disjoint union of cliques by removing as few edges as possible. For general graphs, this is a combinatorial optimization problem that belongs to the NP-hard computational complexity class. In the present paper, we identify a new polynomially solvable CD subproblem. Specifically, we propose a two-phase polynomial algorithm that solves CD on (butterfly, diamond)-free graphs.