Menger's theorem in temporal graphs studies the duality between the maximum number of disjoint $s$-$t$ temporal paths and the minimum number of objects whose removal disconnects $s$ from $t$ — generalising the classical vertex- and edge-Menger theorems from static graphs into a family of analogues, only some of which carry over to the temporal setting.

In static graphs, Menger's theorem (Menger 1927) is the foundational duality between connectivity and path-packings. It admits a vertex- and an edge-version: (note that internally vertex-disjoint means vertex-disjoint without considering the endpoints)

<aside> ⚠️

Theorem (Vertex-Menger, 1927). For any static (di)graph $G=(V,E)$ and $s,t\in V$ non-adjacent, the maximum number of internally vertex-disjoint $s$-$t$ paths equals the minimum size of an $s$-$t$ vertex separator $S\subseteq V\setminus\{s,t\}$.

</aside>

<aside> ⚠️

Theorem (Edge-Menger, 1927). For any static (di)graph $G=(V,E)$ and $s,t\in V$ non-adjacent, the maximum number of edge-disjoint $s$-$t$ paths equals the minimum size of an $s$-$t$ edge cut $R\subseteq E$.

</aside>

The two statements are equivalent under a standard splitting reduction, and — with unit edge-capacities — are the integer-valued Max-Flow Min-Cut theorem.

In temporal graphs, the classical statements split into multiple non-equivalent formulations because the words "disjoint" and "separator" each admit several natural meanings:

1. Disjointness can refer to two temporal paths being internally static-vertex-disjoint, static-edge-disjoint, time-edge-disjoint, or time-vertex-disjoint (sharing no common temporal vertex).
2. Separators can be sets of static vertices $v$, static edges $e$, temporal edges $\varepsilon=(e,t)$, or temporal vertices $(v,t)$.

The choice of pairing matters: some pairings produce a clean duality (Berman 1996; MMS 2013/18), some produce a strict gap (KKK 2002), and the complexity of computing the corresponding minimum Temporal Separators can flip from polynomial to NP-hard depending on the choice. It is also important which setting of temporal graphs is considered.

History on temporal Menger variants

Literature on temporal Menger

Notions of Temporal Menger Dualities — Known Results

Conventions. A temporal $s$-$t$ path in $\mathcal{G}=(G,\lambda)$ is a sequence of temporal edges with non-decreasing (non-strict) or strictly increasing (strict) times. Two temporal paths can be disjoint in several senses; a separator is a set of vertices/edges whose removal destroys all temporal $s$-$t$ reachability. Also, vertex-disjoint always stands for internally vertex-disjoint.

<aside> ❗

We use the notation $\alpha$-$\beta$-Menger to refer to a temporal Menger variant, where $\alpha,\beta \in \{\mathrm{tE}, \mathrm{sE}, \mathrm{tV}, \mathrm{sV}\}$ stand for temporal edges, static edges, temporal vertices, and static vertices, respectively.

The parameter $\alpha$ specifies the notion of disjointness among temporal paths, whereas $\beta$ specifies the type of elements allowed in the separator set.

</aside>

What is missing:

• sE-sE-Menger — holds for simple temporal graphs since there every static edge corresponds to exactly one temporal edge and [Berman96] showed tE-tE-Menger holds. We give a proof for multilabel tgs below.
• off-diagonal pairings such as tE-sV-Menger, meaning all $\alpha$-$\beta$-Menger with $\alpha\neq \beta$ — expected to fail using the existing examples
• nonstrict temporal graphs for the tV-tV-Menger result of MMS13 — holds via nonstrict static expansion.

Proofs for missing entries

<aside>

Theorem 1. sE-sE-Menger does not hold in (un)directed (non)strict temporal graphs.

• Proof. </aside>

Mengerian Temporal Graphs

On Mengerian temporal graphs the computation of temporal vertex-separators is in P, which is not the case for general temporal graphs. This might lead to the believe that other computational problem are easy as well on Mengerian temporal graphs. It follows from [KKK02] that any temporal graph with maximum static degree 3 (which equals the maximum temporal total degree) is Mengerian.

<aside>

Theorem. Open Temporal Connected Components is NP-hard on undirected simple proper Mengerian temporal graphs.

</aside>

This follows directly from the classical reduction from Clique $(H,k)$ to OTCC $(\mathcal{G},k)$ on directed strict simple temporal graphs, where $G=H$ and every edge has time label $1$. Now replace every vertex $v$ with degree larger than $3$ by a binary tree rooted in $v$ with the original neighbors as leaves and a $v$-pivot labeling. Following Simple, Strict, Proper, Happy: A Study of Reachability in Temporal Graphs, we can use the transformation: semaphore to transform this into an undirected simple proper temporal graph of maximum temporal degree 3, which is Mengerian.