Flows and cuts in temporal graphs study how value can be transported through a network whose edges are only available at specific times, and how few deletions suffice to obstruct all such transport — generalising the classical max-flow / min-cut and Menger concepts from static graphs.
In static graphs, flows and cuts are the canonical tools for analysing how much can be routed between two designated vertices and how graph structure can influence this. A flow network is a static graph $G=(V,E)$ together with a source $s$, a sink $t$, and a capacity function $c\colon E\to\mathbb{R}{\ge 0}$. A flow is a function $f\colon E\to\mathbb{R}{\ge 0}$ obeying
The value of a flow $\mathrm{val}(f)$ is the net flow leaving $s$. An $s$-$t$ cut is an edge set $R\subseteq E$ whose removal destroys every $s$-to-$t$ path; equivalently, $R=S(A,B)$ for a partition $(A,B)$ of $V$ with $s\in A$ and $t\in B$, and has capacity $c(R)=\sum_{e\in R}c(e)$. The classical duality is the Max-Flow Min-Cut Theorem [Ford–Fulkerson 1956]: $\max_{f}\mathrm{val}(f) \;=\; \min_{R}c(R)$. The maximum flow can be computed using the augmenting-path algorithms (Ford–Fulkerson, Edmonds–Karp, Dinic) in polynomial time. This max-flow min-cut duality is the generalisation of Menger's theorem: the maximum number of internally vertex-disjoint (resp. edge-disjoint) $s$-$t$ paths equals the minimum size of an $s$-$t$ vertex (resp. edge) separator. Together, the two results are part of a broad family of connectivity problems — $k$-(vertex/edge)-connectivity, multi-commodity flow, vertex/edge multicut, $k$-disjoint paths, bipartite matching, and connectivity augmentation — a substantial portion of which is polynomial-time solvable in static graphs.
In temporal graphs, edges are only usable at their time labels and reachability is governed by Temporal Paths/Trips/Journeys. Both flows and cuts inherit this temporal dimension:
The temporal setting (directed vs undirected, strict vs non-strict, simple vs multi-labeled) can significantly affect both the definitions and complexity of the resulting problems. Many temporal flow- and cut-type problems are NP-hard already under strong structural restrictions. Compared to the static case, max-flow / min-cut duality is delicate: depending on which objects are deleted and how flow is metered, the analogue of Max-Flow Min-Cut may hold exactly, hold up to a bounded multiplicative gap, or fail entirely.
Temporal analogues of Menger’s theorem have been studied extensively.
Temporal Variants of Menger’s Theorem
Computing the maximum flow also has recent a decent amount of attention.
In comparison, the temporal Max-Flow Min-Cut gap is still not fully explored.