2
$\begingroup$

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$).

No unprofitable projects

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?

2 Answers 2

1

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.

1

I hesitate to write this up as an answer, but I guess I don't have the 'comment' privilege yet.

These types of issues are important to understand, as they force you to understand the problem in more depth and come up with a model that accurately describes it without too much fluff.

Anytime you encounter a case that breaks your model, you can try to add something to the model that allows you to model it accurately.

The one project case is obvious: there's no problem to solve. You either do the project or you don't.

A project with zero cost almost makes no sense. If the cost is zero, then I'd try to change the model to more accurately describe the problem. In the simplest case, a business choosing projects to tackle would have at least two costs in mind: time spent, money spent.

Now, suppose project X1.0 (v1.0) is already complete, but it sucks. The choice is one of:

  1. X1.0 -> Y1.0 (Just use it and put up with the headaches)
  2. X1.1 -> Y1.0 (Improve X1.0)
  3. X2.0 -> Y1.0 (Re-write it)

The cost of traversing the edge from X to Y in (1) is zero. However, a proper model for this would have 3 nodes in the graph for Y: one for each path. Treating Y as a single node with separate edges then creates the implicit assumption that the path from Y1.0 to Z1.0 is the same no matter which of the 3 options you pick.

In short: this is what mathematical modeling is all about. Analyzing the problem and coming up with a good way to accurately model it. If something breaks it, more than likely it's your model.