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.

The European Research Council awarded him the Starting Grant for the project entitled “Decomposition methods for discrete problems” (BOBR). The research will take five years. For his project BOBR, Dr. Pilipczuk will receive nearly € 1.4 million. Several doctoral candidates, postdocs and researchers from the Faculty of Mathematics, Informatics and Mechanics will be engaged in BOBR.

 

Dr. Michał Pilipczuk has been working at the Institute of Informatics of the University of Warsaw since 2015. His research interests include parameterized complexity, logic in computer science and structural graph theory.

 

In 2013, he defended his doctoral thesis in Theoretical Computer Science “Tournaments and Optimality: New Results in Parameterized Complexity” at the University of Bergen. In years 2014-2015, he was a postdoc of Warsaw Centre of Mathematics and Computer Science, affiliated with the UW Institute of Informatics.

 

Dr. Pilipczuk was awarded with several awards and scholarships, e.g. ERCIM Cor Baayen Award 2016 (awarded annually to one promising young researcher in computer science and applied mathematics), Lipski Prize for the best young researchers working in computer science in Poland, START scholarships granted by the Foundation for Polish Science (in 2015 and 2016) or scholarship of the Ministry of Science and Higher Education of the Republic of Poland for outstanding young researchers. He was engaged in project entitled “Technology transfer between modern algorithmic paradigms” (TOTAL), led by Prof. Marek Cygan who received an ERC grant in 2015 for implementing it.