University of Warsaw

Advisor: Michał Pilipczuk

Faculty of Mathematics, Informatics and Mechanics

University of Warsaw

Thesis: Reconfiguration and structural graph theory

Advisor: Marcin Kamiński

College of Inter-Faculty Individual Studies in Mathematics and Natural Sciences

University of Warsaw

m.wrochnamimuw.edu.pl

My interests range over theoretical aspects of computer science, focusing on parameterized algorithms, graph theory, computational complexity and occasionally logic.

Current working projects include investigating topological approaches to Hedetniemi's conjecture and reconfiguration.

**Turing kernelization for finding long paths in graph classes excluding a topological minor**

with Bart M. P. Jansen, Marcin Pilipczuk

| … | submitted**On Directed Feedback Vertex Set parameterized by treewidth**

with Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof, Michał Pilipczuk, Arkadiusz Socała

| … | submitted

**Tight lower bounds for the complexity of multicoloring**

with Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała

| arXiv | ESA 2017**Cutwidth: obstructions and algorithmic aspects**

with Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos

| arXiv | IPEC 2016**Linear kernels for edge deletion problems to immersion-closed graph classes**

with Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos

| arXiv | ICALP 2017**Square-free graphs are multiplicative**

| arXiv | presentation | SIAM DM 2016 | JCTb | Young Author Prize at Bordeaux Graph Workshop

**Fully polynomial-time parameterized computations for graphs and matrices of low treewidth**

with Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh | arXiv | SODA 2017**On space efficiency of algorithms working on structural decompositions of graphs**

with Michał Pilipczuk | arXiv | STACS 2016**Edge bipartization faster than 2^k**

with Marcin and Michał Pilipczuk | arXiv | IPEC 2016**Polynomial kernelization for removing induced claws and diamonds**

with Marek Cygan, Marcin and Michał Pilipczuk, Erik Jan van Leeuwen | arXiv | WG 2015 | ToCS

**Homomorphism reconfiguration via homotopy**

| arXiv | STACS 2015 | animated presentation (fr)**Reconfiguration in bounded bandwidth and treedepth**

| arXiv | slides | (abridged version in joint paper below)**Reconfiguration over tree decompositions**

with Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman | arXiv | IPEC 2014**Reconfiguring independent sets in claw-free graphs**

with Paul Bonsma, Marcin Kamiński | arXiv | SWAT 2014 | slides

- Research project Optimality in parameterized complexity with my advisor Michał Pilipczuk (2014-).
- I visited the Bergen Algorithms Research Group for a week in 2015 and two weeks in 2016.
- Second award for best master thesis in computer science in Poland, from PTI.
- Research project
*Graphs Within Graphs*with my masters' advisor Marcin Kamiński (2013-2014). - I visited the University of Waterloo, Canada for 2 weeks for a research collaboration with Naomi Nishimura and Amer Mouawad (2014).