Sites Inria

English version

Challenge FHCP

Anne Schneider - 29/11/2016

Quand les chercheurs jouent pour résoudre le challenge des 1001 graphes

Le challenge proposé par l’université Flinders d’Adelaïde (Australie) aux chercheurs du monde entier consistait à résoudre 1001 instances du problème du cycle hamiltonien.

C’est un duo composé de Nathann Cohen, chercheur CNRS au LRI à Paris XI, et de David Coudert, Directeur de recherche Inria et responsable de l’équipe-projet COATI, commune au centre Inria de Sophia Antipolis – Méditerranée et au laboratoire I3S (CNRS, UNS), qui l’ont remporté. 

Ils sont arrivés à en résoudre 985 et ont remporté le grand prix remis le 1er décembre 2016 avec un mode de résolution pour le moins original.

Le problème du cycle hamiltonien est un problème classique en théorie des graphes, réputé très difficile à résoudre. Il est également connu sous le nom de problème du “voyageur de commerce », qui doit honorer de nombreux rendez-vous dans des villes éloignées sans jamais retourner sur ses pas.

Cycle hamiltonien

L’équipe du Flinders Hamiltonian Cycle Project (FHCP) a donc lancé un défi à tous les chercheurs du domaine en leur proposant de résoudre 1001 instances et récompensant le chercheur ou l’équipe de chercheurs qui parviendrait à trouver une solution pour tous les graphes proposés dans le délai du concours (un an). Douze équipes ont finalement envoyé des résultats complets mais chaque équipe n'est parvenue à résoudre en moyenne que 338 instances. L'équipe arrivée en deuxième position a trouvé 614 cycles. Aucune équipe n'a trouvé à ce jour de solution pour les seize graphes non élucidés par les lauréats.

Recherche opérationnelle et décomposition progressive

Nathann Cohen et David Coudert se sont attaqués à ce challenge comme à un jeu. Plutôt que d’utiliser des logiciels dédiés ou développer et tester de longs algorithmes, ils ont préféré le résoudre comme un casse-tête : après une première classification par caractéristiques principales (nombre de sommets, diamètre, degrés minimum et maximum),  ils ont analysé les différents graphes un par un pour en identifier visuellement le type, les classer par « famille » et imaginer la bonne approche de résolution. Certains graphes ayant jusqu’à 10 000 sommets, ils ont cherché à réduire la taille des instances en combinant des méthodes de séparation, substitution, élimination, réduction, etc. et ont ensuite traité les graphes d’une même famille de façon identique, à l’aide de logiciels différents de ceux utilisés habituellement pour ce type de problème, donc non spécifiques à cette problématique.

La résolution s’est ensuite poursuivie famille par famille jusqu’à permettre la résolution de 985 graphes sur les 1001 proposés par l’université Flinders ! D’une certaine façon ce prix récompense un savoir-faire très opérationnel et intuitif plutôt qu’une approche exhaustive fondée sur la puissance de calcul.

Mots-clés : Cycle hamiltonien Université Flinders Centre de recherche Inria - Sophia Antipolis - Méditerranée Graphes COATI

Haut de page

Suivez Inria tout au long de son 50e anniversaire et au-delà !