**Algorithmic Aspects of Temporal Graphs VII***

Satellite workshop of ICALP 2024

Tallinn, Estonia

Sunday 7 July 2024

**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_1, G_2, \ldots\) 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.

The topic of the workshop is of high interest and relevance to ICALP track A, as it mainly focuses on algorithms and computational complexity,
but it can also straddle to parameterized complexity, structural graph theory, combinatorial optimization, distributed and mobile computing,
as well as randomness in computation.

This workshop is the sequel of the six previous workshops at
ICALP 2023 (in Paderborn and online, hybrid mode),
ICALP 2022 (in Paris and online, hybrid mode),
ICALP 2021 (online),
ICALP 2020 (online),
ICALP 2019 (in Patras), and
ICALP 2018 (in Prague).

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 speakers and the schedule will be announced over time.

For those who cannot attend in person, the meeting will also be hosted on zoom at the following link:

**https://durhamuniversity.zoom.us/j/93457538321**

To receive the password for the zoom session (and any further information), **please register** as soon as possible (with your name and email address) using this link:
**https://forms.gle/4xRWYrAzML37C2WS9**

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**

**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*hidden population where privacy is important or the hidden population is hard to reach. Examples include estimating casualties in an earthquake, conditions among fe- male sex workers, and the prevalence of drug use and infectious diseases. The Network Scale-up Method (NSUM) is the classical approach to developing esti- mates from indirect surveys, but it was designed for one-shot surveys. Further, it requires certain assumptions and asking for or estimating the number of individ- uals in each respondent’s network. In recent years, surveys have been increasingly deployed online and can collect data continuously (e.g., COVID-19 surveys on Facebook during much of the pandemic). Conventional NSUM can be applied to these scenarios by analyzing the data independently at each point in time, but this misses the opportunity of leveraging the temporal dimension. We propose to use the responses from indirect surveys collected over time and develop analyti- cal tools (i) to prove that indirect surveys can provide better estimates for the trends of the hidden population over time, as compared to direct surveys and (ii) to identify appropriate temporal aggregations to improve the estimates. We demonstrate through extensive simulations that our approach outperforms tra- ditional NSUM and direct surveying methods. We also empirically demonstrate the superiority of our approach on a real indirect survey dataset of COVID-19 cases.

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.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)

The video recording of most talks will be found on a dedicated playlist on YouTube.

The video playlist on YouTube for the previous year (2023) is here:
AATG 2023 YouTube playlist.

**Workshop Schedule (tentative):** All times below are in **Central European Time (CET)**

**Abstracts**

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