Course contentsShow
← Computer Science
Lesson 1052 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Project Selection Problem

Model project selection with prerequisites and profits as a max flow problem to maximize revenue.

Project Selection Problem

What you'll learn: You'll learn how to model a project selection scenario—where some projects have profits, some have costs, and certain projects require others—as a maximum flow problem to find the most profitable subset of projects to undertake.

The Core Idea

Imagine you're a manager deciding which projects to green-light. Each project has an associated profit (or cost), and some projects have prerequisites: you can't do Project B unless you also commit to Project A. Your goal is to maximize total revenue by choosing the optimal set of projects.

This problem maps beautifully to a min-cut problem, which by the max-flow min-cut theorem, we solve using maximum flow algorithms.

Building the Flow Network

Here's how to construct the graph:

  1. Create a source node s and a sink node t
  2. For each project i with positive profit p_i, add an edge from s to node i with capacity p_i
  3. For each project j with cost c_j (negative profit), add an edge from node j to t with capacity c_j
  4. For each prerequisite relationship (project j requires project i), add an edge from j to i with infinite capacity

Why It Works

The minimum cut separates the source from the sink. Projects on the source side of the cut are selected; those on the sink side are rejected. The infinite-capacity edges ensure prerequisites are respected (cutting them would be infinitely expensive). The min-cut value represents the maximum profit we must forgo, so:

Maximum profit = (sum of all positive profits) - (min-cut value)

Key Takeaway: The project selection problem transforms business logic (profits, costs, dependencies) into a max-flow/min-cut problem, letting you compute the optimal project portfolio efficiently using flow algorithms like Edmonds-Karp or Dinic's.