Seminar by David Coudert (Inria)

Speaker: David Coudert (Inria)                                                                                                           

Title: On the Flinders Hamiltonian Cycle Project Challenge

Date: Thursday, July 25th, 2019

Time: 11:00 am

Room:  EV3.309

ABSTRACT

On September 30, 2015, the Graph Theory research group at Flinders University in Adelaide, Australia, launched an open competition called the Flinders Hamiltonian Cycle Project (FHCP) Challenge. It provided 1001 large graphs (up to 9528 vertices) and asked participants to find, in each of these graphs, a Hamiltonian Cycle, i.e. a cycle passing through the edges of this graph and visiting all its vertices once and only once. This is a classic problem in graph theory, considered very difficult to solve (NP-Complete). It is the decision version of the famous traveling salesman problem (TSP), a NP-hard optimization problem.

To win this challenge, one had to be the first team to find a solution for all the graphs proposed within the competition deadline (1 year). The objective of the organizers was to make a "state of the art" of known methods and to measure their effectiveness in practice. The competition was also intended to identify the really difficult graphs, i.e. those that no one could solve.

In this talk, we will presents the various methods of graph exploration, decomposition and optimization that the team of Nathann Cohen and David Coudert used to win this challenge by solving 985 instances.

BIO

David Coudert is currently the scientific leader of COATI, a joint project-team between the research center of Inria Sophia Antipolis - Méditerranée and the I3S laboratory which itself belongs to the CNRS and the University Nice - Sophia Antipolis (UNS). Dr. Coudert received a Master degree in Computer Science from ENS Lyon and UCBL in 1997, a PhD in Computer Science from UNS in 2001, and the Habilitation à Diriger des Recherches in 2010. He did a post-doc in 2002 at Universitat Polytècnica de Catalunya (UPC), DMA4, Barcelona, Spain. In September 2002, he became Chargé de Recherche at Inria Sophia Antipolis. Dr. Coudert was a member of the joint project-team Mascotte between INRIA and the I3S laboratory(CNRS/UNS) till December 2012. He was team vice-leader of Mascotte from July 2006 till March 2011, and then the scientific leader of the team till December 2012. In January 2013, Dr. Coudert started the new joint project-team COATI. In 2016, Dr. Coudert has been promoted Research Director.