Max flow to find the most profitable arrangement

Question

Let a_1, ..., a_n actors. Each actor has a cost c_1, ..., c_n. Also, we have investors, b_1,..., b_m such that each investor is willing to put q_j money for our film. An investor would put money in our film iff all of his favor actors, will be in our movie. We may have multiple investors of course. Find the subsets of actors/investors to maximize our profit (i.e. sum of investments minus sum of salaries)

Basically the solution is to connect some vertex s to each investor with an edge of weight q_i. Next, we connect each investor to it's favor actors with edge of weight infinity. Finally, we connect each actor to some vertex t with an edge of weight c_i.

Then, we look for maximum flow.

My questions are:

• Why does it work?
• I've been told that In order to find those subsets of actors/investors we need to look at the minimal cut (S,T), and then we have: picked_investors = S ∩ investors and picked_actors = S ∩ actors. Could you explain that?
• Can't we just look at where the flow goes to find those two subsets?

Answer 1

This algorithm is based in the maximum flow - minimum cut duality. Let's analyze what a mincut in this graph looks like.

We can easily see that a finite solution is possible: consider the cut having {s} in one side and the other nodes in the other side. Clearly, the value of this cut is the sum of the q_i, which is finite.

Now let's see the meaning of a cut in this graph. If an investor is in the same side than s in the cut, that means he/she will invest his/her money. If an actor is in the same side than s in the cut, that means he will also take part in the movie. Being in the other side of the cut means not taking part in the movie (for both actors and investors).

The key part is the following: any cut not satisfying the restrictions given in the statement will have an infinite value, as there will be an edge from an investor to an actor crossing the cut. As we have seen before, a finite solution exists, so a mincut will satisfy the restrictions.

Now, what are we minimizing? Ignoring infinity edges, an actor edge is added to the value iff we pick that actor for the movie and an investor edge is added iff we don't pick that investor for the movie. We wanted to maximize the benefits, that's the same than minimizing what we can lose.