The recognized thesis discusses the computational complexity theory as regards algorithms that solve computational problems defined with graphs. The thesis focuses specifically on the rather broad category of the so-called graph homomorphisms.

Additional assumptions might be of help

There are many important graph problems for which fast-working algorithms have been found over the years. On the other hand, there are some “complex” problems that are easy to formulate but we will still do not know how to write a fast-working algorithm to solve it. One example may be the well-known travelling salesman problem, says Karolina.

Karolina admits that many of the graph homomorphisms are precisely such "complex" problems.

We may adopt a "naive" approach and verify all the possibilities one by one, hoping that eventually we will find the solution. However, in the pessimistic scenario, this may take very long. Therefore, we want to find out whether such approach may be improved, she adds.

According to the award winner, one of the directions in the research on how to improve such approach is to limit the analysis to only a certain class of graphs. In many situations it is not necessary to find a solution for any graph but only for the graphs with a specific property. Then, it may turn out that we are able to design an algorithm that will work faster since it uses the properties of the specific graph. If, despite additional assumptions made, we cannot find a better algorithm, it may occur, however, that we are able to demonstrate in a formal manner that such a property has no significant effect on the speed of the problem-solving process.

In my work I have analyzed graphs of limited treewidth. The treewidth is a function which for each graph shows, to put it simply, the complexity of its structure, the VCLA International Student Award 2020 winner explains.

Great discovery

One of the crucial moments of the research project was when the student and her supervisor found two forgotten scientific articles written almost 20 years ago. The papers were published in 2001 and 2002 and included a series of interesting statements on graph theory but apparently no one had used them in their research before. It turned out that some of the results were exactly what Karolina needed for her thesis. Karolina says that it was an important lesson for her – very often a mathematical statement is proved without any specific application in mind. Such theories are later developed by different researchers, or used as tools in related fields. This is precisely what has happened here, although these mathematical statements had to wait almost 20 years to be applied.

More information on the award granted to Karolina Okrasa can be found on the VCLA website >>