Program

All times are given in GMT+2 zone. Scroll down for the detailed program.

Wednesday

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

Thursday

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

Friday

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

Invited talks

Vida Dujmović

day 1, 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

day 2, 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

day 3, 09.00-10.00

Twin-width

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.

Sessions

Session I

day 1, 14.00-15.15

Preprocessing to Reduce the Search Space: Antler Structures for Feedback Vertex Set
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
Hans L. Bodlaender
Block Elimination Distance
Öznur Yaşar Diner, Archontia Giannopoulou, Giannos Stamoulis and Dimitrios Thilikos
On Fair Covering and Hitting Problems
Sayan Bandyapadhyay, Aritra Banik and Sujoy Bhore
On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem
Isja Mannens, Jesper Nederlof, Céline Swennenhuis and Krisztina Szilagyi
FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More
Bart M. P. Jansen and Jari J.H. de Kroon

Session II

day 2, 10.15-11.15

Disjoint Stable Matchings in Linear Time
Aadityan Ganesh, Vishwa Prakash Hv, Prajakta Nimbhorkar and Geevarghese Philip
Complementation in T-perfect Graphs
Yixin Cao and Shenghua Wang
On subgraph complementation to H-free graphs
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
Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz and Frank Sommer
Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
Christophe Crespelle, Benjamin Gras and Anthony Perez

Session III

day 2, 11.30-12.30

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

Session IV

day 2, 14.00-15.00

Linearizable special cases of the quadratic shortest path problem
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
Manuel Cáceres, Massimo Cairo, Brendan Mumey, Romeo Rizzi and Alexandru I. Tomescu
On Morphing 1-Planar Drawings
Patrizio Angelini, Michael Bekos, Fabrizio Montecchiani and Maximilian Pfister
Bears with Hats and Independence Polynomials
Václav Blažej, Pavel Dvořák and Michal Opler
The Largest Connected Subgraph Game
Julien Bensmail, Foivos Fioravantes, Fionn Mc Inerney and Nicolas Nisse
Can Romeo and Juliet Meet? Or Rendezvous Games with Adversaries on Graphs
Fedor Fomin, Petr Golovach and Dimitrios Thilikos

Session V

day 2, 15.15-16.15

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