Sebastian Wiederrecht

Title: Vital Linkages and the Graph Minor Algorithm

Abstract: One of the many breakthrough results originating from Robertson and Seymour's Graph Minor Series is the Graph Minor Algorithm which allows for efficient minor checking as well as providing an FPT-algorithm for the k-Disjoint Paths Problem. At the core of this problem lies the celebrated Irrelevant Vertex Technique whose proof of correctness heavily relies on a deep structural insight: The existence of the so-called Vital Linkage Function λ. Robertson and Seymour proved that any instance of the k-Disjoint Paths Problem with a unique solution using all vertices of the graph must have treewidth at most λ(k). The original proof did not make any estimate on the order of λ and the best bound until now is still estimated - yet never explicitly stated - to be at least quadruple exponential in k.

In this talk I give insights to how recent developments in the theory of graph minors may be used to prove that λ(k) is exponential in kO(1). Indeed, we prove a stronger version of the Vital Linkage Theorem as follows: Let k be the number of terminals, b be the bidimensionality of the terminal set, and d be a non-negative integer, then there exists an integer β(k,b,d) ∊ exp( (b+d)O(1) ) kO(1) such that every instance of the d-folio problem with k terminals and treewidth at least β(k,b,d) admits an irrelevant vertex. These bounds are optimal up to the degrees of the polynomials involved and imply an algorithm for the rooted minor checking problem for minors of size at most d with running time 2β(k,b,d) n2.

This is joint work with Dario Cavallaro, Maximilian Gorsky, Stephan Kreutzer, and Dimitrios Thilikos.

Viktor Zamaraev

Title: Recent Advances in Adjacency Labeling Schemes
Abstract: Adjacency labeling schemes provide a local representation of graphs: each vertex is assigned a short label, and adjacency between two vertices can be determined solely from their labels. In this talk, I will survey recent advances in adjacency labeling schemes, with a particular emphasis on small graph classes. I will highlight new positive results that establish efficient labeling schemes for broad families of such classes, as well as recent lower bounds that reveal fundamental limitations of these representations. The talk will outline several directions for future work.