Riccardo Dondi (University of Bergamo, Italy)
Covering timeline in temporal graphs: Complexity and algorithms
Abstract: We consider a variant of vertex cover on temporal graphs that has been recently defined for the summarization of timeline activities. The problem asks for the definition of an activity interval for each vertex so that for each edge at least one of its endpoints is active when it is observed. The problem is NP-hard even for a time domain that consists of two timestamps. We discuss novel contributions on the computational complexity of the problem that show its NP-hardness for restricted instances. On the positive side, we present approximation and fixed-parameter algorithms, both for the general problem and the restriction where at most one temporal edge is defined in each timestamp.
Davide Bilò (University of Sassari, Italy)
Temporal network creation games
Abstract:
Most networks are not static objects, but instead they change over time. This observation has sparked rigorous research
on temporal graphs within the last years. In temporal graphs, we have a fixed set of nodes and the connections between them
are only available at certain time steps. This gives rise to a plethora of algorithmic problems on such graphs, most
prominently the problem of finding temporal spanners, i.e., the computation of subgraphs that guarantee all pairs reachability
via temporal paths. To the best of our knowledge, only centralized approaches for the solution of this problem are known.
However, many real-world networks are not shaped by a central designer but instead they emerge and evolve by the interaction
of many strategic agents. This observation is the driving force of the recent intensive research on game-theoretic network formation models.
In this talk we bring together these two recent research directions: temporal graphs and game-theoretic network formation.
As a first step into this new realm, we focus on a simplified setting where a complete temporal host graph is given and the agents,
corresponding to its nodes, selfishly create incident edges to ensure that they can reach all other nodes via temporal paths in the
created network. This yields temporal spanners as equilibria of our game.
We present results on the convergence to and the existence of equilibrium networks, on the complexity of finding best agent
strategies, and on the quality of the equilibria. By taking these first important steps, we uncover challenging open problems
that call for an in-depth exploration of the creation of temporal graphs by strategic agents.
Luciano Gualà (University of Rome Tor Vergata, Italy)
Sparse temporal spanners with low stretch
Abstract:
A temporal graph is an undirected graph \(G=(V,E)\) along with a function \(\lambda : E \to \mathbb{N}^{+}\)
that assigns a time-label to each edge in \(E\). A path in \(G\) such that the traversed time-labels are non-decreasing
is called a temporal path. Accordingly, the distance from \(u\) to \(v\) is the minimum length (i.e., the number of edges)
of a temporal path from \(u\) to \(v\). A temporal \(\alpha\)-spanner of \(G\) is a (temporal) subgraph \(H\) that preserves
the distances between any pair of vertices in \(V\), up to a multiplicative stretch factor of \(\alpha\).
The size of \(H\) is measured as the number of its edges.
In this work, we study the size-stretch trade-offs of temporal spanners. In particular we show that temporal cliques
always admit a temporal \((2k-1)-\)spanner with \(O(kn^{1+\frac{1}{k}})\) edges, where \(k>1\) is an integer parameter of choice.
Choosing \(k=\lfloor \log n \rfloor\), we obtain a temporal \(O(\log n)-\)spanner with \(O(n)\) edges that has almost
the same size (up to logarithmic factors) as the temporal spanner given in [Casteigts et al., JCSS 2021] which only preserves
temporal connectivity.
We then turn our attention to general temporal graphs. Since \(\Omega(n^2)\) edges might be needed by any
connectivity-preserving temporal subgraph [Axiotis et al., ICALP'16], we focus on approximating distances from a single source.
We show that \(O(n/\log(1+\varepsilon))\) edges suffice to obtain a stretch of \((1+\varepsilon)\), for any small \(\varepsilon > 0\).
This result is essentially tight in the following sense: there are temporal graphs \(G\) for which any temporal subgraph preserving
exact distances from a single-source must use \(\Omega(n^2)\) edges. Interestingly enough, our analysis can be extended to the
case of additive stretch for which we prove an upper bound of \(O(n^2 / \beta)\) on the size of any
temporal \(\beta\)-additive spanner, which we show to be tight up to polylogarithmic factors.
Finally, we investigate how the lifetime of \(G\), i.e., the number of its distinct time-labels,
affects the trade-off between the size and the stretch of a temporal spanner.
Thekla Hamm (Utrecht University, Netherlands)
Temporal aspects in crossing-optimal graph drawing
Abstract:
The field of graph drawing concerns itself with the visualisation of graphs - a task which is ubiquitous in areas in which
information is displayed by graphs. Often such information can evolve over time and hence the treatment of temporal aspects is
an important challenge in graph drawing.
Classically, one of the most important features of drawings is a small number of crossings.
This talk will give a cross section on well-studied problems in graph drawing which are related to drawing graphs which can
change over time with few crossings which can serve as a pointer to interesting research directions in the area.
This includes graph drawing extension, simultaneous graph drawing and streaming planarity.
Moreover, we discuss recent and ongoing work with Eiben, Hliněný, Sorge and Rutter on what we call the sequential crossing
number which serves as demonstration on how to extend algorithmic techniques from classic graph drawing to temporal settings.
Pascal Kunz (TU Berlin, Germany)
Disentangling the computational complexity of network untangling
Abstract:
We study the network untangling problem introduced by Rozenshtein, Tatti, and Gionis [DMKD 2021], which is a variant of
Vertex Cover on temporal graphs -- graphs whose edge set changes over discrete time steps. They introduce two problem variants.
The goal is to select at most k time intervals for each vertex such that all time-edges are covered and (depending on the problem
variant) either the maximum interval length or the total sum of interval lengths is minimized. This problem has data mining
applications in finding activity timelines that explain the interactions of entities in complex networks.
Both variants of the problem are NP-hard. We study their multivariate complexity involving the following parameters:
number of vertices, lifetime of the temporal graph, number of intervals per vertex, and the interval length bound.
For both problem versions, we (almost) completely settle the parameterized complexity for all combinations of those
four parameters, thereby delineating the border of fixed-parameter tractability.
Joint work with Vincent Froese and Philipp Zschoche.
Jason Schoeters (University of Cambridge, UK)
On inefficient temporal graphs
Abstract:
Temporal network design is the study of how to optimally design networks with connections over time,
represented as a graph with an edge labeling (or a temporal graph). This area of research has previously
focused on minimising the number of labels to ensure temporal connectivity, whether it's the local or global
number of labels, all-to-all or terminal-to-terminal connectivity, or with additional constraints such as
limiting the age of the network. In this work, we focus on what would be the maximum number of connections.
This can represent the power of an adversary deliberately trying to design an inefficient network, even in the
presence of a verifier. This also implies results on greedy algorithms for finding sparse spanners in temporal graphs.
We present structural results for basic graph families such as trees and cycles, and explore algorithmic ideas on
how to efficiently compute maximum labellings, including a round-based game between adversary and verifier.
Meirav Zehavi (Ben-Gurion University of the Negev, Israel)
In which graph structures can we efficiently find temporally disjoint paths and walks?
Abstract:
A temporal graph has an edge set that may change over discrete time steps, and a temporal path (or walk)
must traverse edges that appear at increasing time steps. Accordingly, two temporal paths (or walks) are temporally
disjoint if they do not visit any vertex at the same time. The study of the computational complexity of finding
temporally disjoint paths or walks in temporal graphs has recently been initiated by Klobas et al. [IJCAI '21].
This problem is motivated by applications in multi-agent path finding (MAPF), which include robotics,
warehouse management, aircraft management, and traffic routing.
We extend Klobas et al.'s research by providing parameterized hardness results for very restricted cases,
with a focus on structural parameters of the so-called underlying graph. On the positive side, we identify
sufficiently simple cases where we can solve the problem efficiently. Our results reveal some surprising
differences between the "path version" and the "walk version" (where vertices may be visited multiple times)
of the problem, and answer several open questions posed by Klobas et al. The talk is based on a joint work
with Pascal Kunz and Hendrik Molter.
Laura Larios-Jones (University of Glasgow, UK)
Uncertainty in temporal reachability problems
Abstract:
Reachability and other path-based metrics on temporal graphs can be used to measure spread of infection, information and people.
These systems need to be simplified when modelled, leading to inaccurate inputs. We consider a number \(\zeta\) of edges whose timestamps
may be perturbed by \(\pm\delta\) for some \(\delta\). This allows us to factor some of the uncertainty associated with real-life into
the temporal assignment of our graphs. With this in mind, we investigate temporal reachability and three variants of temporal eccentricity;
namely shortest, foremost and fastest. We show that each of these problems is \(W[2]\)-hard with respect to \(\zeta\) and give some algorithmic
results.
Joint work with William Pettersson.
Anuj Jain (University of Florida, Gainesville, USA, and Adobe Systems Inc.)
Optimal paths and walks in temporal graphs
Abstract:
Path and walk problems are fundamental to the study of graphs. Temporal graphs are graphs in which the edges and vertices
change with time. We study path and walk problems and develop algorithms for finding min-hop, foremost, min-hop foremost (mhf),
min-wait foremost (mwf) and min-cost foremost (mcf) walks in interval temporal graphs (ITGs). We show experimentally that the
algorithms we develop outperform all the known algorithms for solving these problems by orders of magnitude on the various
benchmark datasets. We show that certain path/walk problems are NP-hard on interval temporal graphs while they are polynomially
solvable on contact sequence graph models (CSGs).
We also develop an algorithm to find optimal walks for any linear combination of the various optimization criteria with waiting
time constraints on temporal graphs with no-zero duration cycles. We show that our linear combination algorithm outperforms the
state-of-the-art algorithm for this problem on every benchmark dataset by a factor ranging from 5.5 to 77.
This is joint work with Dr Sartaj Sahni ( https://www.cise.ufl.edu/~sahni/).
Timothee Corsini (University of Bordeaux, France)
Simple, strict, proper, happy: A study of reachability in temporal graphs
Abstract:
Dynamic networks inherit the complexity of static networks (as
a particular case), making many existing techniques obsolete. In
addition, they happen to be deeply sensitive to original subtleties,
such as strictness (can several consecutive edges be used at the same
time instant?), properness (can adjacent edges be present at the same
time?) and simpleness (can an edge be present more than once?). These
features, it turns out, have a significant impact on the answers to
various questions, and are a frequent source of confusion and
incomparability of results. In this work, we explore their impact more
systematically. In particular, we show that different combinations of
these features lead to distinct levels of expressivity in terms of
reachability (separation results), while some others are equivalent
(transformation results). A surprising example of the latter type is
that proper temporal graphs can realize exactly the same set of
reachability graphs than general temporal graphs where non-strict paths are allowed.
This is joint work with Arnaud Casteigts and Writika Sarkar: https://arxiv.org/abs/2208.01720
Petra Wolf (University of Bergen, Norway)
Kernelizing temporal exploration problems
Abstract:
We study the kernelization of exploration problems on temporal graphs. A temporal graph consists of a finite sequence of snapshot graphs
\(G=(G_1,G_2,\ldots,G_L)\) that share a common vertex set but might have different edge sets.
The non-strict temporal exploration problem (NS-TEXP for short) introduced by Erlebach and Spooner,
asks if a single agent can visit all vertices of a given temporal graph where the edges traversed by the agent
are present in non-strict monotonous time steps, i.e., the agent can move along the edges of a snapshot graph
with infinite speed. The exploration must at the latest be completed in the last snapshot graph.
The optimization variant of this problem is the \(k\)-arb NS-TEXP problem, where the agent's task is to visit at least
\(k\) vertices of the temporal graph. We show that under standard computational complexity assumptions, neither of the
problems NS-TEXP nor \(k\)-arb NS-TEXP allow for polynomial kernels in the standard parameters: number of vertices \(n\),
lifetime \(L\), number of vertices to visit \(k\), and maximal number of connected components per time step \(\gamma\);
as well as in the combined parameters \(L+k\), \(L+\gamma\), and \(k+\gamma\). On the way to establishing these lower bounds,
we answer a couple of questions left open by Erlebach and Spooner.
We also initiate the study of structural kernelization by identifying a new parameter of a temporal graph:
\(p(G)=\sum_{i=1}^{L} (|E(G_i)|) - |V(G)| + 1 \).
Informally, this parameter measures how dynamic the temporal graph is.
Our main algorithmic result is the construction of a polynomial (in \(p(G)\)) kernel for the more general Weighted \(k\)-arb NS-TEXP problem,
where weights are assigned to the vertices and the task is to find a temporal walk of weight at least \(k\).
This talk is based on joined work together with Emmanuel Arrighi, Fedor V. Fomin, and Petr Golovach
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.