Dr. Michał Pilipczuk is a computer scientist at the UW Faculty of Mathematics, Informatics and Mechanics. The European Research Council has awarded him a Starting Grant for his BOBR project. The scientist, together with his team, will try to solve discrete problems in networks using their structural and decomposition properties.

Dr. Michał Pilipczuk and another scientist from the Institute of Informatics at the University of Warsaw, Dr. Wojciech Czerwiński, have been awarded prestigious European Research Council Starting Grants. ERC supports talented early-career scientists with 2-7 years of experience since completion of doctoral thesis. Those researchers have already produced excellent supervised work.

Deep mathematics

How to solve hard computational problems in networks by using decomposition methods? A research team led by Dr. Michał Pilipczuk, one of ERC Starting Grant awardees, will try to find it out. Dr. Michał Pilipczuk’s project “Decomposition methods for discrete problems” (BOBR) studies the structural and decomposition properties of networks.

Dr. Michał Pilipczuk’s research interest concerns algorithmics – solving various types of computational problems with a particular focus on the design of parameterized and approximation algorithms on graphs.

“Graphs are mathematical models of networks. Imagine a roadmap of Poland – cities as vertices of a graph, and roads as connections between them. We would like to place 100 new hospitals in a way to minimize the average time to get to a patient. We need to take into account that some hospitals and roads already exist. This problem is in its nature difficult, we do not know how to quickly and efficiently solve it”, says Dr. Michał Pilipczuk.

The Starting Grant laureate considers a similar problem on the example of Norway. “It seems that in Norway it would take us less time to figure out, where to place those institutions. We could, e.g. divide Norway in half, determine the placement of hospitals in the south and north part of the country independently, and then possibly make minor changes around the division line,” he adds.

Dr. Pilipczuk points out that finding a small road network separator in Norway and trying to solve the problem by dividing this network with small separators and assembling solutions from smaller pieces is a structural approach. The scientist explains that the roadmap in Norway can be compared to a tree; we say that it has low treewidth. The roadmap in Poland has a different structure, it is plain, square and has no small separators. Due to the structural properties, it is possible to distinguish difficult problems (the Polish case) from easy ones (the Norwegian case).

The project “Decomposition methods for discrete problems” is purely theoretical. Scientists will try to understand mathematical reality and describe it.

“What really interest us is this mathematical connection, between the abstract notions of structure in networks and the possibility of using those structural properties in order to design efficient algorithms for real life problems,” explains the computer scientist awarded by ERC.

In the BOBR project, Dr. Michał Pilipczuk will apply structural graph theory in four areas related to:

• the theory of sparse graphs,
• parameterized dynamic algorithms,
• parameterization and approximation on planar graphs, and
• algorithms on graphs with forbidden substructures.