Grant *Optimality in Parameterized Complexity* wass funded by the Polish National Science Center (NCN). It started in October 2014, and concluded September 2017. The investigators in the grant were Michał Pilipczuk (PI) and Marcin Wrochna.

The following list contains works supported by the grant. Preprints of all the works are available on arxiv.

Florian Barbero, Christophe Paul, Michał Pilipczuk,** Strong immersion is a well-quasi-ordering for semi-complete digraphs**,

unpublished, available at [arxiv],

**Show abstract**

Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk,** On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs**,

unpublished, available at [arxiv],

**Show abstract**

Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna,** Turing kernelization for finding long paths in graph classes excluding a topological minor**,

IPEC 2017, available at [arxiv],

**Show abstract**

Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof, Michał Pilipczuk, Arkadiusz Socała, Marcin Wrochna,** On Directed Feedback Vertex Set parameterized by treewidth**,

unpublished, available at [arxiv],

**Show abstract**

Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh,** Below all subsets for Minimal Connected Dominating Set**,

unpublished, available at [arxiv],

**Show abstract**

Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała, Marcin Wrochna,** Tight lower bounds for the complexity of multicoloring**,

ESA 2017, available at [arxiv],

**Show abstract**

Michał Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese,** Approximation and parameterized algorithms for geometric independent set with shrinking**,

MFCS 2017, available at [arxiv],

**Show abstract**

Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, Michał Pilipczuk,** Hardness of approximation for strip packing**,

ACM Transactions on Computation Theory (TOCT), available at [arxiv],

**Show abstract**

Florian Barbero, Christophe Paul, Michał Pilipczuk,** Exploring the complexity of layout parameters in tournaments and semi-complete digraphs**,

ICALP 2017, available at [arxiv],

**Show abstract**

Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna,** Linear kernels for edge deletion problems to immersion-closed graph classes**,

ICALP 2017, available at [arxiv],

**Show abstract**

Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh, Marcin Wrochna,** Fully polynomial-time parameterized computations for graphs and matrices of low treewidth**,

SODA 2017, available at [arxiv],

**Show abstract**

Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh,** Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering**,

FOCS 2016, available at [arxiv],

**Show abstract**

Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna,** Cutwidth: obstructions and algorithmic aspects**,

IPEC 2016, available at [arxiv],

**Show abstract**

Marcin Pilipczuk, Michał Pilipczuk, Marcin Wrochna,** Edge Bipartization faster than 2^{k}**,

IPEC 2016, journal version in Algorithmica, available at [arxiv],

**Show abstract**

Ivan Bliznets, Marek Cygan, Paweł Komosa, Michał Pilipczuk,** Hardness of approximation for H-free edge modification problems**,

APPROX 2016, available at [arxiv],

**Show abstract**

Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh,** Lower bounds for approximation schemes for Closest String**,

SWAT 2016, available at [arxiv],

**Show abstract**

Michał Pilipczuk, Marcin Wrochna,** On space efficiency of algorithms working on structural decompositions of graphs**,

STACS 2016, journal version accepted to ACM Transactions on Computation Theory, available at [arxiv],

**Show abstract**

Ivan Bliznets, Marek Cygan, Paweł Komosa, Lukáš Mach, Michał Pilipczuk,** Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems**,

SODA 2016, available at [arxiv],

**Show abstract**

Pål Grønås Drange, Michał Pilipczuk,** A polynomial kernel for Trivially Perfect Editing**,

ESA 2015, available at [arxiv],

**Show abstract**

Dániel Marx, Michał Pilipczuk,** Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams**,

ESA 2015, available at [arxiv],

**Show abstract**

Ariel Gabizon, Daniel Lokshtanov, Michał Pilipczuk,** Fast algorithms for parameterized problems with relaxed disjointness constraints**,

ESA 2015, available at [arxiv],

**Show abstract**

Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna,** Polynomial kernelization for removing induced claws and diamonds**,

WG 2015, journal version in Theory of Computing Systems, available at [arxiv],

**Show abstract**