Program of WG 2019


Tuesday June 18, 2019

19:30: Latest departure from Ribes de Freser by «cremallera»
20:00–20:45: Registration
20:45: Dinner

Wednesday June 19, 2019

Until 9:00: Breakfast
9:00–9:10: Welcome

Session 1. Chair: Ignasi Sau

9:10–10:00Invited lecture by Marc Noy. Logic of sparse random graphs

10:00–10:25: Ararat Harutyunyan, Michael Lampis, Vadim Lozin and Jerome Monnot. Maximum Independent Sets in Subcubic Graphs: New Results
10:25–10:50: Edin Husic and Martin Milanič. A polynomial-time algorithm for the independent set problem in {P_10,C_4,C_6}-free graphs

10:50 –11:15: Coffee break

Session 2. ChairVadim Lozin

11:15–11:40: Robert Ganian and Sebastian Ordyniak. The Power of Cut-Based Parameters for Computing Edge Disjoint Paths
11:40–12:05: Étienne Bamas and Louis Esperet. Local approximation of the Maximum Cut in regular graphs
12:05–12:30: Pierre Bergé, Benjamin Mouscadet, Arpad Rimmel and Joanna Tomasik. Fixed-parameter tractability of counting small minimum (S,T)-cuts
12:30–12:55: Martin Milanič and Nevena Pivač. Minimal separators in graph classes defined by small forbidden induced subgraphs
13:00–14:30: Lunch

Session 3. ChairHans L. Bodlaender 

15:00–15:25: Svein Høgemo, Jan Arne Telle and Erlend Raa Vågset. Linear MIM-width of Trees
15:25–15:50: Martin Dyer, Catherine Greenhill and Haiko Muller. Counting independent sets in graphs with bounded bipartite pathwidth
15:50–16:15: Ivan Bliznets and Danil Sagunov. On Happy Colorings, Cuts, and Structural Parameterizations
16:15–16:40: Huib Donkers and Bart M.P. Jansen. A Turing Kernelization Dichotomy for Structural Parameterizations of F-Minor-Free Deletion

16:40 –17:05: Coffee break

Session 4. Chair: Maria Serna

17:05–17:30: Yann Disser, Andreas Emil Feldmann, Max Klimm and Jochen Koenemann. Travelling on Graphs with Small Highway Dimension
17:30–17:55: Bart Jansen, László Kozma and Jesper Nederlof. Hamiltonicity below Dirac’s condition
17:55–18:20: Rahnuma Islam Nishat and Sue Whitesides. Reconfiguring Hamiltonian Cycles in L-Shaped Grid Graphs
18:20–18:45: Rémy Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono and Yota Otachi. Independent Set Reconfiguration Parameterized by Modular-Width

19:45–20:30Business meeting

20:45: Dinner

Thursday June 20, 2019

Until 9:00: Breakfast

9:00–12:30: Trekking (in the afternoon it may rain! We will walk couterclockwise the first 3.4km of this track, until here, and then back)

13:00–14:30: Lunch

Session 5Chair: Dimitrios M. Thilikos

14:45–15:35Invited lecture by Saket Saurabh. Parameterized algorithms for geometric graphs via decomposition theorems
15:35–16:00: Bogdan Alecu, Aistis Atminas and Vadim Lozin. Graph functionality
16:00–16:25: Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner and Birgit Vogtenhuber. Flip distances between graph orientations

16:25–16:50: Coffee break

Session 6. ChairJan Kratochvil

16:50–17:15: Daniel Gonçalves. 3-colorable planar graphs have an intersection segment representation using 3 slopes
17:15–17:40: Patrizio Angelini, Michael Bekos, Martin Gronemann and Antonios Symvonis. Geometric Representations of Dichotomous Ordinal Data
17:40–18:05: Dibyayan Chakraborty, Joydeep Mukherjee and Sandip Das. Approximating Minimum Dominating Set on String graphs
18:05–18:30: Steven Chaplick. Intersection Graphs of Non-Crossing Paths

18:30–18:55: Coffee break

Session 7. ChairDaniel Gonçalves

18:55–19:20: Jan Böker. Color Refinement, Homomorphisms, and Hypergraphs
19:20–19:45: Karolina Okrasa and Paweł Rzążewski. Subexponential algorithms for variants of homomorphism problem in string graphs
19:45–20:10: Hubie Chen, Radu Curticapean and Holger Dell. The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms

20:45: Conference dinner


Friday June 21, 2019

Until 9:00Breakfast

Session 8. Chair: Christophe Paul

9:00 – 09:50Invited lecture by Frédéric Havet. Unavoidability and universality of digraphs

09:50–10:15: Guillaume Ducoffe. The 4-Steiner Root Problem
10:15–10:40: Torben Hagerup. Fast Breadth-First Search in Still Less Space

10:40–11:05: Coffee break

Session 9. ChairSteven Chaplick

11:05–11:30: Sebastian Wiederrecht, Meike Hatzel and Roman Rabinovich. Cyclewidth and the Grid Theorem for Perfect Matching Width of Bipartite Graphs
11:30–11:55: Meghana Nasre, Prajakta Nimbhorkar and Nada Pulath. Classified Rank-Maximal Matchings and Popular Matchings -- Algorithms and Hardness
11:55–12:20: Therese Biedl, Ahmad Biniaz, Veronika Irvine, Kshitij Jain, Philipp Kindermann and Anna Lubiw. Maximum Matchings and Minimum Blocking Sets in Theta-6 Graphs
12:20–12:45: Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito and Moritz Muehlenthaler. Shortest Reconfiguration of Matchings

13:00–14:30: Lunch