Lesson 3

To design an efficient algorithm for the project selection problem, we reduce it to the minimum cut problem in a network. Specifically, we build the following network \(G\).

1. The vertex set is the projects \([n]\) and two special vertices \(s\) and \(t\).
2. For each project \(i\) with \(p_{i}>0\), add an edge \((s,i)\) with capacity \(p_{i}\).
3. For each project \(i\) with \(p_{i}<0\), add an edge \((i,t)\) with capacity \(-p_{i}\).
4. For each constraint \((i,j)\), add an edge \((i,j)\) with infinite capacity.

In this network, we will look for a minimum cut and, as we show below, the optimal feasible set of projects will be those in the same part as vertex \(s\). Intuitively, this is because: A cut of finite capacity always exists (e.g., cutting off \(s\)). Thus, edges of infinite capacity never appear in the cut, so all constraints are respected. Also, minimizing the cut means cutting fewer \((s, i)\) edges, which corresponds to including more projects with positive profit. We prove this formally below.