Marthe Bonamy (CNRS, University of Bordeaux)
 |
Talk title: One graph to rule them all: forbidden structures and universal graphs Consider all planar graphs on n vertices. What is the smallest graph that contains them all as induced subgraphs? In this talk, we will gently introduce the audience to the notion of so-called universal graphs (graphs containing all graphs of a given family as induced subgraphs), and focus on the case of graph classes defined by forbidden structures. We present positive and negative results both in dense graphs and in sparse graphs. The audience will also have the answer to the question at the beginning of this abstract, recently established in a breakthrough paper of Dujmović, Esperet, Joret, Gavoille, Micek and Morin. |
|
About the speaker: Marthe Bonamy is a CNRS researcher at the University of Bordeaux since 2015. She is interested in structural and algorithmic aspects of graph theory, with a special fondness for old but simple questions that remain elusive. One of her long-term research obsessions lies in the field of combinatorial reconfiguration, which is about studying the properties of solution spaces of combinatorial optimization problems. She is an editor for Discrete Mathematics and Annals of Combinatorics, a PC member of MFCS 2019, EuroComb 2019, IWOCA 2020, IPEC 2020, and CanaDAM 2021, and has been an invited speaker at several international conferences, including the 8th Cracow Conference on Graph Theory 2018, CanaDAM 2019, Cycles & Colourings 2019, and British Combinatorics Conference 2021. See also her web site here.
|
|
Bart M. P. Jansen (Eindhoven University of Technology)
 |
Talk title: Search-Space Reduction Beyond Kernelization The framework of kernelization gives a mathematical model for the rigorous analysis of preprocessing, aimed at showing that any instance with parameter k can efficiently be reduced to an equivalent one whose size depends only on k. Kernelization serves as a useful tool to obtain FPT algorithms, since any brute-force algorithm solves the reduced instance in time depending only on k. However, from the definition of kernelization it is not clear why kernelization would lead to significant speed-ups when the reduced instance is not solved by brute force, but by a fixed-parameter tractable algorithm whose running time is governed by the value of the parameter. To speed up such algorithms, it is the parameter controlling the size of the search space which should decrease, rather than the encoding size of the input. The discrepancy between reducing the instance size versus decreasing the search space is the focus of this talk. The quest for preprocessing algorithms that reduce the search space leads to a new type of algorithmic and graph-theoretical questions. The talk gives an introduction to this budding line of inquiry by combining examples from recent work with open problems for future research. |
|
About the speaker: Bart Jansen is an Assistant Professor in the Department of Mathematics and Computer Science at Eindhoven University of Technology (TU/e). His areas of expertise include algorithms, complexity theory, and graph theory. His research interests mainly concern parameterized (graph) algorithmics, with a special focus on provably effective preprocessing in the form of kernelization, which has been called the lost continent of polynomial time. He was awarded the Christiaan Huygens Prize in 2014 and the Best Paper Award at MFCS 2016. He is an editor for ACM Transactions on Algorithms and chair of the Steering Committee for the Parameterized Algorithms & Computational Experiments Challenge. His research is supported by ERC Starting Grant ‘ReduceSearch’. See also his web site here. |
|
Bojan Mohar (Simon Fraser University and IMFM)
 |
Talk title: On the structure of crossing-critical graphs Graphs that are critical for the crossing number (their crossing number is at least k but removing any edge decreases the crossing number below k) have bounded path-width. This was proved by Hlineny in 2003. So what else can be said about the structure of crossing-critical graphs for a fixed k? It turns out that there is much more, and this will be the main focus of the presentation. This is joint work with Zdenek Dvorak and Petr Hlineny. |
|
About the speaker: Bojan Mohar is a Professor at the Department of Mathematics, Simon Fraser University, Burnaby, Canada, and Associate Researcher at IMFM, Ljubljana, Slovenia. He is a world-leading graph theorist who has deeply contributed to central areas in discrete mathematics. His fundamental results advanced algebraic, structural, and topological graph theory and influenced theoretical computer science, mathematical chemistry, and other fields. His contributions to graph theory have been recognized with ICA's Euler medal and RSC's John L. Synge Award; he was distinguished as an AMS Fellow, a SIAM Fellow, a Canada Research Chair, and a member of the Royal Society of Canada. He has published more than 250 journal publications, 45 refereed conference papers, 8 books or book chapters, and has over 100 collaborators. See also his web site here. |
|
