The maximum independent union of cliques problem: complexity and exact approaches (Q2174276)

Given a simple graph \(G=(V,E)\), the maximum independent union of cliques (IUC) problem is about finding a maximum-cardinality subset \(C \subseteq V\) of vertices such that each connected component of the subgraph induced by \(C\) is a complete graph. This problem has different formulations, similarly to the connection between independent sets, vertex covers, and cliques: If \(C\) is an IUC, then \(V \setminus C\) is about a cluster vertex deletion, and this problem has been considered by \textit{F. Hüffner} et al. [Theory Comput. Syst. 47, No. 1, 196--217 (2010; Zbl 1205.68263)]. An IUC corresponds to an induced complete \(k\)-partite graph in the complement of \(G\) for some \(k\), and this is probably a more familiar setting for graph theorists. Actually, the variant where \(k\) is fixed has earlier been studied. In this paper, the complexity of the IUC problem is established for several classes of graphs. Two exact algorithms for the IUC problem are further developed, implemented, and tested experimentally. The two algorithms are based on integer programming and branch-and-bound. The branch-and-bound algorithm utilizes a Russian doll search. The application of the Russian doll search in graph algorithms has a longer history than the references indicate. For example, the reviewer's algorithm for the maximum clique problem [Discrete Appl. Math. 120, No. 1--3, 197--207 (2002; Zbl 1019.05054)] fits naturally in this framework.