Making Sense of the Very Complex

From Mathsreach

Catherine McCartin uses parameterised complexity to solve problems like finding the best route for a travelling salesman and constructing evolutionary trees. Read about the sorts of real world problems that can now able to be solved using these new techniques.

• View article: Making Sense of the Very Complex

A travelling salesperson sets out on a trip around the country. Given a number of cities, and the costs of travelling, what is the cheapest round trip she can take to visit each city only once, and then return home? The most direct way for her to answer this question would be to try all the different combinations, and see which one is the cheapest. However, even with just a few different cities, there are many combinations that could be tried, and the more there are, the more complicated the problem becomes. Instead, computational techniques that somehow restrict the problem are needed, to produce a useful solution within a practical time frame.

There are many real-world problems that are similar to this, and a variety of different computational techniques have been developed to find practical ways to solve them. One of the newest ones is known as parameterised complexity, and it is in this area that Dr Catherine McCartin, a Senior Lecturer in Computer Science at Massey University, carries out her research. “Parameterised complexity techniques for designing algorithms for this kind of problem have given us efficient ways of producing exact solutions to real-world problems that we would previously have had to approximate,” she said. “Parameterised complexity also gives us the chance to view a problem from several different perspectives.”

Parameterised complexity is based on the simple observation that many real-world problems have certain aspects of their input that vary only within a moderate range, at least for instances that are of practical importance. By exploiting such small parameters, many problems can be efficiently solved. There are often several different ways to ‘parameterise’ a problem.

Parameterised complexity has applications in many different areas, and McCartin works on both the theory and its uses. One application involves developing methods to help construct evolutionary trees. Often, she explained, “you have several phylogenetic trees from the same group of organisms – they might come from different gene markers. But you want to find the true model that reflects evolutionary history.” The problem, however, is finding out what that is, and it is here that parameterized complexity methods can help.

“Parameterised complexity ideas are applied in all kinds of places. Computational biology is a major one, because it is a newish area and lots of things are happening there, and a lot of their problems seem to fit with the parameterised view,” said McCartin, who enjoys the exact nature of her work. “I like the fact that you can get useful solutions for things where there were none before. Also, I like knowing that my work produces robust results. It is quite satisfying to be able to prove things.”

In 2006, McCartin received the Royal Society of New Zealand’s Hatherton Award, which is presented for the best scientific paper by a PhD student at any New Zealand university in physical, earth, mathematical and information sciences. McCartin received the award for her paper entitled “Parameterized Counting Problems”, which was published in the Annals of Pure and Applied Logic in July 2005.

Interview by Anna Meyer