The Travelling Salesman Problem (TSP) has baffled mathematicians for more than 50 years. But two of our young professors, Daniela Kühn and Deryk Osthus, have made a major step towards it: they have ‘half-solved’ it. In the field of Extremal Combinatorics, that is no mean feat.
The question asked by the TSP is this: If you have a group of cities at various distances from each other, what is the shortest possible route a travelling salesman could take so he visited each city only once and returned to where he started? What makes the TSP such a poser is that the number of solutions is so vast that there’s no efficient algorithm – in particular, it is well beyond the capacity of current computers to solve.
But Daniela and Deryk – who are acknowledged as world leaders in their field – have come closer than anyone has come before: imagine ranking all possible routes in a list according to their length. So the aim is to find a solution near the top of the list. Daniela and Deryk were able to come up with an algorithm which returns a route that is definitely in the top half of the list – a vast improvement over any previous results.
Surprisingly, this breakthrough came via their solution of a famous conjecture on Hamilton cycles in graphs – made by the mathematician PJ Kelly: the connection between the two was not obvious and was, therefore, unexpected. In graph theory, the vertices or nodes represent cities and the edges between them represent possible routes the salesman could take.
Daniela and Deryk’s proof spans almost 90 pages and has also led to the solution of other notorious problems that have been open for decades and resistant to attack.
Although graphs are an abstract concept, they can be applied to many real-life situations, such as modelling social networks (the vertices of a graph representing people and the edges between them representing mutual acquaintances), as well as networks and structures in biology, communications, computer science and genetics. For example, applying graph theory to the internet enables you to see how resilient the network is to attack or component failure.
To fund their ongoing research, Daniela and Deryk have each been awarded European Research Council Starting Grants totalling 1.6 million euros. So far, only 16 such grants have been awarded to mathematicians in the UK, and only seven to combinatorialists in Europe.
Along with collaborators from Birmingham, Daniela and Deryk have also applied their methods to solve other classic mathematical problems: for example edge-colourings of graphs (which can be applied to real-life situations such as school timetables and other scheduling problems) and matching problems (which can be used to decide which teams of colleagues will work best together).