Abstract
In the study of temporal graphs, only paths respecting the flow of time are relevant. In this context, many concepts of walks disjointness have been proposed over the years, and the validity of Menger’s Theorem, as well as the complexity of related problems, has been investigated. Menger’s Theorem states that the maximum number of disjoint paths between two vertices is equal to the minimum number of vertices required to disconnect them. In this paper, we introduce and investigate a type of disjointness that is only time dependent. Two walks are said to be snapshot disjoint if they are not active in a same snapshot (also called timestep). The related paths and cut problems are then defined and proved to be W[1]hard and XPtime solvable when parameterized by the size of the solution. Additionally, in the light of the definition of Mengerian graphs given by Kempe, Kleinberg and Kumar in their seminal paper (STOC'2000), we define a Mengerian graph for time as a graph G for which there is no time labeling for its edges where Menger’s Theorem does not hold in the context of snapshot disjointness. We then give a characterization of Mengerian graphs in terms of forbidden structures and provide a polynomialtime recognition algorithm. Finally, we also prove that, given a temporal graph (G,λ) and a pair of vertices s,z ∈ V(G), deciding whether at most h multiedges can separate s from z is NPcomplete, where one multiedge uv is the set of all edges with endpoints u and v.
BibTeX  Entry
@InProceedings{ibiapina_et_al:LIPIcs.SAND.2023.1,
author = {Ibiapina, Allen and Silva, Ana},
title = {{Snapshot Disjointness in Temporal Graphs}},
booktitle = {2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
pages = {1:11:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772754},
ISSN = {18688969},
year = {2023},
volume = {257},
editor = {Doty, David and Spirakis, Paul},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17937},
URN = {urn:nbn:de:0030drops179379},
doi = {10.4230/LIPIcs.SAND.2023.1},
annote = {Keywords: Temporal graphs, Menger’s Theorem, Snapshot disjointness}
}
Keywords: 

Temporal graphs, Menger’s Theorem, Snapshot disjointness 
Collection: 

2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023) 
Issue Date: 

2023 
Date of publication: 

12.06.2023 