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

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

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

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**

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

unpublished, 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**,

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**,

unpublished, 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, 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, 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**