12.19 Project Selection

Problem

You have a set of possible projects. Each project has a profit or a cost. Some projects depend on other projects.

Example:

Project	Value
Build API	+10
Build Database Layer	-4
Build Auth	-3
Build Dashboard	+8

Dependencies:

Build API requires Build Database Layer
Build Dashboard requires Build API
Build Dashboard requires Build Auth

You want to choose a subset of projects that maximizes total value while respecting dependencies.

This is the project selection problem.

Solution

Reduce the problem to a minimum cut.

Create a graph with:

• One node per project
• A source s
• A sink t

Use edge capacities to encode profit, cost, and dependency constraints.

Then compute a minimum s-t cut.

The projects on the source side of the cut are selected.

Modeling Profits and Costs

For a project with positive value:

profit p > 0

add:

s -> project
capacity = p

For a project with negative value:

cost c < 0

add:

project -> t
capacity = -c

Positive projects pull the cut toward keeping them on the source side.

Negative projects pull the cut toward putting them on the sink side.

Modeling Dependencies

If choosing project A requires choosing project B, add:

A -> B
capacity = INF

This prevents a finite minimum cut from placing A on the source side while placing B on the sink side.

Why?

If A is selected and B is not selected, the cut crosses:

A -> B

with capacity INF.

A minimum cut will avoid that unless no feasible alternative exists.

Example

Projects:

Project	Value
API	+10
Database	-4
Auth	-3
Dashboard	+8

Dependencies:

API -> Database
Dashboard -> API
Dashboard -> Auth

Graph:

s -> API        capacity 10
s -> Dashboard  capacity 8

Database -> t   capacity 4
Auth -> t       capacity 3

API -> Database       capacity INF
Dashboard -> API      capacity INF
Dashboard -> Auth     capacity INF

After computing min cut, suppose the source side contains:

API
Database
Dashboard
Auth

Total value:

10 - 4 + 8 - 3 = 11

This is feasible because every dependency is selected.

Why Min Cut Maximizes Profit

Let:

P = sum of all positive project values

For any valid selection, the corresponding cut cost equals:

P - selectedValue

So minimizing the cut cost maximizes selected value.

This is the key identity.

Positive projects not selected contribute to cut capacity because their source edge is cut.

Negative projects selected contribute to cut capacity because their sink edge is cut.

Dependency violations would contribute INF, so they are excluded.

Cut Interpretation

After max flow/min cut:

selected projects = vertices reachable from s in residual graph

excluding s.

Unselected projects are on the sink side.

This is the same residual-reachability rule used for ordinary minimum cut.

Small Example

Projects:

Project	Value
A	+6
B	-2
C	+4

Dependency:

A requires B

Graph:

s -> A capacity 6
s -> C capacity 4
B -> t capacity 2
A -> B capacity INF

Possible valid selections:

Selection	Value
none	0
C	4
A, B	4
A, B, C	8

Best selection:

A, B, C

Value:

8

The min cut returns these projects on the source side.

Choosing Infinity

INF must be larger than any finite cut that could matter.

A safe value is:

sum of all positive values + sum of all absolute negative values + 1

If values are large, use 64-bit integers.

Do not use maximum integer values if additions may overflow.

Multiple Dependencies

If project A requires both B and C, add:

A -> B capacity INF
A -> C capacity INF

If project A requires at least one of B or C, the simple dependency edge model is not enough. That is an OR dependency and needs a different construction or a more general optimization model.

The min-cut reduction handles implication dependencies:

A selected => B selected

Mandatory Projects

To force a project A to be selected, add:

s -> A capacity INF

To force a project A to be excluded, add:

A -> t capacity INF

These constraints are often useful when a business rule overrides pure profit.

Mutually Exclusive Projects

A simple min-cut project selection model does not directly encode:

choose at most one of A and B

Some special cases can be transformed, but arbitrary mutual exclusion turns the problem into a more general constraint optimization problem.

Use this reduction when dependencies are implications and project values are additive.

Implementation Pattern

Create one integer ID per project.

For each project:

if value > 0:
    addEdge(source, project, value)

if value < 0:
    addEdge(project, sink, -value)

For each dependency:

A requires B:
    addEdge(A, B, INF)

Run max flow.

Then run BFS or DFS in the residual graph from source.

Every reachable project is selected.

Complexity

The graph has:

V = number of projects + 2

and:

E = number of valued projects + number of dependencies

The running time is the running time of your max-flow algorithm.

With Dinic, the method is practical for large dependency graphs.

Common Mistakes

Reversing Dependency Direction

If A requires B, the edge is:

A -> B

not:

B -> A

The edge should penalize selecting A while excluding B.

Using Negative Capacities

Capacities must be nonnegative. Negative project values become edges to the sink.

Selecting Sink-Side Vertices

Selected projects are on the source side of the minimum cut.

Choosing INF Too Small

If INF is not large enough, the cut may prefer violating a dependency.

Modeling OR Dependencies Directly

The simple construction supports implication dependencies, not arbitrary logical formulas.

Discussion

Project selection is a canonical example of min-cut modeling. It shows that flow networks are not only about moving physical resources. They can also encode logical closure constraints and profit maximization.

The selected set must be closed under dependencies: whenever it contains a project, it also contains everything required by that project. This is why the problem is also known as the maximum weight closure problem.

Takeaway

Project selection with additive values and implication dependencies reduces to a minimum cut. Positive-value projects connect from the source, negative-value projects connect to the sink, and dependency edges receive infinite capacity.

After computing the min cut, all project nodes reachable from the source form the optimal feasible selection.