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

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

The topic of my PhD thesis is Hedetniemi's conjecture and spaces of graph homomorphisms, with new applications of topological methods.

**The step Sidorenko property and non-norming edge-transitive graphs**

with Daniel Král’, Taísa L. Martins, Péter Pál Pach

| arXiv | submitted

**On inverse powers of graphs and topological implications of Hedetniemi's conjecture**

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

with Bart M. P. Jansen, Marcin Pilipczuk

| arXiv | IPEC 2017**On Directed Feedback Vertex Set parameterized by treewidth**

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

| arXiv | 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 | J. Comb. Theory B

| 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 | TALG**On space efficiency of algorithms working on structural decompositions of graphs**

with Michał Pilipczuk

| arXiv | STACS 2016 | ACM Trans. Comput. Theory**Edge bipartization faster than 2^k**

with Marcin and Michał Pilipczuk

| arXiv | IPEC 2016 | Algorithmica**Polynomial kernelization for removing induced claws and diamonds**

with Marek Cygan, Marcin and Michał Pilipczuk, Erik Jan van Leeuwen

| arXiv | WG 2015 | Theory Comput. Syst.

**Homomorphism reconfiguration via homotopy**

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

| arXiv | slides | J. Comput. Syst. Sci. | (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

- Principal investigator in
*The topology of solution spaces of combinatorial problems*, a PRELUDIUM grant funded by the National Science Centre, Poland (2017-2019). - Research project
*Optimality in parameterized complexity*with my advisor Michał Pilipczuk (2014-2017). - I visited Daniel Kráľ at the University of Warwick, DIMAP, for 5 weeks in 2017; Claude Tardif at Queen's University in Kingston, Ontario, for a week in 2017; Marthe Bonamy at LaBRI, Bordeaux, for 2 weeks in 2016; 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).

* pronounced [ˈmarʨ̑in 'vrɔxna], like "mar-chin vroh-na", but "Martin" is perfectly fine :)