The Travelling Salesman Problem (TSP) has baffled mathematicians for more than 50 years, yet two of our young professors, Daniela Kühn and Deryk Osthus have made a big step towards a solution by ‘half-solving’ it. And in the field of Extremal Combinatorics, that is no mean feat.
The question posed 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 an intellectual challenge is that the number of solutions is so vast that there’s no efficient algorithm – 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 before. They devised an algorithm to map a route that was in the top half of the list of all possible routes (ranked according to their length) – 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 in 1968: the connection between the two is 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 notoriously difficult-to-solve problems.
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. They have also been invited to present their findings at the International Congress of Mathematicians in Seoul in 2014, one of the highest accolades a Mathematician can receive.
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).