A note on the complexity of the maximum edge clique partitioning problem with respect to the clique number

摘要

Given a simple and undirected graph, we consider the problem of finding a partition of the set of vertices into several cliques such that the number of edges within the cliques is maximized. This problem is referred to as the maximum edge clique partitioning problem. In this note, we show that the problem is NP-hard on graphs with clique number k, for every k ≥ 3.