Optimal clique-partitions of multipartitions of multipartite graphs

Irène Charon*, ENST
Olivier Hudry*, ENST et CERMSEM

Résumé. Etant donné un graphe G = (X, U), le problème abordé dans cet article consiste à partitionner X en une union disjointe de cliques obtenue par l'ajout ou la suppression d'un nombre minimum z(G) d'arêtes (problème de Zahn). Alors que la détermination de z(G) est un problème NP-difficile dans le cas général, on montre que son calcul peut être réalisé en temps polynomial quand G est biparti, en liant ce problème à la recherche d'un couplage maximum dans G. Quand G est un graphe multiparti complet, on donne une formule explicite de la valeur de z(G) en fonction de paramètres caractérisant G. Dans les deux cas, on précise aussi la structure de toutes les solutions optimales admises par G.
Mots clés : Théorie des graphes, partitionnement en cliques, problème de Zahn, indice de Zahn, approximation de relations symétriques par des relations d'équivalence, complexité, couplage.

Abstract. Given a graph G = (X, U), the problem dealt with in 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 clique-partitionings of G.
Keywords : Graph theory, clique-partitioning, Zahn's problem, Zahn index, approximation of symmetric relations by equivalence relations, clustering, complexity, matching.

AMS Classification : 05C, 05C69, 05C99.

*Ecole Nationale Supérieure des Télécommunications, 46 rue Barrault, 75634 Paris cedex 13.