NP-hardness of the computation of a median equivalence relation in classification (Régnier problem)

Résumé Fr En

Étant donnée une collection de relations d’équivalence (ou partitions), le problème de Régnier consiste à déterminer une relation d’équivalence qui minimise l’éloignement par rapport à . L’éloignement est fondé sur la distance de la différence symétrique et mesure le nombre de désaccords entre  et la relation d’équivalence considérée. Une telle relation d’équivalence minimisant l’éloignement est appelée une relation d’équivalence médiane de . On montre ici la NP-difficulté du problème de Régnier, c’est-à-dire du calcul d’une relation d’équivalence médiane d’une collection de relations d’équivalence, du moins quand le nombre de relations d’équivalence de est suffisamment grand.

Given a collection of equivalence relations (or partitions), Régnier’s problem consists in computing an equivalence relation which minimizes the remoteness from . The remoteness is based on the symmetric difference distance and measures the number of disagreements between and the considered equivalence relation. Such an equivalence relation minimizing the remoteness is called a median equivalence relation of . We prove the NP-hardness of Régnier’s problem, i.e. the computation of a median equivalence relation of a collection of equivalence relations, at least when the number of equivalence relations of is large enough.