This workshop is devoted to the memory of Prof. Dr. Rolf Niedermeier,
who has been a great scientist, a dear colleague and a good friend.
Algorithmic Aspects of Temporal Graphs V*
Satellite workshop of ICALP 2022
Paris, France
Monday 4 July 2022
(hybrid event)
|
This workshop is devoted to the memory of Prof. Dr. Rolf Niedermeier, |
|
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 G1, G2, ... 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.
As this research area grows and broadens, our aim is to bring together people from theoretical and practical
communities of temporal graphs in order to establish new and strengthen existing links between these communities.
This workshop is the sequel of the four previous workshops at
ICALP 2018 (in Prague),
ICALP 2019 (in Patras),
ICALP 2020 (online), and
ICALP 2021 (online).
The workshop is planed to run in hybrid mode, i.e. both online on zoom and in-person in Paris. 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 20-25 minutes of talk and 5-10 minutes for questions and change-over.
The presentations are grouped into four sessions (two in the morning and two in the afternoon).
Details of the invited speakers and the schedule can be found below.
The meeting will also be hosted on zoom at the following link:
https://durhamuniversity.zoom.us/j/96357567173?pwd=Mjlta1VBY2c4VERudFNURGJYSllUUT09
(Meeting ID: 963 5756 7173, Passcode: 964974)
For the online participants, we will have the following rules in place for the workshop to run smoothly:
- Please log in to the Zoom meeting using your REAL NAME and AFFILIATION, e.g. "Eleni Akrida, Durham University" or "Eleni Akrida, Durham".
- Please keep your microphone muted unless you would like to speak publicly, e.g. when you ask a question.
- Should you have any questions while a speaker is presenting, please try to not interrupt (unless you think it is necessary).
Instead, please prefer write "Q" (for "Question") or "C" (for "Comment") in the chat.
After the talk is over and it is time for questions, the chair of the session will advise those who have commented to ask their questions.
Video Recording
The video recording of most talks can be found in the following playlist on YouTube:
AATG 2022 YouTube playlist.
The individual slides and videos can be found next to the corresponding speaker in the workshop schedule below.
Information for onsite participants:
Location:
The workshop will be held in the Saint Père site of the Université Paris Cité (not the same place as the main ICALP conference) at: 45, rue des Saints-Pères, 75006 Paris.
Please look for the room 'Avogadro F' on the 2nd floor of the building.
Environmental awareness:
This year, ICALP is promoting environmental awareness, so we ask those of you who will not participate at the main ICALP conference to please return your badges to the designated box after the end of the workshops' day.
Coffee breaks and lunch:
Coffee breaks will be served in the entrance hall. To get to where lunch is served, there will be a short (10') walk to the Tuieleries gardens. There will be volunteers who will guide groups of interested people there. Of course, any participant who doesn't wish to follow can stay in the building. Please be reminded that the rooms do not lock, so please do not leave any valuables in the rooms.
Workshop Schedule: All times below are in Central European Time (CET)
Abstracts
Eduard Eiben (Royal Holloway University of London, UK)
Minimizing Reachability Times on Temporal Graphs via Shifting Labels
Abstract:
We study how we can accelerate the spreading of information in temporal graphs via delaying operations; a problem that captures real-world applications varying from information flows to distribution schedules.
In a temporal graph there is a set of fixed vertices and the available connections between them change over time in a predefined manner. We observe that, in some cases, the delay of some connections can
in fact decrease the time required to reach from some vertex (source) to another vertex (target). We study how we can minimize the maximum time a set of source vertices needs to reach every other vertex of
the graph when we are allowed to delay some of the connections of the graph. For one source, we prove that the problem is W[2]-hard and NP-hard, when parameterized by the number of allowed delays.
On the other hand, we derive a polynomial-time algorithm for one source and unbounded number of delays. This is the best we can hope for; we show that the problem becomes NP-hard when there are two sources
and the number of delays is not bounded. We complement our negative result by providing an FPT algorithm parameterized by the treewidth of the graph plus the lifetime of the optimal solution.
Finally, we provide polynomial-time algorithms for several classes of graphs.
This is a joint work with Argyrios Deligkas and George Skretas.
Nina Klobas (Durham University, UK)
Defining Labeling that Preserves Reachability
Abstract:
We study temporal design problems of undirected temporally connected graphs. The basic setting of these optimization problems is as follows: given an undirected graph G, what is the smallest number of time-labels that we need to add to the edges of G such that the resulting temporal graph is temporally connected? This basic problem, called MINIMUM LABELING, can be optimally solved in polynomial time, thus resolving an open question. The situation becomes however more complicated if we strengthen, or even if we relax a bit, the requirement of temporal connectivity of the temporal graph. One way to strengthen the temporal connectivity requirements is to upper-bound the allowed age (i.e., maximum label) of the obtained temporal graph. On the other hand, we can relax temporal connectivity by only requiring that there exists a temporal path between any pair of ``important'' vertices which lie in a subset R of V, which we call the terminals. This relaxed problem, called MINIMUM STEINER LABELING, resembles the problem STEINER TREE in static (i.e., non-temporal) graphs; however, as it turns out, STEINER TREE is not a special case of MINIMUM STEINER LABELING.
This is a join work with Geroge B. Mertzios, Hendrik Molter, and Paul G. Spirakis.
Thomas Erlebach (Durham Univerity, UK)
Parameterized Temporal Exploration Problems
Abstract:
The temporal exploration problem, which aims at visiting all vertices
of a given temporal graph as quickly as possible, is NP-hard in most
settings. We study parameterized versions of this problem for strict
and non-strict temporal walks. For strict temporal walks, we give
FPT algorithms for the problem of visiting k given vertices or
k arbitrary vertices, parameterized by k. For non-strict temporal
walks, we give an FPT algorithm for visiting all vertices,
parameterized by the lifetime of the graph. We also consider
the case of non-strict temporal exploration with a bounded number
of components in each time step.
This is joint work with Jakob Spooner.
Malte Renken (TU Berlin, Germany)
Temporal Pathfinding in the Presence of Delays
Abstract: Finding paths in temporal graphs has many obvious applications, e.g. in public transport networks. In many of these, delays are unfortunately a constant problem to cope with, especially as they can cause one to miss subsequent links at transfer stations. This creates a need find paths which are robust to some number of (small) delays. An important factor in determining the robustness of a connection is how far in advance delays are announced and whether deviating from the initial route is possible. We consider three different settings: one where delays are known before departure, one where delays occur without prior warning, and one where deviating from the chosen route is impossible (in this case the time at which delays are announced does not matter). In this talk, we look into all three of these cases from an algorithmic perspective and provide results on the (parameterized) complexity.
Hendrik Molter (Ben Gurion University of the Negev, Israel)
Counting Temporal Paths
Abstract:
The betweenness centrality of a vertex v is an important centrality measure that quantifies how many optimal paths between pairs of other vertices visit v.
Computing betweenness centrality in a temporal graph, in which the edge set may change over discrete timesteps, requires us to count temporal paths that are optimal with
respect to some criterion. For several natural notions of optimality, including foremost or fastest temporal paths, this counting problem reduces to #Temporal Path,
the problem of counting all temporal paths between a fixed pair of vertices; like the problems of counting foremost and fastest temporal paths, #Temporal Path is #P-hard in general.
Motivated by the many applications of this intractable problem, we initiate a systematic study of the parameterised and approximation complexity of #Temporal Path.
We show that the problem presumably does not admit an FPT-algorithm for the feedback vertex number of the static underlying graph, and that it is hard to approximate in general.
On the positive side, we proved several exact and approximate FPT-algorithms for special cases.
Based on joint work with Jessica Enright and Kitty Meeks.
Michael Raskin (Technical University of Munich, Germany)
Sharp Thresholds in Random Simple Temporal Graphs
Abstract: We will focus on a simple model of random temporal graphs, having the same parameters n and p as classical Erdös-Rényi graphs. In this model, we characterize various thresholds on temporal reachability as the graph densifies -- in particular, temporal connectivity (the existence of temporal paths between all pairs of vertices) occurs exactly at p = 3 log n / n. Interestingly, it turns out that above this threshold, there also exists temporal spanners of near-optimal size (i.e. 2n+o(n) edges). Among other things, this means that all the known counter-examples to the existence of linear-size spanners are statistically insignificant.
Ana Silva (Federal University of Ceará, Brasil)
Temporal Menger and Related Problems
Abstract: Given a graph G and vertices s and t of G, Menger’s Theorem states that the maximum number of (internally) vertex disjoint s,t-paths is equal to the minimum size of a subset X for which G-X contains no s,t-path. This is a classical result in Graph Theory, taught in most basic Graph Theory courses, and it holds also when G is directed and when edge disjoint paths and edge cuts are considered instead. A direct translation of Menger’s Theorem to the temporal context has been known not to hold since an example was shown in the seminal paper by Kempe, Kleinberg and Kumar (STOC’00). In this talk, an overview of possible temporal versions of Menger’s Theorem will be discussed, as well as the complexity of the related problems.
Samuel Hand (University of Glasgow, UK)
The Temporal Firefighter Problem
Abstract: The Firefighter problem on a static graph asks how to best prevent the vertices of a graph from "burning" when a fire is spreading over the graph. At timestep 0 a vertex begins burning, and then at each subsequent timestep a chosen vertex is defended, before the fire spreads to all adjacent undefended vertices. The problem of determining how many vertices can be saved from the fire in such a process is NP-complete, however several classes of graph have been found for which there are polynomial time solutions. We introduce the problem Temporal Firefighter, an extension of Firefighter to temporal graphs. We show that Temporal Firefighter is also NP-complete, and furthermore remains so on all but one of the underlying classes of graph for which Firefighter is known to have polynomial-time solutions. We then turn our attention to restricting the temporal structure of the graph, finding that Temporal Firefighter is fixed parameter tractable with respect to the temporal graph parameter vertex-interval-membership-width, but remains hard even on trees with at most two edges active per timestep.
Suhas Thejaswi (Aalto University, Finland)
Finding Path Motifs in Temporal Graphs using Algebraic Fingerprints.
Abstract:
We study the problem of detecting and finding temporal patterns in
vertex-colored temporal graphs. In particular, given a vertex-colored temporal
graph and a multiset of colors (query), we search for a temporal path in the
graph such that the vertex colors of the path agree with the multiset of colors
specified in the query. We extend the constrained-multilinear sieving technique
to present polynomial-space FPT-exact algorithms for a family of
pattern-detection problems parameterized by the size of the multiset query. We
present efficient generating functions to answer temporal-reachability queries
under restrictive settings such as waiting-time restrictions as well as vertex
and edge constraints. The presented algorithms are probably optimal for a subset
of temporal path problems and practically scale to large real-world problem
instances with up to one billion temporal edges.
Joint work with Aristides Gionis and Juho Lauri.
Pierluigi Crescenzi (Gran Sasso Science Institute, Italy)
On Making Graphs Temporally (In)Efficient
Abstract:
A typical question that has been considered in the literature in the field of network optimisation consists in finding the graph modification which maximises or minimises a specific optimisation criterion (often connected to the notion of reachability and distance between nodes). Recently, this kind of problems has been analysed also in the case of temporal graphs, that is, graphs whose topology changes over time. For instance, the problem of deleting edges from a given temporal graph in order to reduce its temporal reachability, the problem of assigning the appearing time to the edges of a graph in order to minimise the temporal reachability of the resulting temporal graph, or the problem of minimising the average temporal reachability in a temporal graph by delaying some edges, have been considered. In this talk we first briefly review these results and we then consider the problem of assigning appearing times to the edges of a digraph in order to maximize the (average) temporal reachability between pairs of nodes.
Motivated by the application to public transit networks, where edges cannot be scheduled independently one of another, we consider the setting where the edges are grouped into certain walks (called trips) in the digraph and where assigning the appearing time to the first edge of a trip forces the appearing times of the subsequent edges. In this setting, we show that, quite surprisingly, it is NP-complete to decide whether there exists a time assignment connecting a given pair of nodes. This result allows us to prove that the problem of maximising the temporal reachability cannot be approximated within a factor better than some polynomial term in the size of the graph. We thus focus on the case where, for each pair of nodes, there exists a time assignment such that one node is reachable from the other. We call this property strong temporalisability. It is a very natural assumption for the application to public transit networks.
On the negative side, the problem of maximising the temporal reachability remains, in that setting, hard to approximate within a factor proportional to the square root of the number of nodes. Moreover, we show the existence of collections of trips that are strongly temporalisable but for which any time assignment connects at most a fraction of all pairs of nodes proportional to the inverse of the square root of the number of nodes. On the positive side, we show that there must exist a time assignment that connects a constant fraction of all pairs in the strongly temporalisable and symmetric case, that is, when the set of trips to be scheduled is such that, for each trip, there is a symmetric trip visiting the same nodes in reverse order. We conclude with the main problem left open by our results, that is, whether the case of single edge trips (which is still NP-hard) can be approximated in polynomial time.
This is a joint work with Filippo Brunelli and Laurent Viennot.
Andrea Marino (University of Florence, Italy)
On Computing the Diameter of (Weighted) Link Streams
Abstract: A weighted link stream is a pair (V,E) comprising V, the set of nodes, and E, the list of temporal edges (u,v,t,\lambda), where u,v are two nodes in V, t is the starting time of the temporal edge, and \lambda is its travel time. By making use of this model, different notions of diameter can be defined, which refer to the following distances: earliest arrival time, latest departure time, fastest time, and shortest time. After proving that any of these diameters cannot be computed in time sub-quadratic with respect to the number of temporal edges, we propose different algorithms (inspired by the approach used for computing the diameter of graphs) which allow us to compute, in practice very efficiently, the diameter of quite large real-world weighted link stream for several definitions of the diameter. In the case of the fastest time distance and of the shortest time distance, we introduce the notion of pivot-diameter, in order to deal with the fact that temporal paths cannot be concatenated in general. The pivot-diameter is the diameter restricted to the set of pairs of nodes connected by a path which passes through a pivot (that is, a node at a given time instant). We prove that the problem of finding an optimal set of pivots, in terms of the number of pairs connected, is NP-hard, and we propose and experimentally evaluate several simple and fast heuristics for computing ``good'' pivot sets.
Nicola Santoro (Carleton University, Canada)
On Cop & Robber in a Periodic Temporal Graph
Abstract:
A temporal graph G is (usually represented as) a possibly infinite
sequence of graphs, G= (G(0),G(1),G(2)...), where G(t) denotes the
topology of G at time t. Problem solving by mobile computational
entities operating in a temporal graph G is an intensively
investigated research area, where the focus has been almost
exclusively on cooperating entities.
In this talk we consider instead competitive entities in a temporal
graph, focusing in particular on the well known two-players
pursue-evasion game of Cop & Robber, played in discrete rounds.
Thus, in round i, the players are in G(i) and, first the cop and
then the robber, make their decisions and moves, and they find
themselves in G(i+1) in the next round. The cop wins iff both players
are in the same node in some round
Knowing the changes beforehand, can the cop still find a winning
strategy or the robber forever avoid capture? Under what conditions
G is copwin? This talk will address some of these questions and
the issues that they raise, focusing in particular on periodic
temporal graphs.
This is based on joint work with Jean-Lou de Carufel, Paola Flocchini,
and Frederic Simard.
George B. Mertzios (Durham University, UK)
Paul G. Spirakis (University of Liverpool, UK and University of Patras, Greece)
Eleni C. Akrida (Durham University, UK)
Viktor Zamaraev (University of Liverpool, UK)
* Partially supported by the EPSRC grants EP/P020372/1 and EP/P02002X/1, and by the EEE/CS University of Liverpool Initiative NeST.