Second Smallest $s$-$t$-Cut in a Network
The second smallest cut, and more generally the $k$ smallest cuts, can be found in time polynomial in $k$ and the network size. See:

H. W. Hamacher. An $(K\cdot n^4)$ algorithm for finding the $k$ best cuts in a network. Oper. Res. Lett. 1(5):186–189, 1982, doi:10.1016/0167-6377(82)90037-2.

H. W. Hamacher, J.-C. Picard, and M. Queyranne. On finding the $K$ best cuts in a network. Oper. Res. Lett. 2(6):303–305, 1984, doi:10.1016/0167-6377(84)90083-X.

H. W. Hamacher and M. Queyranne. $K$ best solutions to combinatorial optimization problems. Ann. Oper. Res. 4(1–4):123–143, 1985, doi:10.1007/BF02022039.