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

Multi-Commodity Flow Introduction

Introduce multi-commodity flow problems where multiple types of flow share network capacity.

Multi-Commodity Flow Introduction

What you'll learn: How to model network flow problems where multiple independent flows must share the same network capacity.

The Core Idea

Until now, we've worked with single-commodity flow: one type of "stuff" flowing from source to sink. But real networks often handle multiple different flows simultaneously. Multi-commodity flow extends the maximum flow problem to scenarios where k different commodities (each with its own source and sink) must share the same network edges.

Think of a telecommunications network: multiple phone calls (commodities) route through the same physical cables (edges), each call needing its own path from caller to receiver. Unlike single-commodity flow, you can't just merge flows—Call A and Call B are distinct and need separate paths, even though they share capacity.

Key Characteristics

Each commodity i has:

  • Its own source node s_i
  • Its own sink node t_i
  • Its own flow value or demand d_i

The crucial constraint: the sum of all commodity flows on any edge cannot exceed that edge's capacity. This creates competition for resources.

Why It's Harder

In single-commodity flow, you don't care which path the flow takes. With multiple commodities, you must track which commodity uses which edges. This makes the problem significantly more complex—in fact, even deciding if a feasible multi-commodity flow exists can be NP-hard for certain variants.

Applications

  • Network routing (internet traffic)
  • Transportation logistics (different cargo types)
  • VLSI chip design (wire routing)
  • Railway scheduling (different train routes)

Key Takeaway: Multi-commodity flow models realistic scenarios where multiple independent flows compete for shared network capacity, requiring careful coordination to satisfy all demands without exceeding edge capacities.