Isolde Adler Haiko Müller (Eds.) S S o C R A 1 0 3 2 Graph-Theoretic Concepts 1 S C in Computer Science N L 46th International Workshop, WG 2020 Leeds, UK, June 24–26, 2020 Revised Selected Papers Lecture Notes in Computer Science 12301 Founding Editors Gerhard Goos, Germany Juris Hartmanis, USA Editorial Board Members Elisa Bertino, USA Gerhard Woeginger , Germany Wen Gao, China Moti Yung, USA Bernhard Steffen , Germany Advanced Research in Computing and Software Science Subline of Lecture Notes in Computer Science Subline Series Editors Giorgio Ausiello, University of Rome ‘La Sapienza’, Italy Vladimiro Sassone, University of Southampton, UK Subline Advisory Board Susanne Albers, TU Munich, Germany Benjamin C. Pierce, University of Pennsylvania, USA Bernhard Steffen , University of Dortmund, Germany Deng Xiaotie, Peking University, Beijing, China Jeannette M. Wing, Microsoft Research, Redmond, WA, USA More information about this series at http://www.springer.com/series/7407 ü Isolde Adler Haiko M ller (Eds.) (cid:129) Graph-Theoretic Concepts in Computer Science 46th International Workshop, WG 2020 – Leeds, UK, June 24 26, 2020 Revised Selected Papers 123 Editors Isolde Adler HaikoMüller University of Leeds University of Leeds Leeds,UK Leeds,UK ISSN 0302-9743 ISSN 1611-3349 (electronic) Lecture Notesin Computer Science ISBN 978-3-030-60439-4 ISBN978-3-030-60440-0 (eBook) https://doi.org/10.1007/978-3-030-60440-0 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ©SpringerNatureSwitzerlandAG2020 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartofthe material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodologynow knownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbookare believedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsortheeditors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissionsthatmayhavebeenmade.Thepublisherremainsneutralwithregardtojurisdictionalclaimsin publishedmapsandinstitutionalaffiliations. ThisSpringerimprintispublishedbytheregisteredcompanySpringerNatureSwitzerlandAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Preface This volume contains the 32 papers presented at the 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020). The workshop was held online during June 24–26, 2020, after the original plans to organise it in Leeds, UK, had to be abandoned due to COVID-19. Over 200 computer scientists and mathe- maticians from all over the world registered for the conference, although most talks were attended by 65–75 participants. WGhasalong-standingtradition.Since1975,WGtookplace24timesinGermany, 5timesinTheNetherlands,3timesinFrance,2timesinAustria,2timesintheCzech Republic,aswellasinGreece,Israel,Italy,Norway,Slovakia,Spain,Switzerland,and Turkey one time each. This was the second time the workshop was organised in the UK. WGaimstomergetheoryandpracticebydemonstratinghowconceptsfromGraph Theory can be applied to various areas in Computer Science, or by extracting new graph theoretic problems from applications. The goal is to present emerging research results and to identify and explore directions of future research. The conference is well-balanced with respect to established researchers and junior scientists. Wereceived96submissions,2ofwhichwerewithdrawnbeforeenteringthereview process. The Program Committee (PC) provided 3 to 5 independent reviews for each submission. The PC accepted 32 papers – an acceptance ratio of nearly 1/3. As in previousyears,duetostrongcompetitionandlimitedspacetherewerepapersthatwere not accepted although they deserved to be. The prize for the Best Paper at WG 2020 was awarded to Jesper Nederlof, Michał Pilipczuk, Céline Swennenhuis, and Karol Wȩgrzycki for their paper “Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space.” TheprizefortheBestStudentPaperatWG2020wasawardedtoSriramBhyravarapu for his paper “Combinatorial bounds for conflict-free coloring on open neighbor- hoods,” coauthored by Subrahmanyam Kalyanasundaram. The program included two inspiringinvitedtalks,byMihyunKang(TUGraz,Austria)on“Topologicalaspectsof random graphs” and by Jaroslav Nešetřil (Charles University, Prague) on “Three aspects of structural graph theory.” Moreover, many individuals contributed to the success of WG 2020. In particular our thanks go to: – All authors who submitted their newest research results to WG – The reviewers whose expertise supported the selection process – The members of the PC, who graciously gave their time and energy – The members of the Organizing Committee at the University of Leeds, UK – The School of Computing at the University of Leeds, UK – The EasyChair system for hosting the evaluation process vi Preface – Springer for supporting the Best Paper Awards – The invited speakers, all speakers, the session chairs, and the participants for their contributions and support to make WG 2020 an inspiring event July 2020 Isolde Adler Haiko Müller Organization Program Committee Isolde Adler University of Leeds, UK Nikhil Bansal Eindhoven University of Technology, CWI, The Netherlands Cristina Bazgan Université Paris Dauphine, France Radu Curticapean IT University of Copenhagen, Denmark Thomas Erlebach University of Leicester, UK Celina de Figueredo Federal University of Rio de Janeiro, Brazil Pinar Heggernes Bergen University, Norway Bart Jansen EindhovenUniversityofTechnology,TheNetherlands Mamadou Kanté Université Clermont Auvergne, France Tereza Klimošová Charles University Prague, Czech Republic Łukasz Kowalik University of Warsaw, Poland Stephan Kreutzer Technical University Berlin, Germany Beppe Liotta University of Perugia, Italy Ross McConnell Colorado State University, USA Haiko Müller University of Leeds, UK Sang-il Oum Institute for Basic Science, KAIST, South Korea Viresh Patel University of Amsterdam, The Netherlands Alex Scott University of Oxford, UK Ryuhei Uehara Japan Advanced Institute of Science and Technology, Japan Sue Whitesides McGill University, Canada Organizing Committee Isolde Adler Haiko Müller Martin Dyer Alison Whiteley Marc Heinrich Samuel Wilson Additional Reviewers Mikkel Abrahamsen Manu Basavaraju Ernst Althaus Julien Baste André Nichterlein Michael Bekos Oliver Bachtler Rémy Belmonte viii Organization Benjamin Bergougnoux Niels Grüttemeier Therese Biedl Grzegorz Gutowski Thomas Bläsius Michel Habib Hans L. Bodlaender Michael Hamann Stefan Boettcher Tesshu Hanaka Nicolas Bonichon Marc Heinrich Nicolas Bousquet Duc A. Hoang Andreas Brandstädt Jacob Holm Nick Brettell Andreas Holmsen Guido Brückner Md. Iqbal Hossain Yixin Cao Shenwei Huang Guilherme de Castro Mendes Gomes Davis Issac Leroy Chew Lars Jaffke Rafael Santos Coelho Pallavi Jain Colin Cooper Matthew Johnson Matthew Coulson Mark Jones Bruno Courcelle Tomáš Kaiser Christophe Crespelle Mong-Jen Kao Konrad K. Da browski Leon Kellerhals Clément Dallard Shuji Kijima Sandip Das Eun Jung Kim Ewan Davies Ringi Kim Holger Dell Philipp Kindermann Alberto Espuny Díaz Evangelos Kipouridis Walter Didimo Masashi Kiyomi Emilio Di Giacomo Yasuaki Kobayashi François Dross Yusuke Kobayashi Vida Dujmović Christian Komusiewicz Martin Dyer Danny Krizanc Eduard Eiben Arnaud Labourel Jessica Enright Michael Lampis David Eppstein Van Bang Le Carl Feghali Orlando Lee Andreas Emil Feldmann Erik Jan van Leeuwen Asaf Ferber Paloma de Lima Krzysztof Fleszar Henri Lotze Guilherme D. da Fonseca Borut Lužar Florent Foucaud Yingbin Ma Viktor Fredslund-Hansen Gary Macgillivray Vincent Froese Raphael Machado Radoslav Fulek Ana Karolinna Maia Nicola Galesi Thiago Marcilon Archontia Giannopoulou Andrea Marino J. Pascal Gollin Nicolas Martins Petr Golovach Arnaud Mary Daniel Gonçalves Tomáš Masařík Organization ix Tamara Mchedlidze Guus Regts Kitty Meeks Jonathan Rollin George Mertzios Ignaz Rutter Martin Milanič Paweł Rza żewski Pranabendu Misra Toshiki Saitoh Kazuyuki Miura Gelasio Salazar Eiji Miyano Maycon Sambinelli Hiroyuki Miyata Rudini Sampaio Hendrik Molter Marcio Costa Santos Debajyoti Mondal Rafael Schouery Fabrizio Montecchiani Pascal Schweitzer Guilherme O. Mota Aleksandar Shurbevski Marcin Mucha Ana Silva Irene Muzi Murilo V. G. da Silva Jesper Nederlof Jefferson Elbert Simões Ofer Neiman Blerina Sinaimeri Alantha Newman George Skretas Nicolas Nisse Uéverton Souza Jana Novotná Yann Strozecki Eunjin Oh Asahi Takaoka Yoshio Okamoto Alessandra Tappini Mateus de Oliveira Oliveira Anastasiia Tsvietkova Aurélien Ooms Tomáš Valla Sebastian Ordyniak Lluis Vena João Paixão Kevin Verbeek Fahad Panolan Kristina Vušković Charis Papadopoulos Kunihiro Wasa Pan Peng Sebastian Wiederrecht Lucia Draque Penso Samuel Wilson Thi Ha Duong Phan Michał Włodarczyk Christophe Picouleau David R. Wood Théo Pierron Marcin Wrochna Astrid Pieterse Mingyu Xiao Lionel Pournin Viktor Zamaraev Arash Rafiey Meirav Zehavi Ashutosh Rai Anna Zych Jean-Florent Raymond The Long Tradition of WG WG 1975 U. Pape – Berlin, Germany WG 1976 H. Noltemeier – Göttingen, Germany WG 1977 J. Mühlbacher – Linz, Austria WG 1978 M. Nagl, H. J. Schneider – Burg Feuerstein near Erlangen, Germany