{"id":276,"date":"2021-06-02T15:56:33","date_gmt":"2021-06-02T13:56:33","guid":{"rendered":"https:\/\/wg2021.mimuw.edu.pl\/?page_id=276"},"modified":"2021-06-26T00:13:55","modified_gmt":"2021-06-25T22:13:55","slug":"program","status":"publish","type":"page","link":"https:\/\/wg2021.mimuw.edu.pl\/program\/","title":{"rendered":"Program"},"content":{"rendered":"\n

<\/p>\n\n\n

\n
\n\n

Program<\/h1>\n\n\n\n

All times are given in GMT+2 zone (CET, Warsaw time zone). Scroll down for the detailed program.<\/p>\n\n\n\n

\n
\n

Wednesday, June 23rd<\/h3>\n\n\n\n
14.00-15.15<\/td>Session I<\/strong><\/td><\/tr>
15.30-16.30<\/td>Invited talk:<\/strong>
Vida Dujmovi\u0107<\/strong><\/td><\/tr>
16.45-18:00<\/td>Business meeting<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n<\/div>\n\n\n\n
\n

Thursday, June 24th<\/h3>\n\n\n\n
09.00-10.00<\/td>Invited talk:<\/strong>
Wojciech Samotij<\/strong><\/td><\/tr>
10.15-11.15<\/td>Session II<\/strong><\/td><\/tr>
11.30-12.30<\/td>Session III<\/strong><\/td><\/tr>
<\/td>(long break)<\/td><\/tr>
14.00-15.00<\/td>Session IV<\/strong><\/td><\/tr>
15.15-16.15<\/td>Session V<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

<\/p>\n<\/div>\n\n\n\n

\n

Friday, June 25th<\/h3>\n\n\n\n
09.00-10.00<\/td>Invited talk:<\/strong>
\u00c9douard Bonnet<\/strong><\/td><\/tr>
10.15-11.45<\/td>Dieter Kratsch in memoriam<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n<\/div>\n<\/div>\n\n\n\n

The conference takes place on Airmeet platform and can be accessed below.<\/p>\n\n\n

Enter event<\/a><\/div>\n<\/div><\/div><\/div>\n\n
\n
\n\n

Invited talks<\/h1>\n\n\n
\n
\n

Vida Dujmovi\u0107<\/h3>\n

Wednesday, 15.30-16.30<\/p>\n \n (video)<\/a>\n <\/div>\n

\n
\n\n

Graph Product Structure Theory<\/strong><\/h3>\n\n\n\n

This talk will introduce product structure theorem<\/em> [Dujmovi\u0107, 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\u0142uszczak, and Riordan 2002].<\/p>\n\n<\/div>\n \n <\/div>\n<\/div><\/div>\n\n

\n
\n

Wojciech Samotij<\/h3>\n

Thursday, 09.00-10.00<\/p>\n \n (video)<\/a>\n <\/div>\n

\n
\n\n

On a method of enumerating independent sets<\/strong><\/h3>\n\n\n\n

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 \u2018real-life\u2019 combinatorial problems.<\/p>\n\n<\/div>\n \n <\/div>\n<\/div><\/div>\n\n

\n
\n

\u00c9douard Bonnet<\/h3>\n

Friday, 09.00-10.00<\/p>\n \n (video)<\/a>\n <\/div>\n

\n
\n\n

Twin-width<\/strong><\/h3>\n\n\n\n

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.<\/p>\n\n<\/div>\n \n <\/div>\n<\/div><\/div>\n<\/div><\/div><\/div>\n\n

\n
\n\n

Sessions<\/h1>\n\n\n
\n
\n

Session I<\/h3>\n

Wednesday, 14.00-15.15<\/p>\n

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

Session II<\/h3>\n

Thursday, 10.15-11.15<\/p>\n

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

Session III<\/h3>\n

Thursday, 11.30-12.30<\/p>\n

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

Session IV<\/h3>\n

Thursday, 14.00-15.00<\/p>\n

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

Session V<\/h3>\n

Thursday, 15.15-16.15<\/p>\n

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

Dieter Kratsch in memoriam<\/h3>\n

Friday, 10.15 – 11:45<\/p>\n

Chair: Fedor V. Fomin<\/h5>\n \n <\/div>\n
\n
\n
\n
Introduction<\/div>\n
Fedor V. Fomin<\/div>\n
<\/div>\n<\/div>\n
\n
Early years<\/div>\n
Andreas Brandst\u00e4dt<\/div>\n
<\/div>\n<\/div>\n
\n
Treewidth and graph classes<\/div>\n
Hans Bodlaender<\/div>\n
<\/div>\n<\/div>\n
\n
Exact and enumeration algorithms <\/div>\n
Petr Golovach<\/div>\n
<\/div>\n<\/div>\n
\n
Personal memories<\/div>\n
Pinar Heggernes, Haiko M\u00fcller and Ioan Todinca<\/div>\n
<\/div>\n<\/div>\n<\/div>\n<\/div>\n \n <\/div>\n<\/div><\/div>\n<\/div><\/div><\/div>\n\n\n

<\/p>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":2,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"_links":{"self":[{"href":"https:\/\/wg2021.mimuw.edu.pl\/wp-json\/wp\/v2\/pages\/276"}],"collection":[{"href":"https:\/\/wg2021.mimuw.edu.pl\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/wg2021.mimuw.edu.pl\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/wg2021.mimuw.edu.pl\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/wg2021.mimuw.edu.pl\/wp-json\/wp\/v2\/comments?post=276"}],"version-history":[{"count":73,"href":"https:\/\/wg2021.mimuw.edu.pl\/wp-json\/wp\/v2\/pages\/276\/revisions"}],"predecessor-version":[{"id":397,"href":"https:\/\/wg2021.mimuw.edu.pl\/wp-json\/wp\/v2\/pages\/276\/revisions\/397"}],"wp:attachment":[{"href":"https:\/\/wg2021.mimuw.edu.pl\/wp-json\/wp\/v2\/media?parent=276"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}