EVENT

Event News

Talk on Andrea Marino, Jason Schoeters, and Lapo Cioni on topics

We are pleased to inform you about the upcoming seminar by "Andrea Marino, Jason Schoeters, and Lapo Cioni on topics" Everyone interested is cordially invited to attend!

Talk 1:

Disjoint Temporal Walks Under Waiting Time Constraints

Abstract:

A temporal (directed) graph is a (directed) graph whose edge availability varies over time, and temporal walks are sequences of adjacent edges respecting these availabilities.
A third component of this scenario imposes time constraints on the vertices, known as ``waiting time constraints.'' Drawing a parallel with a transportation network, these constraints can be envisioned as the minimum and maximum time a person would need or be willing to stay at the same location. It is known that computing a temporal walk between a pair of vertices under waiting time constraints can be achieved in polynomial time, even when optimizing certain criteria. In this article, we extend these investigations to the problem of finding $k$ temporal walks such that no two distinct walks overlap in time. Given a multiset $\{(s_1, z_1), \ldots, (s_k, z_k)\}$ of pairs of vertices of a temporal graph $\mathcal{G}$, we consider the problem of finding a set of pairwise temporally disjoint walks $P_1, \ldots, P_k$ such that each $P_i$ is a temporal walk from $s_i$ to $z_i$. Under a given set of waiting time constraints, when $s_i = s$ and $z_i = z$ for all $i \in [k]$ we show that determining the existence of such walks is $\W[1]$-hard when parameterized by $k$, and that it is $\NP$- complete to decide the existence of a separator (i.e., a set of vertex occurrences in time intersecting all such walks) of size at most $h$. In the more general case, when the vertices $s_i$ and $z_i$ are allowed to be disjoint, we show that the walks can be found in $\XP$ time parameterized by $k$ when each walk has to wait at least $\omega_L(u) \geq 1$ units of time on each occurrence of each vertex $u$ used by the walk, and that the separator can be found in $\XP$ time with parameter $h$.

Paper:
Allen Ibiapina, Raul Lopes, Andrea Marino, Ana Silva: Disjoint Temporal Walks Under Waiting Time Constraints. CIAC (2) 2025: 87-103

Speaker Bio:

Andrea Marino (From University Florence, Italy)

Talk 2:

Temporal Cycle Detection and Acyclic Temporalization

Abstract:

In directed graphs, a cycle can be seen as a structure that allows its vertices to loop back to themselves, or as a structure that allows pairs of vertices to reach each other through distinct paths. We extend these concepts to temporal graph theory, resulting in multiple interesting definitions of a "temporal cycle". For each of these, we consider the problems of Cycle Detection and Acyclic Temporalization. For the former, we are given an input temporal digraph, and we want to decide whether it contains a temporal cycle. Regarding the latter, for a given input (static) digraph, we want to time the arcs such that no temporal cycle exists in the resulting temporal digraph. We're also interested in Acyclic Temporalization where we bound the lifetime of the resulting temporal digraph. Multiple results are presented, including polynomial and fixed-parameter tractable search algorithms, polynomial-time reductions from 3-SAT and Not All Equal 3-SAT, and temporalizations resulting from arbitrary vertex orderings which solve (almost) all cases.

Speaker Bio:

Jason Schoeters (From University Florence, Italy)

Talk 3:

Matching and Edge Cover in Temporal Graphs

Abstract:

Temporal graphs are an extension of traditional "static" graphs which incorporate the dimension of time. Each edge in a temporal graph has timestamps indicating when the edges are available. Many classical graph problems can be naturally extended to the temporal setting, often leading to fundamentally different computational behaviours and outcomes.

In this seminar, we introduce the Temporal Edge Cover and Temporal Matching problems. Their static counterparts consists of finding a set of edges such that they are incident to each vertex of a graph (Edge Cover) and a set of edges where no two edges share any vertex (Matching). There are many ways to generalize this problems in temporal graphs. We explore some of the natural extensions, proving complexity results, even under restrictive conditions where the lifetime is bounded or the underlying graph is a tree. We also discuss about FPT agorithms and approximation algorithms which solve Temporal Edge Cover and Temporal Matching.