Consider an undirected, weighted graph $G = (P,E)$ where $P$ is the node set and $E$ is the edge set. Say that for a single source and target pair, $s$ and $t$ there is a min-cut $C_{\min}$ which generates the max-flow $f_{\max}$.
I am interested in the following question: Is there a way to find a sub-graph with the least number of edges, such that the min-cut $C_{\min}$ (and thus max-flow) is preserved?
Can anyone point me to any relevant problems, algorithms, or provide any insight?
On
You can solve the problem via mixed integer linear programming as follows. Let nonnegative decision variable $x_{i,j}$ be the flow across arc $(i,j)$, and let binary decision variable $y_{i,j}$ indicate whether arc $(i,j)$ is selected. The problem is to minimize $\sum_{i,j} y_{i,j}$ subject to linear constraints: \begin{align} \sum_j x_{i,j} - \sum_j x_{j,i} &= \begin{cases}C_\min &\text{if $i=s$} \\ -C_\min &\text{if $i=t$} \\ 0 &\text{otherwise}\end{cases} &&\text{for $i\in P$} \tag1 \\ x_{i,j} &\le C_\min y_{i,j} &&\text{for $(i,j)\in E$} \tag2 \end{align} Constraint $(1)$ enforces a flow of $C_\min$ from $s$ to $t$. Constraint $(2)$ enforces the logical implication $x_{i,j} > 0 \implies y_{i,j} = 1$.
The problems in which we want to buy some minimum-cost set of arcs to ensure some connectivity properties between pairs of vertices are called survivable network design. They are well-studied, most of them (if not all) are NP-hard but there are several known approximation algorithms.
In your case, you have only one pair with a requirement equal to the max-flow value, and the costs are uniform (as you want to minimize the cardinal of the arc set). Unfortunately, this does not make it much easier. Indeed you can reduce the uniform Steiner tree problem in graphs: given $G=(V,E)$ an undirected graph and $T \subseteq V$ a set of terminal, find a tree spanning $T$ with a minimum number of edges.
The reduction is: choose $s \in T$, add a new vertex $t$ with an arc from each $z \in T \setminus \{s\}$ to $t$. Replace each edge $\{u,v\} \in E$ by two arcs $uv$ and $vu$, each with infinite capacity (or capacity $|T|-1$ if you prefer). Then the support of an $st$-flow of value $|T|-1$ induces a Steiner tree on $T$, and reciprocally from a Steiner tree on $T$ one can find an $st$-flow whose support is the tree. Hence both instances are equivalent. Your problem is NP-hard.
I suggest looking at approximation algorithms for the survivable network design problem and trying to use one of them, and perhaps even simplify one of them to your particular setting.