I am trying to find a polynomial time algorithm or a reduction to an NP-hard problem for the following version of the minimum cut problem:
given: Directed Graph $G=(V,R)$, source node $s \in V$ and sink node $t \in V$, capacities $u:R \rightarrow \mathbb{R}_{\geq 0}$ and arcs $A \subseteq R$
problem: Find a minimum $s,t$-cut $(S,T)$ under the condition that $A \subseteq \delta^{-}(S)$ (i.e. the constraint arcs are contained in the cut set)
I've already tried dualizing an LP-formulation for the minimum cut problem in a directed graph extended by some constraints representing the new edge constraints. \begin{alignat}{3} \min & \sum_{r \in R}{u(r)y(r)} & \\ \text{subject to: } & z(\omega(r)) - z((\alpha(r))) + y(r) \geq 0 & & \forall r \in R\\ & z(s) - z(t) + y(\overline(r)) \geq 1 & & \mid \overline{r} \text{ artificial edge (t,s)} \\ & z(\alpha(r)) \geq 1 & & \mid \text{ additional constraint for } A \\ & z(\omega(r)) \leq 0 & & \mid \text{ additional constraint for } A \\ & y \geq 0 & \quad\\ \end{alignat}
Without these constraints one can get an corresponding s,t-cut in this formulation as
$S:=\{v \in V \mid z(v) \geq 1\}$ and $T:= \{v \in V \mid z(v) \leq 0\}$
The corresponding dual LP would be:
\begin{alignat}{3} \min & f(\overline{r}) + \sum_{r \in A}{k(r)} & \\ \text{subject to: } & \sum_{r \in \delta^{-}(v)}{f(r)} - \sum_{r \in \delta^{+}(v)}{f(r)} (+ \sum_{r \in \delta^{+}(v)}{k(r)} \text{ if } \delta^{+}(v) \cap A \neq \emptyset) (- \sum_{r \in \delta^{-}(v)}{l(r)} \text{ if } \delta^{+}(v) \cap A \neq \emptyset) = 0 & & \forall v \in V\\ & 0 \leq f(r) \leq u(r) & & \forall r \in R \\ & 0 \leq k(r),l(r) & & \forall r \in R \quad\\ \end{alignat}
However, this didn't help as it further confused me. At first i hoped that it should be an easy problem as for an edge $e=(u,v) \in A$ one has to assure that $u \in S$ and $v \in T$ for every flow one consideres. I thought that maybe one could alter Ford Fulkerson in such a way that every augmenting path considered could be treated conditionally in such a way that $u \in S$ and $v \in T$ is always assured. I tried to search for this constrained version of a minimum cut problem online. However, i wasn't able to find any valuable sources on this problem. I am looking forward for your comments.