Topic

In modern systems the classical modeling paradigm using static graphs may be restrictive or oversimplifying, as the interactions among the elementary system units usually change over time in a highly dynamic manner. For example, friendships are added and removed over time in a social network and links in a communication network may change dynamically, either according to a specific known pattern (satellites following a trajectory) or in an unpredictable manner (mobile ad hoc networks). The common characteristic in all these application areas is that the system structure, i.e. graph topology, is subject to discrete changes over time. In such dynamically changing graphs the notion of vertex adjacency needs to be revisited and various graph concepts, e.g. reachability and connectedness, now crucially depend on the exact temporal ordering of the edges' presence.

A temporal graph is a graph that changes over time. Assuming discrete time and a fixed set V of vertices, a temporal graph can be viewed as a discrete sequence G₁, G₂, ... of static graphs, each with vertex set V. Many notions and algorithms from the static case can be naturally transferred in a meaningful way to their temporal counterpart, while in other cases new approaches are needed to define the appropriate temporal notions. In particular, some problems become radically different and substantially more difficult when the time dimension is additionally taken into account.

In this one-day workshop, recent advances in the area of temporal / dynamically changing graphs will be presented, as well as some of the key challenges will be highlighted.

Presentations are given by invitation only. Everyone is welcome to register and attend.

Practical information

Every presentation is given 30 minutes in total, which is expected to be 25 minutes of talk and 5 minutes of questions. The presentations are grouped into four sessions (two in the morning and two in the afternoon). Details of the schedule can be found below. A participant can register only to the workshop (Monday 9 July), or to both the workshop and the conference (Monday 9 July to Friday 13 July). Early registration is until 31 May.

Full information about the registration to the workshop and/or the conference, as well as about accommodation, is given here:
https://iuuk.mff.cuni.cz/~icalp2018/registration

The workshop is held in the room S9, 1st floor of the building of Charles University, at Malá Strana (Malostranské námestí 2/25, Praha 1).
Please check out this website for more information (including directions, suggestions etc.) about the venue: https://iuuk.mff.cuni.cz/~icalp2018/venue

Workshop Schedule (tentative)

Time	Talk
9:00-9:30	Paola Flocchini (University of Ottawa, Canada) [slides] Decentralized computations by mobile agents in time-varying graphs
9:30-10:00	Arnaud Casteigts (LaBRI and University of Bordeaux, France) [slides] On robust temporal structures in highly dynamic networks
10:00-10:30	Ralf Klasing (CNRS and LaBRI, University of Bordeaux, France) [slides] Computing parameters of sequence-based dynamic graphs
10:30-11:00	Coffee break
11:00-11:30	Christos Zaroliagis (University of Patras, Greece) [slides] An axiomatic approach to time-dependent shortest paths
11:30-12:00	Matthieu Latapy (CNRS and LIP6, Sorbonne Université, France) [slides] Analysis of temporal interactions with link streams and stream graphs
12:00-12:30	Clémence Magnien (CNRS and LIP6, Sorbonne Université, France) [slides] Algorithmic challenges in link streams: the case of clique computations
12:30-14:00	Lunch break
14:00-14:30	Thomas Erlebach (University of Leicester, UK) [slides] Exploration of temporal graphs with bounded degree
14:30-15:00	Eleni Akrida (University of Liverpool, UK) [slides] The temporal explorer who returns to the base
15:00-15:30	Hendrik Molter (Technical University of Berlin, Germany) [slides] On separators in temporal graphs
15:30-16:00	Coffee break
16:00-16:30	Jessica Enright (University of Edinburgh, UK) Reducing reachability in temporal graphs: Part I
16:30-17:00	Kitty Meeks (University of Glasgow, UK) Reducing reachability in temporal graphs: Part II

Abstracts

• 9:00-9:30: Paola Flocchini (University of Ottawa, Canada) [slides]
  Decentralized computations by mobile agents in time-varying graphs

  Abstract: A large literature exists on distributed computations by mobile agents operating in graphs. Typical problems include exploration, map construction, rendezvous, black hole search, network decontamination, etc. On the other hand, little is known when the agents move and compute in time-varying graphs, where topological changes are a natural and frequent occurrence, and most of these studies are centralized and offline.
  
  In this talk I will review recent decentralized online solutions to gathering and exploration in time-varying graphs.

  
  

• 9:30-10:00: Arnaud Casteigts (LaBRI and University of Bordeaux, France) [slides]
  On robust temporal structures in highly dynamic networks

  Abstract: We define a new type of robust structure motivated by a large class of highly dynamic networks, namely those networks where temporal connectivity is recurrently achieved (over an infinite lifetime). Such a regularity forces some of the links to reappear infinitely often, although these links are indistinguishable from the ones that appear finitely many times. The resulting uncertainty gives rise to a new notion of heredity in graph, which we will illustrate through a number of basic properties and two classical problems (MIS and MDS).

  This is a joint work with Swan Dubois, Franck Petit, and John Michael Robson.

  
  

• 10:00-10:30: Ralf Klasing (CNRS and LaBRI, University of Bordeaux, France) [slides]
  Computing parameters of sequence-based dynamic graphs

  Abstract: We present a general framework for computing parameters of dynamic networks which are modeled as a sequence ( G₁, G₂, ..., G_δ ) of static graphs such that G_i = ( V, E_i ) represents the network topology at time i and changes between consecutive static graphs are arbitrary. The framework operates at a high level, manipulating the graphs in the sequence as atomic elements with two types of operations: a "composition" operation and a "test" operation. The framework allows us to compute different parameters of dynamic graphs using a common high-level strategy by using composition and test operations that are specific to the parameter. The resulting algorithms are optimal in the sense that they use only O(δ) composition and test operations, where δ is the length of the sequence. We illustrate our framework with three minimization problems, namely "bounded realization of the footprint", "temporal diameter", and "round trip temporal diameter", as well as with one maximization problem, namely "T-interval connectivity". We prove that the problems are in the class NC by presenting polylogarithmic-time parallel versions of the algorithms. Finally, we show that the algorithms can operate online with amortized complexity Θ(1) composition and test operations for each graph in the sequence.

  This is joint work with Arnaud Casteigts, Yessin M. Neggaz, and Joseph G. Peters.

  
  

• 11:00-11:30: Christos Zaroliagis (University of Patras, Greece) [slides]
  An axiomatic approach to time-dependent shortest paths

  Abstract: Computing shortest paths in networks that exhibit a time-dependent metric is a core routine for many applications. In this talk, we present an axiomatic approach which shows that for directed networks that satisfy certain properties we can provide time-dependent distance oracles that exhibit subquadratic preprocessing time and space (independent of the metric's amount of disconcavity) and query time sublinear on the network size, or the actual Dijkstra rank of the query at hand.

  
  

• 11:30-12:00: Matthieu Latapy (CNRS and LIP6, Sorbonne Université, France) [slides]
  Analysis of temporal interactions with link streams and stream graphs

  Abstract: Money or data transfers, contacts between individuals, or product sales, may all be modeled as temporal interactions. Studying the structure and dynamics of interactions is therefore crucial for many fundamental and applied questions (like event detection in traffic, fraud fighting, recommender systems, network optimisation, and the interplay between relations and interactions). Their structure is studied with graphs and networks (sets of nodes and links); their dynamics is studied with signals and time series (variations of a property over time); to study the dynamics of their structure, one uses graph sequences. However, these approaches poorly capture the both structural and temporal nature of interactions, that calls for a dedicated formalism. I will present a generalization of graphs, that we call link streams and stream graphs, and that makes it possible to consistently handle both aspects. We thus obtain a language for the study of interactions over time, similar to the one provided by graphs for the study of relations.

  
  

• 12:00-12:30: Clémence Magnien (CNRS and LIP6, Sorbonne Université, France) [slides]
  Algorithmic challenges in link streams: the case of clique computations

  Abstract: Link streams model interactions over time as sequences of triplets (t,u,v) meaning that an interaction between u and v occurred at time t. Such interactions may represent financial transactions, network traffic, mobility, sales, contacts, messages, and many other objects of interest. A variety of graph concepts were recently generalized to link streams, and are useful to describe such sequences of interactions. This includes clustering coefficient, k-cores, connected components, closeness, betweenness, and cliques, that raise many algorithmic challenges. I will present in particular our works on clique computations in link streams, which already received much attention. I will also illustrate their relevance in the contexts of network traffic and of contacts between individual analysis.

  
  

• 14:00-14:30: Thomas Erlebach (University of Leicester, UK) [slides]
  Exploration of temporal graphs with bounded degree

  Abstract: For a given temporal graph that is connected in every step, the temporal exploration problem asks for a shortest temporal walk that starts at a given start vertex and visits every vertex of the graph at least once. For temporal graphs with n vertices, it is known that O(n²) steps suffice for an exploration and that Ω(n²) steps are also necessary in the worst case. We consider temporal graphs where the graph in every step has bounded degree. For this case, we show that exploration in o(n²) steps is always possible.

  This is joint work with Jakob Spooner.

  
  

• 14:30-15:00: Eleni Akrida (University of Liverpool, UK) [slides]
  The temporal explorer who returns to the base

  Abstract: We study the problem of exploring a temporal graph (i.e. a graph that changes over time), in the fundamental case where the underlying static graph is a star. The aim of the exploration problem in a temporal star is to find a temporal walk which starts at the center of the star, visits all leafs, and eventually returns back to the center. We initiate a systematic study of the computational complexity of this problem, depending on the number k of time-labels that every edge is allowed to have. To do so, we distinguish between the decision version StarExp(k) asking whether a complete exploration of the instance exists, and the maximization version MaxStarExp(k) of the problem, asking for an exploration schedule of the greatest possible number of edges in the star. We present a collection of results establishing the computational complexity of these two problems.

  This is joint work with George B. Mertzios and Paul G. Spirakis.

  
  

• 15:00-15:30: Hendrik Molter (Technical University of Berlin, Germany) [slides]
  On separators in temporal graphs

  Abstract: Vertex separators, that is, vertex sets whose deletion disconnects two distinguished vertices in a graph, play a pivotal role in algorithmic graph theory. For many realistic models of the real world it is necessary to consider graphs whose edge set changes with time, more specifically, the edges are labeled with time stamps. While there is an extensive literature on separators in “static” graphs, much less is known for the temporal setting. Building on previous work, we study the problem of finding a small vertex set (the separator) in a temporal graph with two designated terminal vertices such that the removal of the set breaks all temporal paths connecting one terminal to the other. Herein, we consider two models of temporal paths: paths that contain arbitrarily many hops per time step (non-strict) and paths that contain at most one hop per time step (strict). Both versions of temporal separation are known to be NP-hard which motivates a parameterized complexity analysis and studying the complexity of the problem on restricted classes of temporal graphs.

  This talk will give an overview of recent results based on joint work with Philipp Zschoche, Till Fluschnik and Rolf Niedermeier.

  
  

• 16:00-17:00: Jessica Enright (Part I; University of Edinburgh, UK) and Kitty Meeks (Part II; University of Glasgow, UK)
  Reducing reachability in temporal graphs

  Abstract: The concept of reachability (i.e. which vertices in a graph can be reached by travelling along edges from a given starting vertex) is central to many applications, including the dissemination of information or the spread of disease through a network. Depending on the application, it might be desirable to increase or decrease the number of vertices that are reachable from any one starting vertex. In most applications, time plays a crucial role: each contact between individuals, represented by an edge, will only occur at certain time(s). The relative timing of edges is clearly crucial in determining the reachability of any vertex in the graph.

  In this pair of talks, we will address the problems of reducing the maximum reachability of any vertex in a given temporal graph by two different means:

  • we can remove a limited number of time-edges (times at which a single edge is active) from the graph, or

  • the number of timesteps at which each edge is active is fixed, but we can change the relative order at which different edges are active (perhaps subject to constraints on which edges must be active simultaneously, or restrictions on the timesteps available for each edge).

  Mostly, we find that these problems are computationally intractable even when very strong restrictions are placed on the input, but we identify a small number of special cases which admit polynomial-time algorithms, and raise a number of open questions.

  This includes some joint work with George B. Mertzios and Viktor Zamaraev.

  
  

Workshop organizers*

• George B. Mertzios (Durham University, UK)

• Paul G. Spirakis (University of Liverpool, UK and University of Patras, Greece)

• Eleni C. Akrida (University of Liverpool, UK)

• Viktor Zamaraev (Durham University, UK)

* Partially supported by the EPSRC grants EP/P020372/1 and EP/P02002X/1, and by the EEE/CS University of Liverpool Initiative NeST.