I'm solving questions training for a test and I came across this question. not sure how to even approach it. i have a flow network and i need to find out if there exist a minimum capacity cut, with 100 edges crossing it at the most. the more general question i thought of is, how to find the minimum capacity cut with the minimal number of edges.
thanks!
Assuming your goal is to first minimize capacity, and the only minimize the number of edges among all cuts that achieve the minimum capacity, one way is to replace the capacity $c(e)$ of each edge $e$ by $c(e) + \epsilon$ for some very small $\epsilon>0$, then find the minimum-capacity cut with the new capacities.
The goal is to choose $\epsilon$ small enough that no amount of $\epsilon$'s will make the difference between a minimum-capacity cut with lots of edges and a worse-than-minimum-capacity cut with few edges. For example, if all capacities are integers, you could choose $\epsilon = \frac1{|E|}$, where $|E|$ is the total number of edges in the network.
However, if two cuts both achieved the minimum capacity before the $\epsilon$'s were added, then the one with fewer edges will have the minimum capacity after the $\epsilon$'s are added. So the minimum cut you find will also minimize the number of edges.