Alain Gély

Recherche : Travaux de th�se

Th�se

Sujet de th�se :
Algorithmique combinatoire : Cliques, Bicliques et Syst�me d'implications

Th�se soutenue le 8 d�cembre 2005, sous la direction du professeur Lhouari Nourine, devant le jury suivant :

Pr. Lhouari Nourine, Directeur de th�se
Pr. Michel Habib, Rapporteur
Pr. Bernard Monjardet, Rapporteur
Pr. Michel Chein, Examinateur
Pr. Bernhard Ganter, Examinateur
Pr. Alain Quilliot, Examinateur, Pr�sident du Jury
Dr. Raoul Medina, Examinateur invit�
Pr. Michel Morvan, Examinateur invit�

Résumé des travaux de th�se

Mes travaux s'articulent autour de l'algorithmique d'�num�ration, consistant � lister tous les objets obtenus � partir d'une structure discr�te (typiquement, un graphe) et poss�dant une propri�t� particuli�re (par exemple, �tre une clique maximale, une biclique maximale, ...)

Mes travaux de th�se se sont d�coup�s en trois grandes parties :

La premi�re partie traite du probl�me de l'�num�ration des cliques maximales d'un graphe. A cette occasion, nous donnons une vision unifi�e des algorithmes existants sur le sujet en pr�sentant une nouvelle structure : H(G), le graphe de transition des cliques maximales d'un graphe G.

La deuxi�me partie traite des probl�mes d'�num�ration des bicliques maximales d'un graphe. Apr�s une �tude bibliographique de trois probl�mes d'�num�ration de bicliques maximales (bicliques maximales induites d'un graphe, bicliques maximales non induites d'un graphe et bicliques maximales induites d'un graphe biparti), nous nous int�ressons particuli�rement au dernier de ces trois probl�mes.

En effet, le probl�me de l'�num�ration des bicliques maximales d'un graphe biparti a des applications dans plusieurs grands domaines de l'informatique, comme le datamining (recherche des motifs ferm�s fr�quents), l'analyse de concept formel (construction du treillis des concepts), les math�matiques discr�tes (recherche des pav�s maximum de 1 dans une matrice bool�enne). Pour chacune de ces applications, des algorithmes ont �t�s d�velopp�s pour r�soudre ce probl�me.
Nous �tudions les propri�t�s du graphe de transition dans ce cas pr�cis, apr�s transformation du probl�me permettant de se ramener � un probl�me d'�num�ration de cliques. Encore une fois, cette m�thode nous permet de donner une vision unifi�e d'algorithmes existants, d�velopp�s dans les divers domaines pr�sent�s ci-dessus.

L'ensemble des bicliques maximales d'un graphe biparti est en bijection avec deux syst�mes de fermeture. Un graphe biparti est donc une repr�sentation d'un syst�me de fermeture. Une autre repr�sentation, les bases d'implications, est utilis�e dans de nombreux domaines.
En effet, le probl�me de l'�num�ration des implications d'une base minimum � partir d'une autre repr�sentation d'un syst�me de fermeture (les �l�ments inf-irr�ductibles) est �quivalent � de nombreux autres probl�mes dans de nombreux champs applicatifs (datamining avec la recherche des cl�s dans une base de donn�es. Th�orie des graphes avec la recherche des transversaux minimaux d'un hypergraphe. Logique avec le passage d'une fonction bool�enne monotone de la CNF � la DNF). A l'heure actuelle, il n'existe pas d'algorithme polynomial (par implication) d'�num�ration des implications d'une base minimum. D'autre part la taille d'une base minimum peut �tre exponentielle en la taille de la famille des �l�ments inf-irr�ductibles d'un syst�me de fermeture. Dans cette th�se, nous proposons deux approches permettant de r�duire la combinatoire associ�e au probl�me : Les �l�ments clones sont des �l�ments jouant un r�le sym�trique (similaire) dans une base minimum. Il s'en suit qu'en ne gardant qu'un seul �l�ment de chaque classe de clones ainsi que les informations sur les classes d'�quivalences, on peut r�duire fortement la taille d'une base minimum. L'exemple exponentiel de Mannila et R�ih� (1992) se r�duit � une seule implication apr�s traitement des �l�ments clones.

Malheureusement, on ne sait pour l'instant d�tecter qu'un sous ensemble des �l�ments clones d'une base minimum � partir des �l�ments inf-irr�ductibles d'un syst�me de fermeture. Il est en effet possible que la sym�trie de deux �l�ments dans une base minimum soit bris�e dans le syst�me de fermeture � cause d'implications particuli�res : Les implications unitaires (poss�dant un singleton pour pr�misse). Or, ces implications sont en nombre polynomial et faciles � calculer. La deuxi�me approche permettant de r�duire la combinatoire associ�e au probl�me est bas� sur la manipulation de l'ensemble des implications unitaires. Puisque ces derni�res emp�chent la sym�trie entre deux �l�ments, nous nous int�ressons aux conditions n�cessaires et suffisantes permettant de rajouter ou d'enlever de telles implications sans modifier les implications non unitaires. Nous avons notamment caract�ris�, � partir de la famille des �l�ments inf-irr�ductibles, dans quels cas une implication unitaire peut �tre ajout�e � la base de telle fa�on que le nouveau syst�me de fermeture obtenu soit en relation de couverture avec le syst�me de fermeture de d�part dans la famille des syst�mes de fermeture partageant les m�mes implications non unitaires. Nous avons aussi montr� comment obtenir la famille d'�l�ments inf-irr�ductibles correspondante. Le cardinal de celle-ci est plus petit ou �gal au cardinal de la famille d'�l�ments inf-irr�ductibles de d�part. Nous en d�duisons un algorithme permettant de calculer la famille des �l�ments inf-irr�ductibles d'un syst�me de fermeture minimal poss�dant les m�mes implications non unitaires, r�duisant ainsi les donn�es d'entr�es du probl�me (les �l�ments inf-irr�ductibles) ainsi que certaines donn�es g�n�ralement utilis�es comme interm�diaire (le syst�me de fermeture)