The grant Algorithmic Structure Theory for Sparse Graphs - ALGSTRUCT - was supported by the National Science Centre of Poland (NCN) via POLONEZ grant agreement UMO-2015/19/P/ST6/03998, which has received funding from the European Union's Horizon 2020 research and innovation programme (Marie Skłodowska-Curie grant agreement No. 665778). It started in October 2016, and concluded in September 2018. The investigators in the grant were Sebastian Siebertz (PI) and Michał Pilipczuk.

We organized the Workshop on Algorithms and Structure for Sparse Graphs that took place on Friday, July 14, 2017 at University of Warsaw, Poland as a satellite event of ICALP 2017 (July 10-13, 2017).

Sebastian Siebertz took part in the research project Foreign-born scholars in Central Europe: a planned strategy or a ‘dart throw’?, conducted by Kamil Luczaj. You can find the transcription of the interview here

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

Submitted/in Preparation

M. Pilipczuk, S. Siebertz
Kernelization and approximation of distance-r independent sets on nowhere dense graphs
Available online.

2019

G. Fabiański, M. Pilipczuk, S. Siebertz, S. Toruńczyk.
Progressive Algorithms for Domination and Independence
STACS 2019: 27:1-27:16. Available online.

S. Kreutzer, I. Muzi, P. Ossona de Mendez, R. Rabinovich, S. Siebertz.
Algorithmic Properties of Sparse Digraphs.
STACS 2019: 46:1-46:20. Available online.

S. Akhoondian Amiri, Stefan Schmid, and S. Siebertz.
Distributed Dominating Set Approximations beyond Planar Graphs.
ACM Trans. Algorithms 15(3): 39:1-39:18 (2019). Available online.

M. Pilipczuk and S. Siebertz.
Polynomial bounds for centered colorings on proper minor-closed graph classes.
SODA 2019: 1501-1520. Available online.

S. Siebertz
Greedy domination on biclique-free graphs
Inf. Process. Lett. 145: 64-67 (2019). Available online.

E. Eiben, M. Kumar, A. E. Mouawad, F. Panolan, S. Siebertz
Lossy Kernels for Connected Dominating Set on Sparse Graphs
SIAM J. Discrete Math. 33(3): 1743-1771 (2019). Available online

2018

M. Grohe, S. Kreutzer, R. Rabinovich, S. Siebertz, K. Stavropoulos
Coloring and Covering Nowhere Dense Graphs.
SIAM Journal on Discrete Mathematics (SIDMA), Volume 32(4), 2018. Available online.

J.Gajarsky, S. Kreutzer, J. Nestril, P. Ossona de Mendez, M. Pilipczuk, S. Siebertz, S.Torunczyk.
First-order interpretations of bounded expansion classes.
45th International Colloquium on Automata, Languages, and Programming, ICALP 2018. Available online.

S. Siebertz.
Reconfiguration on nowhere dense graph classes
The Electronic Journal of Combinatorics, Volume 25, 2018. Available online.

M. Pilipczuk, S. Siebertz, and S. Torunczyk.
Parameterized circuit complexity of model-checking on sparse structures.
33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018. Available online.

M. Pilipczuk, S. Siebertz, and S. Torunczyk.
On the number of types in sparse graphs
33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018. Available online.

A. E. Mouawad, N. Nishimura, V. Raman, S. Siebertz.
Vertex Cover Reconfiguration and Beyond.
Algorithms 11(2), 2018. Available online.

S. Akhoondian Amiri, P. Ossona de Mendez, R. Rabinovich, and S. Siebertz.
Distributed Domination on Graph Classes of Bounded Expansion.
30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018. Avalable online.

W. Nadara, Ma. Pilipczuk, R. Rabinovich, F. Reidl, S. Siebertz.
Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness.
17th International Symposium on Experimental Algorithms, SEA 2018. Available online

E. Eiben, M. Kumar, A. E. Mouawad, F. Panolan and S. Siebertz.
Lossy kernels for connected dominating set on sparse graphs.
35th International Symposium on Theoretical Aspects of Computer Science, STACS 2018. Available online

2017

O. Kwon, M. Pilipczuk, and S. Siebertz.
On Low Rank-Width Colorings
43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017. Available online.

K. Eickmeyer, A. Giannopoulou, S. Kreutzer, O. Kwon, M. Pilipczuk, R. Rabinovich, and S. Siebertz.
Neighborhood complexity and kernelization for nowhere dense classes of graphs.
44th International Colloquium on Automata, Languages, and Programming, ICALP 2017. Available online.

J. van den Heuvel, S. Kreutzer, M. Pilipczuk, D. A. Quiroz, R. Rabinovich, and S. Siebertz.
Successor-invariant model-checking on classes of bounded expansion
32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017. Available online.