Keynote Speakers

Fabian Kuhn, Albert-Ludwigs-Universität

Title:Deterministic Rounding: An Algorithmic Tool for Efficient Deterministic Distributed Symmetry Breaking

Abstract: The problem of obtaining fast deterministic algorithms for distributed symmetry breaking problems in graphs has long been considered one of the most challenging problems in the area of distributed graph algorithms. Consider for example the distributed coloring problem, where a (computer) network is modeled by an arbitrary graph G = (V,E) and the objective is to compute a vertex coloring of G by running a distributed algorithm on the graph G. It is maybe not surprising that randomization can be a helpful tool to efficiently compute such a coloring. As long as each node v in V can choose among deg(v)+1 different colors, even an almost trivial algorithm in which all nodes keep trying a random available color allows to color all nodes in O(log n) parallel steps. In some cases, it might however be preferable to have a deterministic solution. How to obtain a similarly efficient deterministic algorithm is far less obvious. In fact, for a long time, there has been an exponential gap between the time complexities of the best randomized and the best deterministic distributed algorithms for various graph coloring variants and many other basic graph problems. In the last few years, there however has been substantial progress and we now have deterministic distributed graph algorithms that are nearly as fast as the classic randomized algorithms for the same tasks.

After giving a short overview on the history of the problem of finding fast deterministic algorithms for distributed symmetry breaking problems, we will discuss a concrete, novel distributed derandomization technique that in many cases leads to particularly efficient and also particularly simple deterministic distributed algorithms. One interprets a given randomized algorithm (with certain nice properties) as a fractional relaxation of the problem at hand. This fractional solution is then gradually rounded to an integral solution that approximately preserves the expected quality of the initial randomized algorithm. The method leads to the current fastest deterministic algorithms for various important distributed graph problems.

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.