Laurent Viennot (INRIA, France)
Temporalizing multi-digraphs
Abstract:
Temporalizing a multi-diraph consists in assigning a single time label to each edge so as to maximize the number of
pairs of vertices that are temporally connected in the resulting temporal graph. We will focus on the case where
the input is a strong digraph and where constant approximation can be obtained. For this, we construct a linear size
balanced bi-tree T (an out-tree and an in-tree with same size, same root, and disjoint sets of non-root nodes).
More precisely, T can be computed in quadratic time (in the number of vertices) and has size at least n/3.
A temporalization connecting a constant fraction of all pairs can easily be deduced from it.
The construction involves a particular depth-first search tree (Left-maximal DFS) of independent interest,
and shows that every strongly connected directed graph has a balanced directed separator which is a circuit.
This is a joined work with Alkida Balliu, Stéphane Bessy, Filippo Brunelli, Pierluigi Crescenzi, Dennis Olivetti and Stéphan Thomassé.
John Sylvester (University of Liverpool, UK)
Temporal exploration of random spanning tree models
Abstract:
In this talk we will consider the temporal exploration problem (TEXP) on two random models of temporal graphs which are connected
in each time step. TEXP asks for a walk in a given temporal graph that visits all vertices, and which finishes at the earliest time
amongst all such walks. It is known that there are $n$-vertex temporal graphs which require \Omega(n^2) steps to explore,
our aim is to explore what happens against a random adversary.
In the first model an adversary supplies a measure \mu supported on a set of (labelled) spanning trees of a static graph G,
and we obtain a (random) temporal graph by sampling a spanning tree from \mu at each time step.
We show that, for any pair (\mu, G), there is a schedule which explores the corresponding temporal graph in expected time O(|E(G)|).
Furthermore we provide an example of pair (\mu, G) which require a super-linear number of steps to explore in expectation.
The second model we consider is an unlabeled variant of the first, where an adversary supplies a set S of n-vertex trees and each step
is a uniform random permutation of a tree from S. We show that, for any set S, with high probability the time to explore the corresponding
temporal graph lies between \Omega(n) and O(n\log n), and we provide instances where both bounds are tight.
This is joint work with Samuel Baguley, Andreas Göbel, Nicolas Klodt, George Skretas and Viktor Zamaraev.
Jessica Enright (University of Glasgow, UK)
Structural parameters for dense temporal graphs
Abstract:
Temporal graphs provide a useful model for many real-world networks. Unfortunately the majority of algorithmic problems we might consider on
such graphs are intractable. There has been recent progress in defining structural parameters which describe tractable cases by simultaneously
restricting the underlying structure and the times at which edges appear in the graph. These all rely on the temporal graph being sparse in some sense.
We introduce temporal analogues of three increasingly restrictive static graph parameters -- cliquewidth, modular-width and neighbourhood
diversity -- which take small values for highly structured temporal graphs, even if a large number of edges are active at each timestep.
The computational problems solvable efficiently when the temporal cliquewidth of the input graph is bounded form a subset of those solvable
efficiently when the temporal modular-width is bounded, which is in turn a subset of problems efficiently solvable when the temporal
neighbourhood diversity is bounded. By considering specific temporal graph problems, we demonstrate that (up to standard complexity
theoretic assumptions) these inclusions are strict.
Joint work with: Kitty Meeks, Sam Hand, Laura Larios-Jones.
Thomas Erlebach (Durham University, UK)
Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization
Abstract:
In the periodic temporal graph realization problem introduced by Klobas et al. (SAND 2024) one is given a period $\Delta$
and an $n\times n$ matrix $D$ of desired fastest travel times, and the task is to decide if there is a simple periodic temporal graph
with period $\Delta$ such that the fastest travel time between any pair of vertices matches the one specified by $D$.
We generalize the problem from simple temporal graphs to temporal graphs where each edge can appear up to $\ell$ times in each period,
for some given integer $\ell$. For the resulting problem Multi-Label Periodic TGR, we show that it is fixed-parameter tractable for
parameter $n$ and for parameter $vc+\Delta$, where $vc$ is the vertex cover number of the underlying graph.
We also show the existence of a polynomial kernel for parameter $k+d_{max}$, where $k$ is the number of non-universal vertices
of the underlying graph and $d_{max}$ is the largest entry of $D$. Furthermore, we show that the problem is NP-hard for each $\ell \geq 5$,
even if the underlying graph is a tree, a case that was known to be solvable in polynomial time if the task is to
construct a simple periodic temporal graph, that is, if $\ell = 1$.
This is joint work with Nils Morawietz and Petra Wolf.
Nils Morawietz (University of Jena, Germany)
Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs
Abstract: A temporal graph is a graph whose edges only appear at certain points in time. Reachability in these graphs is defined in terms of paths that traverse the edges in chronological order (temporal paths). This form of reachability is neither symmetric nor transitive, the latter having important consequences on the computational complexity of even basic questions, such as computing temporal connected components. In this paper, we introduce several parameters that capture how far a temporal graph G is from being transitive, namely, vertex-deletion distance to transitivity and arc-edit distance to transitivity, both being applied to the reachability graph of G. We illustrate the impact of these parameters on the temporal connected component problem, obtaining several tractability results in terms of fixed-parameter tractability and polynomial kernels. Significantly, these results are obtained without restrictions of the underlying graph, the snapshots, or the lifetime of the input graph. As such, our results isolate the impact of non-transitivity and confirm the key role that it plays in the hardness of temporal graph problems.
Andrea Marino (University of Florence, Italy)
On computing large temporal (unilateral) connected components
Abstract:
A temporal (directed) graph is a graph whose edges are available only at specific times during its lifetime, \tau.
Paths are sequences of adjacent edges whose appearing times are either strictly increasing or non-strictly increasing
(i.e., non-decreasing), depending on the scenario. The classical concept of connected components and also of unilateral
connected components in static graphs naturally translate to temporal graphs in several non-equivalent ways.
In this talk, we adress the following fundamental questions in temporal graphs. (i) What is the complexity of deciding
the existence of a component of size k, parameterized by \tau, by k, and by k+\tau? We show that this question
has a different answer depending on the considered definition of component and whether the temporal graph is
directed or undirected. (ii) What is the minimum running time required to check whether a subset of vertices are pairwise reachable?
A quadratic-time algorithm is known but, contrarily to the static case, a better running time is unlikely unless SETH fails.
(iii) Is it possible to verify whether a subset of vertices is a component in polynomial time? We show that depending on the
definition of temporal component this test is NP-complete.
Hendrik Molter (Ben-Gurion University of the Negev, Israel)
Realizing temporal transportation trees
Abstract:
This talk deals with the complexity of the periodic temporal graph realization problem with respect to upper bounds on the fastest path durations
among its vertices. This constraint with respect to upper bounds appears naturally in transportation network design applications where, for example,
a road network is given, and the goal is to appropriately schedule periodic travel routes, while not exceeding some desired upper bounds on the travel times.
This approach is in contrast to verification applications of the graph realization problems, where exact values for the distances
(respectively, fastest travel times) are given, following some kind of precise measurement. We focus only on underlying tree topologies,
which are fundamental in many transportation network applications. As it turns out, the periodic upper-bounded temporal tree realization
problem has a very different computational complexity behavior than both (i) the classic graph realization problem with respect to shortest
path distances in static graphs and (ii) the periodic temporal graph realization problem with exact given fastest travel times
(which was recently introduced).
Based on joint work with George B. Mertzios and Paul G. Spirakis.
Lutz Oettershagen (KTH Royal Institute of Technology, Sweden)
A higher-order temporal H-index for evolving networks
Abstract:
The H-index of a node in a static network is the maximum value h such that at least h of its neighbors have a degree of at
least h (J E Hirsch, 2005). Recently, a generalized version, the n-th order H-index, was introduced, allowing to relate
degree centrality, H-index, and the k-core of a node (Lü et al., 2016). We extend the n-th order H-index to temporal networks
and define corresponding temporal centrality measures and temporal core decompositions. Our n-th order temporal H-index respects
the reachability in temporal networks leading to node rankings, which reflect the importance of nodes in spreading processes.
We derive natural decompositions of temporal networks into subgraphs with strong temporal coherence.
We analyze a recursive computation scheme and develop a highly scalable streaming algorithm.
Our experimental evaluation demonstrates the efficiency of our algorithms and the conceptional validity of our approach.
Specifically, we show that the n-th order temporal H-index is a strong heuristic for identifying possible super-spreaders
in evolving social networks and detects temporally well-connected components.
Joint work with Nils M. Kriege and Petra Mutzel (https://dl.acm.org/doi/10.1145/3580305.3599242).
George Skretas (Hasso Plattner Institute, Potsdam, Germany)
How to reduce temporal cliques to find sparse spanners
Abstract:
Many real-world networks, like transportation networks and social networks, are dynamic in the sense that the edge set may change over time,
but these changes are known in advance. This behavior is captured by the temporal graphs model, which has recently become a trending topic in
theoretical computer science. A core open problem in the field is to prove the existence of linear-size temporal spanners in temporal cliques,
i.e., sparse subgraphs of complete temporal graphs that ensure all-pairs reachability via temporal paths. So far, the best-known result is the
existence of temporal spanners with O(n log n) many edges. We present significant progress towards proving that linear-size temporal spanners
exist in all temporal cliques.
We adapt techniques used in previous works and heavily expand and generalize them. This allows to show that the existence of a linear spanner
in cliques and bi-cliques is equivalent and also provide a simpler and more intuitive proof of the O(n log n) bound. Moreover, we use our novel
approach to show that a large class of temporal cliques, called edge-pivotable graphs, admit linear-size temporal spanners. To contrast this,
we investigate other classes of temporal cliques that do not belong to the class of edge-pivotable graphs. We introduce two such graph classes
and we develop novel techniques for establishing the existence of linear temporal spanners in these graph classes as well.
Joint work with: Sebastian Angrick, Ben Bals, Hans Gawendowicz, Niko Hastrich, Nicolas Klodt, Pascal Lenzer, Jonas Schmidt and Armin Wells.
Dibyayan Chakraborty (University of Leeds, UK)
Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
Abstract:
In this presentation, we shall talk about a dynamic analogue of the Path Cover problem, which can be solved in polynomial-time in
directed acyclic graphs. A temporal digraph has an arc set that changes over discrete time-steps, if the underlying digraph
(the union of all the arc sets) is acyclic, then we have a temporal DAG. A temporal path is a directed path in the underlying digraph,
such that the time-steps of arcs are strictly increasing along the path. Two temporal paths are temporally disjoint if they do not occupy
any vertex at the same time. A temporal (resp. temporally disjoint) path cover is a collection of (resp. temporally disjoint)
temporal paths that covers all vertices.
We study the computational complexities of the problems of finding a temporal (disjoint) path cover with minimum cardinality,
denoted as Temporal Path Cover (TPC) and Temporally Disjoint Path Cover (TD-PC). We show that both problems are NP-hard even
when the underlying DAG is planar, bipartite, subcubic, and there are only two arc-disjoint time-steps. Moreover, TD-PC remains
NP-hard even on temporal oriented trees. In contrast, we show that TPC is polynomial-time solvable on temporal oriented trees
by a reduction to Clique Cover for (static undirected) weakly chordal graphs (a subclass of perfect graphs for which Clique Cover
admits an efficient algorithm). This highlights an interesting algorithmic difference between the two problems. Although it is
NP-hard on temporal oriented trees, TD-PC becomes polynomial-time solvable on temporal oriented lines and temporal rooted directed trees.
We also show that TPC (resp. TD-PC) admits an XP (resp. FPT) time algorithm with respect to parameter tmax + tw, where tmax is the maximum
time-step, and tw is the treewidth of the underlying static undirected graph.
Antonio Fernandez Anta (IMDEA Networks Institute, Madrid, Spain)
Nowcasting temporal trends using indirect surveys
Abstract:
Indirect surveys, in which respondents provide information about other people
they know, have been proposed for estimating (nowcasting) the size of a
This is a joint work of Ajitesh Srivastava, Juan Marcos Ramirez, Sergio Dıaz-Aranda, Jose Aguilar,
Antonio Fernandez Anta, Antonio Ortega, and Rosa E. Lillo.
Part of project TED2021-131264B-I00 (SocialProbing) funded by MCIN/AEI/10.13039/501100011033/ and the European Union-NextGenerationEU/PRTR.
Workshop organizers*
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.