https://hal.telecom-paris.fr/hal-02286316Hudry, OlivierOlivierHudryMC2 - Mathématiques discrètes, Codage et Cryptographie - LTCI - Laboratoire Traitement et Communication de l'Information - IMT - Institut Mines-Télécom [Paris] - Télécom ParisINFRES - Département Informatique et Réseaux - Télécom ParisTechMajority graphs of profiles of equivalence relations and complexity of Régnier’s problemHAL CCSD2012Majority graphcomplexityNP-hardnesssymmetric dif- ference distancemedian relationsequivalence relationsclassicationclusteringRegnier's problem[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO][INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC][INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM][MATH.MATH-CT] Mathematics [math]/Category Theory [math.CT][MATH.MATH-RT] Mathematics [math]/Representation Theory [math.RT]HAL, TelecomParis2019-09-13 15:36:182022-01-24 08:26:292019-09-13 15:36:18enConference papers1A classic problem arising in classication consists in summarizing a collection C, called a profile, of p equivalence relations defined on a finite set X by an equivalence relation E* at minimum remoteness from C. The remoteness is based on the symmetric dierence distance and measures the total number of disagreements between E* and C, and then E* is called a median equivalence relation of C. It is usual to summarize C by its majority graph. We study the converse issue. We give asufficient condition for a graph to be the majority graph of a profile of equivalence relations. We then deduce from this that the computation of E* is NP-hard when p is large enough.