I have encounter a network disconnecting problem can be abstracted as a generalized version of s-t min-cut problem.

The standard s-t min-cut problem is the following. Consider a digraph $G=(V, E)$ with a nonnegative weight $c_e$ for every edge $ein E$ and a pair of nodes $(s, t)$ where $s$ is the source and $t$ is the terminal. Find a set of edges C with a minimal weight sum such that by removing $C$ from $E$ in the graph $G$ (resulting in a subgraph $G’$), from $s$ we can no longer reach $t$. This s-t min-cut problem have been well solved by max-flow-min-cut theorem and can be solved using many algorithms such as push-relabel etc.

Notice that by putting any one edge in the min-cut $C$ back to the subgraph $G’$, $t$ is again reachable from $s$. The problem I am encountering is: I want to disconnect $t$ from $s$ with a stronger cut so that the disconnection is not recoverable so easily. Hence, what I want to do is to find a cut, denoted as $C2$, of a minimal weight such that: (1) by removing $C2$ from $E$, $t$ is not reachable from $s$ in the subgraph $G’$, and (2) to recover the reachability of $t$ from $s$, at least $k=2$ edges in $C2$ must be put back in $G’$.

If $k=1$, the problem is exactly the standard s-t min-cut problem.

I have tried to generalize max-flow-min-cut theorem to my case but seems difficult (or impossible). On the other hand, I have a strong feeling that the problem is not NP (at least for a fixed number of disconnections).

My current solution is to apply min-cut three times to obtain a solution: find a min-cut $C$ which splits $G$ into $G_S$ and $G_T$; for $G_S$ and $G_T$ find min-cuts $C_S$ and $C_T$; select $C+C_S$ or $C+C_T$ with the smaller weight. But I cannot be sure that such a “greedy” solution is globally optimal.

So, does anyone have some clue on efficient algorithms to find a globally optimal solution, or clues for the difficulty of the problem?