Plant Propagation finds really hard NP-complete problem instances.

  • Thu 3 Jun 21

    14:00 - 15:00

  • Online


  • Event speaker

    Daan van den Berg

  • Event type

    Lectures, talks and seminars

  • Event organiser

    Mathematical Sciences, Department of

  • Contact details

    Osama Mahmoud

These Departmental Seminars are for everyone in Maths. We encourage anyone interested in the subject in general, or in the particular subject of the seminar, to come along. It's a great opportunity to meet people in the Maths Department and join in with our community.

Plant Propagation finds really hard NP-complete problem instances.

We use two evolutionary algorithms to make hard instances of the NP-complete Hamiltonian cycle problem. Hardness, or fitness, is defined as the number of recursions required by Vandegriend-Culberson, the best known exact backtracking algorithm for the problem.

The hardest instances, all non-Hamiltonian, display a high degree of regularity and scalability across graph sizes. These graphs are found multiple times through independent runs and in both algorithms, suggestion the search space might contain monotonic paths to the global maximum.

The one-bit neighbourhoods of these instances are also analysed and show that these hardest instances are separated from the easiest problem instances by just one bit of information. For Hamiltonian-bound graphs, the hardest instances are less uniform and substantially easier than their non-Hamiltonian counterparts. Reasons for these less-conclusive results are presented and discussed.


Daan van den Berg, University of Amsterdam

How to attend

If not a member of the Dept. Mathematical Science at the University of Essex, you can register your interest in attending the seminar and request the Zoom’s meeting password by emailing Dr Osama Mahmoud (o.mahmoud@essex.ac.uk)

Related events