12.16 Vertex Capacities

Problem

Standard flow networks place capacity constraints on edges.

That works when the limiting resource is a road, pipe, cable, route, or connection. But in many problems, the bottleneck belongs to a vertex.

Examples:

• A warehouse can process at most 500 packages per hour.
• A router can forward at most 10 Gbps.
• A machine can handle at most 12 jobs.
• A hospital can admit at most 40 patients.
• A checkpoint can process at most 300 vehicles.

In these cases, limiting only the incoming and outgoing edges is not enough. You need to constrain the total amount of flow passing through a vertex.

Solution

Convert each capacity-limited vertex into two vertices:

v_in
v_out

Then add one directed edge:

v_in -> v_out

with capacity equal to the vertex capacity.

All original incoming edges now point to v_in.

All original outgoing edges now leave from v_out.

This technique is called node splitting.

Basic Transformation

Suppose vertex v has capacity 7.

Replace:

v

with:

v_in -> v_out

where:

capacity(v_in, v_out) = 7

Original edges:

a -> v
v -> b
v -> c

become:

a -> v_in
v_out -> b
v_out -> c

Any flow passing through v must cross:

v_in -> v_out

so the vertex capacity is enforced.

Example

Original graph:

s -> a -> t
s -> b -> t
a -> b

Suppose vertex b has capacity 3.

Split b:

b_in -> b_out
capacity = 3

Transformed graph:

s -> a
a -> t
a -> b_in
s -> b_in
b_out -> t
b_in -> b_out

Now all flow that uses b must pass through the internal edge:

b_in -> b_out

No more than 3 units can traverse b.

Why It Works

A vertex capacity limits total transit flow.

In the split graph, every path entering the original vertex must enter v_in, cross the internal edge, and leave through v_out.

The internal edge is the only bridge between the incoming side and outgoing side.

Therefore:

flow through v ≤ capacity(v)

becomes an ordinary edge-capacity constraint:

flow(v_in, v_out) ≤ capacity(v)

This lets you use any standard max-flow algorithm without modification.

Source and Sink Handling

Be careful with the source and sink.

If the source has no capacity limit, do not constrain it. Either leave it unsplit or split it with infinite capacity.

If the sink has no capacity limit, do the same.

If the problem explicitly limits production at the source or consumption at the sink, then split them too.

Example:

source capacity = 100

Use:

s_in -> s_out
capacity = 100

and treat s_out as the flow source, depending on the exact modeling convention.

Directed Graphs

For a directed edge:

u -> v

after splitting both endpoints, the transformed edge becomes:

u_out -> v_in

Then each vertex internal edge enforces its own capacity.

Rule:

original edge u -> v
becomes u_out -> v_in

Undirected Graphs

For an undirected connection:

u -- v

model it as two directed edges:

u_out -> v_in
v_out -> u_in

If the undirected edge itself has shared capacity, the modeling becomes more subtle. Two opposite directed edges each with capacity c allow up to 2c total opposite-direction usage. To enforce shared capacity, introduce an intermediate edge-capacity gadget or model the problem as a directed equivalent if direction is fixed.

Multiple Capacities

A model may have both edge capacities and vertex capacities.

Original edge:

u -> v
capacity = 5

with split vertices becomes:

u_out -> v_in
capacity = 5

The edge capacity limits the connection. The internal edge limits the receiving vertex.

Both constraints apply.

Example: Router Throughput

Suppose packets move through routers:

Edge	Link Capacity
s -> A	10
s -> B	10
A -> R	10
B -> R	10
R -> t	20

Router R can process only 12 units.

Without vertex capacity, max flow is:

20

After splitting:

R_in -> R_out
capacity = 12

all traffic through R is capped at 12.

The correct max flow becomes:

12

Example: Worker Task Throughput

Suppose one worker can perform up to two tasks.

A simple matching network gives each worker capacity 1:

source -> worker
capacity = 1

To allow two tasks, use:

source -> worker
capacity = 2

This is simpler than node splitting because the worker is adjacent to the source.

But when the worker appears as an internal processing node in a larger graph, node splitting is the general solution.

Lower Bounds with Vertex Capacities

If a vertex must process at least l units and at most c units, split it and put a lower-bounded edge between its two copies:

v_in -> v_out
lower = l
capacity = c

Then apply the lower-bound transformation from the previous recipe.

This is a common pattern in staffing and demand satisfaction models.

Implementation Pattern

Assign two IDs for every original vertex:

in[v]  = 2 * v
out[v] = 2 * v + 1

Add:

addEdge(in[v], out[v], vertexCapacity[v])

For every original edge:

u -> v

add:

addEdge(out[u], in[v], edgeCapacity[u][v])

Run max flow on the transformed graph.

Choosing Infinity

When a vertex should be unconstrained, use a capacity large enough that it cannot become the bottleneck.

A safe value is often:

sum of capacities leaving the source

or:

sum of all positive capacities

Use 64-bit integers when capacities may be large.

Avoid using the maximum integer value directly if later additions may overflow.

Complexity

Node splitting doubles the number of vertices:

V' = 2V

It adds one internal edge per vertex:

E' = E + V

The transformed graph remains linear in the original graph size.

The dominant cost is still the max-flow algorithm.

Common Mistakes

Connecting to the Wrong Side

Incoming edges must go to v_in.

Outgoing edges must leave from v_out.

The common transformation is:

u_out -> v_in

Forgetting the Internal Edge

Without:

v_in -> v_out

there is no way to enforce the vertex capacity.

Constraining Source or Sink Accidentally

Only split source or sink with finite capacity when the problem explicitly requires it.

Mishandling Undirected Shared Capacity

Two directed edges do not enforce one shared undirected capacity.

Using Too Small an Infinity

An artificial infinity that is too small silently changes the problem.

Discussion

Vertex capacity is a modeling issue. Max-flow algorithms do not need special support for it. By splitting a vertex into an input side and an output side, you turn a vertex constraint into an ordinary edge constraint.

This is a recurring theme in network-flow modeling: if a constraint is awkward in the original graph, change the graph so that the constraint becomes a standard capacity constraint.

Takeaway

To enforce a vertex capacity, split the vertex into v_in and v_out, connect them with an edge whose capacity is the vertex limit, route all incoming edges into v_in, and route all outgoing edges from v_out.

After this transformation, any standard max-flow, min-cut, or min-cost-flow algorithm can be applied unchanged.