Sophia Heck (University of Vienna, Austria)
New approximations for temporal vertex cover on always star temporal graphs
Abstract:
Modern networks are highly dynamic, and temporal graphs capture these changes through discrete edge appearances
on a fixed vertex set, known in advance up to the graph's lifetime. The Vertex Cover problem extends to the temporal
setting as Temporal Vertex Cover (TVC) and Sliding Window Temporal Vertex Cover (SW-TVC). In TVC, each edge is covered
by one endpoint over the lifetime, while in SW-TVC, edges are covered within every \(\Delta\)-step window.
In always star temporal graphs, each snapshot is a star with a center that may change at each time step.
TVC is NP-complete on always star temporal graphs, but an FPT algorithm parameterized by \(\Delta\) solves it
optimally in \(O(T \Delta (n+m) \cdot 2 \Delta)\).
This paper presents two polynomial-time approximation algorithms for SW-TVC on always star temporal graphs,
achieving \(2\Delta-1\) and \(\Delta-1\) approximation ratios with running times \(O(T)\) and \(O(Tm \Delta^2)\), respectively.
These algorithms provide exact solutions for \(\Delta=1\) and \(\Delta <= 2\). Additionally, we offer the first
implementation and experimental evaluation of state-of-the-art approximation algorithms with \(d\) and \(d-1\) approximation
ratios, where d is the maximum degree of any snapshot. Our experiments on artificially generated always star temporal
graphs show that the new approximation algorithms outperform the known d-1 approximation in running time,
even in some cases where \(\Delta > d\). We test state-of-the-art algorithms on real-world data and observe that
the \(d-1\) approximation algorithm outperforms the analytically better d approximation algorithm in running time
when implemented as described in the original paper. However, a novel implementation of the \(d\) approximation
algorithm significantly improves its runtime, surpassing \(d-1\) in practice. Nonetheless, the \(d-1\) approximation
consistently computes smaller solutions.
Ella Yates (XXX)
Temporal role colouring
Abstract:
A role colouring of a graph \(G\) is an assignment of colours to the vertices of \(G\) such that two vertices of the
same colour have identical sets of colours in their neighbourhoods. For a fixed graph \(R\) the \(R\)-role colouring
problem asks whether \(G\) has a role colouring that is consistent with the adjacencies of \(R\). More formally, it asks
if there exists a vertex mapping \(r: V(G) \rightarrow V(R)\), such that \(r(N_G(u))=N_R(r(u))$ for all $u \in V(G)\).
We define an extension of the \(R\)-role colouring problem to temporal graphs. Temporal roles are defined via an automaton
with states capturing both the current colour of a vertex and information about its temporal adjacencies. Transitions
between these states are labelled with subsets of colours: allowing a vertex \(v\) to move to a new state at time \(t\) along
an arc labelled with the colours \(C'\) if the set of colours appearing on neighbours of \(v\) at time \(t\) is precisely \(C'\).
For a given automaton \(A\) and temporal graph \(\mathcal{G}\) the \(A\)-role colouring problem asks if there is a colouring
of \(\mathcal{G}\) where every vertex has an accepting path through the automaton.
We show, by a reduction from the static problem, that the \(A\)-role colouring problem is NP-complete. To contend
with this intractability, we explore parameters where this problem can be solved more efficiently. We give fpt
results with respect to each of: the vertex-interval-membership width of the temporal graph, the tree-interval-membership
width of the temporal graph, and the treewidth of the underlying graph, each in combination with the number of states of the automaton.
Jonas Sauer (University of Bonn, Germany)
Journey planning in public transportation networks: An application of temporal graph reachability
Abstract: One of the most commonplace applications of temporal graph algorithms is journey planning in public transportation networks, where the schedule-based nature of the network introduces a temporal aspect. Interactive journey planning applications are used by many of us on a daily basis. These impose challenging requirements on the underlying algorithms: journeys should be found in a matter of milliseconds, even on continental-sized networks, while optimizing multiple criteria. Past research on this problem has rarely made the connection to temporal graphs explicit. Instead, it is still often seen as an extension of the more well-studied shortest path problem in road networks, even though the employed algorithmic methods are quite different. In this talk, I will outline why public transit journey planning is more closely related to temporal graph reachability than it is to shortest paths, even in the multicriteria setting. I will then give a brief overview on recent developments in the field.
Nils Morawietz (University of Jena, Germany)
On the hardness of finding temporally connected subgraphs of any size
Abstract:
Temporal graphs are graphs whose edges are only present at certain points in time. Reachability in these graphs relies
on temporal paths, where edges are traversed chronologically. A temporal graph that offers all-pairs reachability is said
to be temporally connected (or TC). For temporal graphs that are not TC, a natural question is whether they admit a TC subgraph
(a.k.a. closed temporal component) of a given size \(k\). This question was one of the earliest in the field, shown to be NP-hard
by Bhadra and Ferreira in 2003.
We strengthen this result dramatically, showing that deciding if a TC subgraph exists on at least 3 vertices is
already NP-hard in all the standard temporal graph settings (directed/undirected and strict/non-strict through simple
and proper reductions). This implies a strong separation between closed temporal components and open temporal components
(where temporal paths can travel outside the component), for which inclusion-maximal components can be found in polynomial time.
As a by-product, our reductions strengthen a number of existing results and establish new derived results. They imply
that the size of the largest TC subgraph cannot be approximated within a factor of \((1-\epsilon)n\) in directed graphs,
and within a factor of \((1-\epsilon)n/2\) in undirected graphs.
One of the reductions also completes the complexity landscape for TC subgraphs of size exactly \(k\) when parameterized
by \(k\) (answering the missing non-strict case). Finally, on the structural side, our results imply that there exist
arbitrarily large TC graphs of constant lifetime without nontrivial TC subgraphs, and we also show that there exist TC graphs
of arbitrary girth, both facts being of independent interest.
(Joint work with Arnaud Casteigts and Christian Komusiewicz).
Andrea Marino (University of Florence, Italy)
Enumerating spanners in temporal graphs
Abstract:
A spanner of a temporal graph is a subset of edges that preserves connectivity over time between vertices.
A minimal spanner is a spanner in which no edges can be removed without breaking this connectivity.
Our focus is on enumerating minimal spanners for a given temporal graph. We explore several variations of this
problem based on the type of connectivity considered, ranging from one-to-all connectivity to one-to-all-to-one,
many-to-all, and finally all-to-all connectivity. We establish that these problems become progressively harder:
(i) We present a polynomial-time delay algorithm for one-to-all connectivity; (ii) We prove Dual-hardness for both
one-to-all-to- one and many-to-all connectivity, even in the restricted case of two-to-all; (iii) Finally,
for all- to-all connectivity, we show that enumeration cannot be done in output-polynomial time unless 𝖯 = 𝖭𝖯.
We also show that these results hold regardless of whether temporal paths use strictly increasing or non-decreasing times.
Joint work with: Lapo Cioni, Kazuhiro Kurita, Jason Schoeters, and Takeaki Uno.
Paul Bastide (University of Oxford, UK)
Exploring temporal graphs
Abstract:
A temporal graph G is a sequence of graphs \(G_1, G_2, ... , G_t\) on the same vertex set. In this talk, we are interested in
the analogue of the Travelling Salesman Problem for temporal graphs. It is referred to in the literature as the Temporal
Exploration Problem, and asks for the minimum length of an exploration of the graph, that is, a sequence of vertices such
that at each time step \(t\), one either stays at the same vertex or moves along a single edge of \(G_t\).
One natural and still open case is when each graph \(G_t\) is connected and has bounded maximum degree. We present a
short proof that any such graph admits an exploration in \(O(n^{3/2} log n^{1/2})\) time steps. In fact, we deduce
this result from a more general statement by introducing the notion of average temporal maximum degree.
This more general statement improves the previous best bounds, under a unified approach, for several studied exploration problems.
This is based on joint work with Carla Groenland, Lukas Michel and Clément Rambaud.
Hendrik Molter (Hasso Plattner Institute, Germany)
Minimum temporal spanners in happy graphs
Abstract:
Temporal graphs have edge sets that change over discrete time steps. Such graphs are temporally connected (TC)
if all pairs of vertices can reach each other using paths that traverse the edges in a time-respecting way (temporal paths).
Given a TC temporal graph it, a natural question is to find a minimum spanning subgraph of it that preserves temporal connectivity.
These structures, known as temporal spanners, are fundamental and their properties (especially size) have been studied thoroughly
in the past decade. In particular, the problem of minimizing the size of a temporal spanner is known to be hard. However,
the existing results establish hardness for several incomparable settings and versions of the problem.
In this article, we unify and strengthen these results by showing that this problem is NP-hard even on temporal graphs
that are simple and proper (also known as "happy"), i.e., where every edge appears only one time, and a vertex cannot be
incident to several edges simultaneously. Proving hardness in this extremely restricted setting implies, at once, that the
problem is NP-hard for all the previously considered settings and versions of the problem, resolving Open Question 4 in
[Casteigts et al. TCS, 2024]. We also initiate the parameterized study of this problem, showing that in the happy setting,
the problem can be solved in polynomial time if the underlying graph has a constant-size vertex cover, this result being
actually the first positive result on temporal spanners in general. We also show that in the non-happy setting, the problem
is W[1]-hard when parameterized by the feedback vertex number of the underlying graph.
Joint work with Arnaud Casteigts and Meirav Zehavi.
Antonio Fernández Anta (IMDEA Networks Institute, Madrid, Spain)
Tracking the evolution of dynamic networks with indirect sampling
Abstract: We have explored how indirect sampling can be used to estimate the size of subpopulations in a static network. In this presentation we will show results that illustrate how it can also be used to track the evolution of the subpopulations in a dynamic network. We will consider different forms of sampling and estimators. We will illustrate the techniques to track the evolution of a structured peer-to-peer network.
Fabio Vandin (XXX)
Efficient approximate temporal triangle counting in streaming with predictions
Abstract:
Triangle counting is a fundamental problem in both static and temporal graphs. Although it has been extensively studied,
existing exact and approximate algorithms still struggle to handle large-scale temporal graphs. In this talk, I will
introduce STEP, a scalable algorithm for approximating temporal triangle counts from a stream of temporal edges. STEP
combines predictions (about the number of triangles a temporal edge is involved in) with a simple sampling strategy, leading
to scalability, efficiency, and accurate approximation of all temporal triangle types simultaneously.
Our theoretical results show that, by using a sublinear amount of memory, STEP provides unbiased and accurate estimates,
and that its estimates remain robust and of high quality even with reasonably noisy predictions. Extensive experiments on
massive temporal graphs with up to billions of edges show that STEP produces high-quality estimates and is more efficient
than state-of-the-art methods.
This is joint work with Giorgio Venturin and Ilie Sarpe.
Davide Bilò (University of L'Aquila, Italy)
Data structures for temporal queries on dynamic temporal graphs
Abstract:
Temporal graphs provide a natural framework for modeling networks whose connectivity evolves over time.
A central challenge in this setting is the design of efficient data structures capable of supporting temporal-path
queries while the underlying network undergoes updates.
We present recent advances in the design of data structures that support temporal queries on dynamic temporal
graphs under a variety of update operations. The queries considered include temporal reachability, earliest-arrival,
latest-departure, and fastest-path queries. More precisely, we obtain trade-offs among space usage, query time, and update time.
The presented results establish efficient solutions for several classes of temporal graphs, including temporal trees and forests,
while also highlighting lower bounds and open problems in the area.
Henry Austin (Durham University, UK)
Structural thresholds in doubly random temporal graphs
Abstract:
In this talk we discuss the emergence of thresholds in random temporal graphs generalising the popular Random Simple Temporal Graph model.
In particular, we consider the so-called Doubly Random Temporal Graph model where the number of time labels on each edge is drawn
independently at random from some (almost) arbitrary distribution, and the appearance time of each label is then sampled uniformly
at random. We consider phase transitions in the emergence of two forms of structure, one global and one more local. Locally,
we consider the existence of fixed delta-temporal motifs, a natural time bounded analogue of static subgraphs. Globally,
we consider the higher order connectivity of the network, characterised by the maximum time required for a reachability ball
to double in size. In both cases we find sharp thresholds.
This talk is based on joint work with George Mertzios and Paul Spirakis.
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.