Invited talks

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.

Treewidth is the classic example of a decomposition-based width parameter: the treewidth of a graph G is the minimum width of a tree-decomposition of G. Other tree-decomposition-based width parameters use different measures on the bags; tree-independence number, for example, uses the maximum size of an independent set of a bag. 

In this talk, we explore graph-decompositions where we allow the underlying graph of the decomposition to be more complex than a tree. The goal of these general graph-decompositions is to absorb the global structure of a graph into the decomposition graph itself, so the size of the bags reflects only the local complexity of the graph. First, we will discuss how to define the decomposition graph to reflect (only) the global structure of the underlying graph. Then, we will consider the insights gained by modeling the global structure of a graph via a graph-decomposition in this way. I will also discuss how width parameters based on graph-decompositions compare to other width parameters designed to capture the local complexity of a graph. The focus of this talk will be on open problems and promising directions for further study. 

This talk is based on joint work with Reinhard Diestel and Paul Knappe.

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.