Optimal clustering of multipartite graphs

Given a graph G = (X, U), the problem dealt within this paper consists in partitioning X into a disjoint union of cliques by adding or removing a minimum number z (G) of edges (Zahn's problem). While the computation of z (G) is NP-hard in general, we show that its computation can be done in polynomial time when G is bipartite, by relating it to a maximum matching problem. When G is a complete multipartite graph, we give an explicit formula specifying z (G) with respect to some structural features of G. In both cases, we give also the structure of all the optimal clusterings of G.