Majority graphs of profiles of equivalence relations and complexity of Régnier’s problem

Olivier Hudry 1, 2
Abstract :

A 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 a sufficient 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.

Complete list of metadatas

https://hal.telecom-paristech.fr/hal-02286316
Contributor : Telecomparis Hal <>
Submitted on : Friday, September 13, 2019 - 3:36:18 PM
Last modification on : Thursday, October 17, 2019 - 12:37:00 PM

Identifiers

  • HAL Id : hal-02286316, version 1

Collections

Citation

Olivier Hudry. Majority graphs of profiles of equivalence relations and complexity of Régnier’s problem. 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012), May 2012, Munich, Germany. pp.147-150. ⟨hal-02286316⟩

Share

Metrics

Record views

6