Marcin Wrochna – personal web page

science teaching personal

Marcin Wrochna

pronounced [ˈmarʨ̑in 'vrɔxna]
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.

---

Publications

[DBLP]

2016

Tight lower bounds for the complexity of multicoloring
with Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała
  | arXiv | submitted
• 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

2015

• 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

2014

• 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

Activities

• 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).