Menger’s theorem and related problems on temporal graphs.

Abstract

Temporal graphs are an important tool for modeling time-varying relationships in dynamic systems. Among the problems of interest, paths and connectivity problems have been the ones that have attracted the most attention of the community. The famous Menger’s Theorem says that, for every pair of non-adjacent vertices s,z in a graph G, the maximum number of internally vertex disjoint s,z-paths in G is equal to the minimum number of vertices in G − {s,z} whose removal destroys all s,z-paths (called and s,z-cut). This combined with flow techniques also leads to polynomial time algorithms to compute disjoint paths and cuts. A natural question is therefore whether such results carry over to temporal graphs, where the paths/walks between a pair of vertices must respect the flow of time. The first obstacle in such question is the definition of the robustness in context, i.e., what it means for paths/walks to be disjoint. In this thesis, we investigate three possible types of robustness, each of which leading to the definition of two optimization parameters, one concerning the maximum number of disjoint paths, and the other the minimum size of a cut. We give theoretical results about the validity of Menger’s Theorem and computational complexity results for the decision problems related to each parameter.