Algorithms and Complexity for Temporal Graph Optimization and Design

Abstract

In this dissertation, we focus on graphs with an added time dimension, called temporal graphs.
Temporal graphs naturally model graphs whose underlying topology changes over time.
Our aim is to extend classical graph concepts with a temporal dimension and contribute to the algorithmic developments in temporal graphs.
We achieve this by presenting an in-depth study of four different problems.

We start with the problem of finding temporally disjoint paths or walks between a given set of vertices, where two paths or walks are temporally disjoint if they do not intersect at any point in time.
We focus on the special cases, where the underlying graph of the given temporal graph is either a tree or a path.
While this problem proves to be computationally demanding in general, we identify specific cases where its complexity is more manageable.

Our research extends to the Temporal Vertex Cover (TVC) and Sliding-Window Temporal Vertex Cover (Delta-TVC) problems, natural extensions of the classic Vertex Cover problem. Interestingly, Delta-TVC proves to be computationally challenging already on simple graphs like paths or cycles, presenting a sharp contrast to the more tractable TVC in similar scenarios. We introduce various algorithms to solve these problems in specific types of temporal graphs.

Shifting our focus, we explore temporal design problems for ensuring connectivity in undirected temporally connected graphs. The core objective is to minimize the number of time-labels added to the edges while preserving temporal connectivity. We present scenarios where this task is computationally challenging and others where it demonstrates more tractable behavior, which leads us to investigate the complex connection between time and structure in these graphs.

Our final problem explores temporal graph realization, specifically in constructing periodic temporal graphs with fastest paths matching prescribed time durations between vertices. We show that while this problem is generally hard, it becomes more manageable when the underlying structure resembles a tree.