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
Title:Moving in Time-Varying Graphs
Abstract:The advent of highly dynamic networks (e.g., ad-hoc wireless mobile networks, vehicular networks, social networks), where changes in the interconnection structure are continuously occurring normal events, has brought to the forefront the problem of how to model such networks and the changes through time of their topology. The common representation (variously called time-varying graph, temporal network, or, if time is discrete, dynamic graph, temporal graph, evolving graph, …) fully captures the temporal dynamics of the changes. Interestingly, the presence in the network of mobile computational entities (e.g., mobile agents, robots, web crawlers, …) adds an additional level of dynamics, the one created by their movements on the changing space.
The focus of this talk will be on entities moving in (discrete-time) highly dynamic networks, and examine some of the different crucial assumptions made in the current research. From a computational point of view, the fundamental critical assumption is on the (amount and type of) knowledge that the entities have about the dynamics of the changes. A wide variety of assumptions have been made in this regards in the literature, ranging from full advanced knowledge of all the changes (called full disclosure), to just awareness of the existence of minimal connectivity requirements (called temporal connectivity).
In this talk, I will discuss some problems, in particular “Cops&Robber” and “Exploration”, recently examined in the literature under some of these assumptions. I will use them to highlight some interesting solution techniques as well as methodological insights, which have emerged in these investigations and that, if not immediately applicable/transferable in other contexts, can possibly be generalized.