# 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

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.