I am currently studying network flow algorithms and one of its application is supposed to be "Project Selection". A (more) complete description is given here, but the problem basically is this:
There is a graph $G$ with a number of projects $P$ as nodes. Projects have a revenue $p_i$ and a dependency from project $j$ on $i$ is given as an edge $(j,i)$.
Now it is said that the minimum cut will provide the most efficient set of projects to take if makes a source node $s$, sink node $t$ and make an edge $(s,i)$ if $p_i > 0$ and an edge $(i,t)$ if $p_i < 0$
There are however several cases I can think of that seem impossible to solve in this matter.
Consider for example a case with only 1 project ($P = {a}$) with a revenue of +10. Clearly the most profitable set of projects to do is ${a}$, but a flow is impossible in this case (and thus all possible cuts are minimal, including those without $a$).
Or if there is a project with no cost, it will not have a connection with the source nor sink and as such does not have to be in the minimum cut.
(pic coming later)
(other counter-examples I can think of basically are all based on these 2 problems)
Can anyone shed some light on this algorithm for me?
Best Answer
You misunderstood the result. Whether a flow is possible or not is not relevant. In your first case, where the graph is
$ s \to a \, \ t $
the minimal cut (=partition of the nodes into two sets, one containing s and the other t) is ({s,a}, {t}) which has capacity 0 because there are no edges from one set to the other. The other cut ({s},{a,t}) has capacity 10 (the capacity of the edge from s to a). In the other example with revenue 0, both possible cuts have capacity 0 so you can either do project a or not; both are optimal.