Fabian Kuhn, Albert-Ludwigs-Universität
Kitty Meeks, University of Glasgow
Title: In search of useful temporal graph parameters
Abstract: A highly successful approach for tackling NP-hard problems on static graphs is the paradigm of parameterised complexity: the running time of algorithms is analysed in terms of a secondary measure, or parameter, in addition to the total input size, and the goal is to restrict the combinatorial explosion to the parameter (which is hopefully, in instances of interest, much smaller than the total input size). Many widely used parameters capture structural properties of the input graph, for example the edit distance to some class on which the problem is tractable, or the ease with which the graph can be decomposed according to specific rules. In recent years, there have been numerous attempts to apply the parameterised approach to algorithmic problems on temporal graphs, but this has led to efficient parameterised algorithms in only a few cases: for many natural problems (including some that are polynomial-time solvable on static graphs) the additional complexity introduced by encoding temporal information in the graph renders the temporal versions intractable even when the underlying graph has very simple structure (e.g. when it is a tree or even a path). This motivates the search for new parameters, specifically designed for temporal graphs, which capture properties of the temporal information in addition to the structure of the underlying graph. In this talk I will survey recent progress in the development of such parameters and highlight a large number of remaining challenges.
Nicola Santoro, Carleton University