All times are given in GMT+2 zone (CET, Warsaw time zone). Scroll down for the detailed program.

Wednesday, June 23rd

14.00-15.15 Session I
15.30-16.30 Invited talk:
Vida Dujmović
16.45-18:00 Business meeting

Thursday, June 24th

09.00-10.00 Invited talk:
Wojciech Samotij
10.15-11.15 Session II
11.30-12.30 Session III
(long break)
14.00-15.00 Session IV
15.15-16.15 Session V

Friday, June 25th

09.00-10.00 Invited talk:
Édouard Bonnet
10.15-11.45 Dieter Kratsch in memoriam

The conference takes place on Airmeet platform and can be accessed below.

Invited talks

Vida Dujmović

Wednesday, 15.30-16.30


Graph Product Structure Theory

This talk will introduce product structure theorem [Dujmović, Joret, Micek, Morin, Ueckerdt and Wood 2019] that states that every planar graph is contained in the strong product of a bounded treewidth graph and a path. The theorem can be generalized from planar graphs to bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k-planar graphs. This introductory talk will also discuss some applications including: asymptotically optimal results for queue number [Heath, Leighton, Rosenberg 1992], and nonrepetitive chromatic number [Alon, Grytczuk, Hałuszczak, and Riordan 2002].

Wojciech Samotij

Thursday, 09.00-10.00


On a method of enumerating independent sets

In this talk, we will present an elementary, yet quite powerful, method of enumerating independent sets in graphs. This method was first employed almost fourty years ago by Kleitman and Winston. It has subsequently been rediscovered and used numerous times by many researchers in various contexts. Our presentation will be illustrated with several applications of it to ‘real-life’ combinatorial problems.

Édouard Bonnet

Friday, 09.00-10.00



The twin-width of a graph, and more generally of a binary structure, has recently been introduced. It is based on a succession of vertex contractions going from the initial graph to a single vertex, called contraction sequence. Surprisingly many classes have bounded twin-width, while generic classes of bounded twin-width enjoy several structural properties and improved algorithms. Throughout applications in algorithmic and structural graph theory, combinatorics, finite model theory, and algebra, we will survey various uses of twin-width. We wish to demonstrate that, perhaps in hindsight, the notion naturally pops up in many contexts. Among other things, we will see that twin-width behaves well with respect to model theory, is a key concept to handle ordered graphs, and that all the principal width measures can be expressed in terms of contraction sequences. We will propose several open questions.


Session I

Wednesday, 14.00-15.15

Chair: Łukasz Kowalik
Preprocessing to Reduce the Search Space: Antler Structures for Feedback Vertex Set (video) (paper)
Huib Donkers and Bart M. P. Jansen
Best Paper Award and Best Student Paper Award
Parameterized complexity of Bandwidth of Caterpillars and Weighted Path Emulation (video) (paper)
Hans L. Bodlaender
Block Elimination Distance (video) (paper)
Öznur Yaşar Diner, Archontia Giannopoulou, Giannos Stamoulis and Dimitrios Thilikos
On Fair Covering and Hitting Problems (video)
Sayan Bandyapadhyay, Aritra Banik and Sujoy Bhore
On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem (video) (paper)
Isja Mannens, Jesper Nederlof, Céline Swennenhuis and Krisztina Szilagyi
FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More (video) (paper)
Bart M. P. Jansen and Jari J.H. de Kroon

Session II

Thursday, 10.15-11.15

Chair: Jan Arne Telle
Disjoint Stable Matchings in Linear Time (video)
Aadityan Ganesh, Vishwa Prakash Hv, Prajakta Nimbhorkar and Geevarghese Philip
Complementation in T-perfect Graphs (video) (paper)
Yixin Cao and Shenghua Wang
On subgraph complementation to H-free graphs (video) (paper)
Dhanyamol Antony, Jay Garchar, Sagartanu Pal, R B Sandeep, Sagnik Sen and R Subashini
Odd Cycle Transversal in Mixed Graphs
Avinandan Das, Lawqueen Kanesh, Jayakrishnan Madathil and Saket Saurabh
Preventing Small (s,t)-Cuts by Protecting Edges (video)
Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz and Frank Sommer
Completion to chordal distance-hereditary graphs: a quartic vertex-kernel (video) (paper)
Christophe Crespelle, Benjamin Gras and Anthony Perez

Session III

Thursday, 11.30-12.30

Chair: Saket Saurabh
A heuristic approach to the treedepth decomposition problem for large graphs (video)
Sylwester Swat and Marta Kasprzak
The Perfect Matching Cut Problem Revisited (video) (paper)
Van Bang Le and Jan Arne Telle
The Complexity of Gerrymandering over Graphs: Paths and Trees (video) (paper)
Matthias Bentert, Tomohiro Koana and Rolf Niedermeier
Feedback Vertex Set on Hamiltonian Graphs (video)
Dario Cavallaro and Till Fluschnik
Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality (video) (paper)
Maciej Rymar, Hendrik Molter, André Nichterlein and Rolf Niedermeier
The Dynamic Complexity of Acyclic Hypergraph Homomorphisms (video)
Nils Vortmeier and Ioannis Kokkinis

Session IV

Thursday, 14.00-15.00

Chair: Bartosz Walczak
Linearizable special cases of the quadratic shortest path problem (video) (paper)
Eranda Cela, Bettina Klinz, Stefan Lendl, James B. Orlin, Gerhard J. Woeginger and Lasse Wulf
A linear-time parameterized algorithm for computing the width of a DAG (video) (paper)
Manuel Cáceres, Massimo Cairo, Brendan Mumey, Romeo Rizzi and Alexandru I. Tomescu
On Morphing 1-Planar Drawings (video) (paper)
Patrizio Angelini, Michael Bekos, Fabrizio Montecchiani and Maximilian Pfister
Bears with Hats and Independence Polynomials (video) (paper)
Václav Blažej, Pavel Dvořák and Michal Opler
The Largest Connected Subgraph Game (video) (paper)
Julien Bensmail, Foivos Fioravantes, Fionn Mc Inerney and Nicolas Nisse
Can Romeo and Juliet Meet? Or Rendezvous Games with Adversaries on Graphs (video) (paper)
Fedor Fomin, Petr Golovach and Dimitrios Thilikos

Session V

Thursday, 15.15-16.15

Chair: Bart Jansen
Beyond Helly graphs: the diameter problem on absolute retracts (video) (paper)
Guillaume Ducoffe
Acyclic, Star, and Injective Colouring: Bounding the Diameter (video) (paper)
Christoph Brause, Petr Golovach, Barnaby Martin, Daniel Paulusma and Siani Smith
The Graphs of Stably Matchable Pairs (video) (paper)
David Eppstein
Sparse and Lightweight Spanners in Weighted Graphs with Local Additive Error (video) (paper)
Reyan Ahmed, Greg Bodwin, Keaton Hamm, Stephen Kobourov and Richard Spence
Labeling Schemes for Deterministic Radio Multi-Broadcast (video) (paper)
Colin Krisko and Avery Miller
On 3-Coloring of (2P_4 ,C_5)-Free Graphs (video) (paper)
Vít Jelínek, Tereza Klimošová, Tomáš Masařík, Jana Novotná and Aneta Pokorná

Dieter Kratsch in memoriam

Friday, 10.15 – 11:45

Chair: Fedor V. Fomin
Fedor V. Fomin
Early years
Andreas Brandstädt
Treewidth and graph classes
Hans Bodlaender
Exact and enumeration algorithms
Petr Golovach
Personal memories
Pinar Heggernes, Haiko Müller and Ioan Todinca