Exercises

For a directed graph $G = (V, E)$ with integer edge capacities, source $s$, and sink $t$: $\text{maxflow}(s, t) = \text{mincut}(s, t)$.

For unicast, this means the capacity of the network (the maximum rate of information transfer from $s$ to $t$) equals the capacity of the tightest bottleneck (minimum cut). This is achievable by routing alone.

$\min_k \text{mincut}(s, t_k) = \min(2, 2) = 2$ symbols per time unit. This is achieved by network coding (XOR at node $w$).

With routing, the edge $w \to x$ can carry either $a$ or $b$ but not both. One sink receives both bits, the other receives only one. Routing achieves multicast rate 1 (only one bit delivered to both sinks).

The gap: network coding achieves rate 2, routing achieves only rate 1.

Path 1: $s \to a \to t$, flow = 3 (limited by $a \to t$).

Path 2: $s \to b \to t$, flow = 4 (limited by $s \to b$).

Path 3: $s \to a \to b \to t$. Residual on $s \to a$ is $5 - 3 = 2$. $a \to b$ has cap 2. $b \to t$ has residual $6 - 4 = 2$. Flow = 2.

Total: $3 + 4 + 2 = 9$.

Cut $\{s\}$: cap = $5 + 4 = 9$. Cut $\{s, a\}$: cap = $4 + 3 + 2 = 9$. Wait: $a \to b$ crosses the cut only if counted correctly. $\{s, a\}$ vs $\{b, t\}$: edges $s \to b$ (4), $a \to b$ (2), $a \to t$ (3). Total = 9. Cut $\{s, b\}$: cap = $5 + 6 = 11$. (Not minimum.) Cut $\{s, a, b\}$: cap = $3 + 6 = 9$.

Min-cut = 9 = max-flow. $\checkmark$

The max-flow min-cut theorem says that routing alone achieves the unicast capacity (the min-cut). Since the min-cut is also an upper bound for any scheme (including network coding), routing is already optimal.

Network coding can only help when multiple sinks need the same data (multicast), because coding creates packets that are simultaneously useful to different sinks with different side information. For unicast, there is only one sink and no such diversity benefit.

The sink observes $y_i = \mathbf{g}_i^T \mathbf{a}$ for $i = 1, \ldots, h$, which can be written as $\mathbf{y} = \mathbf{M}\mathbf{a}$ where $\mathbf{M} = [\mathbf{g}_1, \ldots, \mathbf{g}_h]^T$ is the $h \times h$ transfer matrix.

The sink can uniquely recover $\mathbf{a}$ if and only if $\mathbf{M}$ is invertible over $\mathbb{F}_q$, i.e., $\det(\mathbf{M}) \neq 0$ in $\mathbb{F}_q$.

Decoding is by Gaussian elimination: $\mathbf{a} = \mathbf{M}^{-1}\mathbf{y}$, with complexity $O(h^2)$ field operations.

$\text{mincut}(s, t_1)$: cut $\{s\}$ gives cap 3, cut $\{s, r_3\}$ gives cap 2 (edges $s \to r_1$ and $s \to r_2$, but $r_3 \to t_2$ doesn't help $t_1$). Actually: $t_1$ receives from $r_1$ and $r_2$ only, so $\text{mincut}(s, t_1) = 2$.

$\text{mincut}(s, t_2)$: $t_2$ receives from $r_2$ and $r_3$ only, so $\text{mincut}(s, t_2) = 2$.

Multicast capacity $= \min(2, 2) = 2$.

Source produces $\mathbf{a} = (a_1, a_2) \in \mathbb{F}_3^2$.

• $s \to r_1$: $a_1$ (vector $(1, 0)$)
• $s \to r_2$: $a_2$ (vector $(0, 1)$)
• $s \to r_3$: $a_1 + a_2$ (vector $(1, 1)$)

Each relay forwards its received symbol:

• $r_1 \to t_1$: $a_1$
• $r_2 \to t_1$: $a_2$
• $r_2 \to t_2$: $a_2$
• $r_3 \to t_2$: $a_1 + a_2$

$t_1$: receives $(a_1, a_2)$, transfer matrix $\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$. Trivially decodable.

$t_2$: receives $(a_2, a_1 + a_2)$, transfer matrix $\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}$, $\det = -1 = 2 \neq 0$ in $\mathbb{F}_3$. Decodable.

Note: the coding happens at the source, not at intermediate nodes. The relays simply forward. The source "pre-codes" by sending $a_1 + a_2$ on the third edge.

By flow conservation at all nodes in $S \setminus \{s\}$: $$|f| = \sum_{v \in S} \left(\sum_{e \in \text{out}(v)} f(e) - \sum_{e \in \text{in}(v)} f(e)\right)$$ (only $s$ contributes a net positive; all other nodes in $S$ cancel).

Splitting edges into those within $S$, those from $S$ to $S^c$, and those from $S^c$ to $S$, the internal edges cancel: $$|f| = \sum_{e \in E(S, S^c)} f(e) - \sum_{e \in E(S^c, S)} f(e).$$

Since $f(e) \leq c(e)$ for all edges and $f(e) \geq 0$: $$|f| \leq \sum_{e \in E(S, S^c)} c(e) - 0 = \text{cap}(S, S^c).$$

Since this holds for all cuts: $|f| \leq \text{mincut}(s, t)$. Since this holds for all flows: $\text{maxflow}(s, t) \leq \text{mincut}(s, t)$. $\blacksquare$

For each sink $t_k$, the determinant of the transfer matrix $\mathbf{M}_k$ is a polynomial of degree at most $h$ in the random coding coefficients. By Schwartz–Zippel, $\Pr[\det(\mathbf{M}_k) = 0] \leq h/q$ for a single random evaluation.

More carefully: the product $\prod_{k=1}^K \det(\mathbf{M}_k)$ is a polynomial of degree at most $Kh$ in the coding coefficients. By Schwartz–Zippel applied to each edge independently:

For each edge $e$, the conditional probability that choosing $e$'s coefficient creates a zero determinant at some sink is at most $K/q$. Over all $|E|$ edges: $$\Pr[\text{all sinks decode}] \geq \prod_{e \in E} (1 - K/q) = (1 - K/q)^{|E|}.$$

For $q = 256$ and $K = 10$, $|E| = 100$: $(1 - 10/256)^{100} \approx 0.98$. $\blacksquare$

Slot 1: A sends $a$ to R. Slot 2: R forwards $a$ to B. Slot 3: B sends $b$ to R. Slot 4: R forwards $b$ to A.

Slot 1: A sends $a$ to R. Slot 2: B sends $b$ to R. Slot 3: R broadcasts $a \oplus b$ to both A and B.

A knows $a$, so it computes $b = a \oplus (a \oplus b)$. B knows $b$, so it computes $a = b \oplus (a \oplus b)$.

The coding at R (XOR) saves one time slot — a 25% improvement.

Slot 1: A and B transmit simultaneously. R receives $y_R = h_{AR}a + h_{BR}b + n$. R decodes $a \oplus b$ from the superimposed signal (using lattice decoding or other techniques).

Slot 2: R broadcasts $a \oplus b$ to both A and B.

A and B decode as before. The simultaneous transmission in slot 1 saves another time slot — a 50% improvement over routing.

Broadcast $W_1 \oplus W_2 \oplus W_3$.

Receiver 1 knows $W_2$: $W_1 = (W_1 \oplus W_2 \oplus W_3) \oplus W_2 \oplus W_3$. But receiver 1 does not know $W_3$! So it cannot decode.

A single broadcast of $W_1 \oplus W_2 \oplus W_3$ does not work.

Try two broadcasts: $W_1 \oplus W_2$ and $W_2 \oplus W_3$.

Receiver 1 (wants $W_1$, knows $W_2$): $W_1 = (W_1 \oplus W_2) \oplus W_2$. $\checkmark$

Receiver 2 (wants $W_2$, knows $W_3$): $W_2 = (W_2 \oplus W_3) \oplus W_3$. $\checkmark$

Receiver 3 (wants $W_3$, knows $W_1$): $W_3 = (W_1 \oplus W_2) \oplus (W_2 \oplus W_3) \oplus W_1 = W_3$. $\checkmark$

Two broadcasts suffice. Can we do it with one? No — the 3-cycle requires at least 2 broadcasts (the fractional chromatic number of the complement graph is 3/2, so the optimal rate is 2 broadcasts for 3 messages).

Let $h = \min(\text{mincut}(s, t_1), \text{mincut}(s, t_2))$. We need to find coding coefficients such that both $\mathbf{M}_1$ and $\mathbf{M}_2$ are invertible over $\mathbb{F}_2$.

By Menger's theorem, there exist $h$ edge-disjoint paths from $s$ to $t_1$ and $h$ edge-disjoint paths from $s$ to $t_2$. Assign the identity coding along the paths to $t_1$: this makes $\mathbf{M}_1 = \mathbf{I}_h$ (invertible).

Now consider $\mathbf{M}_2$. By Menger's theorem and the edge-disjoint paths, $\mathbf{M}_2$ has rank $h$ over $\mathbb{R}$ (the paths to $t_2$ are linearly independent). For $K = 2$, we can always find binary coding coefficients on the shared edges such that $\mathbf{M}_2$ is also invertible over $\mathbb{F}_2$.

The formal proof uses the matroid intersection theorem: the intersection of the two graphic matroids corresponding to the two sets of edge-disjoint paths has a common independent set of size $h$ over $\mathbb{F}_2$.

For $K > 2$, this argument fails, and larger fields may be needed. $\blacksquare$

The source generates $\mathbf{a} = (a_1, \ldots, a_h) \in \mathbb{F}_q^h$ uniformly at random. The multicast rate is $h\log q$ bits per time unit.

For any sink $t_k$ and any $s$-$t_k$ cut $(S, S^c)$, the information reaching $t_k$ must pass through the edges crossing the cut.

Let $\mathbf{Y}_{\text{cut}}$ be the vector of symbols on edges crossing the cut $(S, S^c)$. Since $t_k \in S^c$, all information reaching $t_k$ is a function of $\mathbf{Y}_{\text{cut}}$ (no information can bypass the cut):

$$h\log q = H(\mathbf{a}) = I(\mathbf{a}; \mathbf{Y}_{t_k}) \leq I(\mathbf{a}; \mathbf{Y}_{\text{cut}}) \leq H(\mathbf{Y}_{\text{cut}}) \leq \sum_{e \in E(S, S^c)} c(e) \log q$$

where the second inequality uses data processing (since $\mathbf{Y}_{t_k}$ is a function of $\mathbf{Y}_{\text{cut}}$) and the last uses the fact that each edge symbol has entropy at most $c(e) \log q$ bits.

Dividing by $\log q$: $h \leq \sum_{e \in E(S, S^c)} c(e) = \text{cap}(S, S^c)$. Since this holds for all cuts: $h \leq \text{mincut}(s, t_k)$. Since this holds for all sinks: $h \leq \min_k \text{mincut}(s, t_k)$. $\blacksquare$

Consider the network:

• Sources $s_1, s_2$, sinks $t_1, t_2$, relay $r$
• Edges: $s_1 \to r$ (cap 1), $s_2 \to r$ (cap 1), $r \to t_1$ (cap 1), $r \to t_2$ (cap 1)

$t_1$ wants $W_1$, $t_2$ wants $W_2$.

Individual min-cuts: $\text{mincut}(s_1, t_1) = 1$, $\text{mincut}(s_2, t_2) = 1$.

Sum rate: cut $\{s_1, s_2\}$ gives cap $= 1 + 1 = 2$; cut $\{r, s_1\}$ gives cap $= 1 + 1 = 2$. So the cut-set bound allows $R_1 + R_2 \leq 2$ and $R_1 \leq 1, R_2 \leq 1$.

Node $r$ has two outgoing edges of capacity 1 each. To deliver $W_1$ to $t_1$, the edge $r \to t_1$ must carry (a function of) $W_1$. To deliver $W_2$ to $t_2$, the edge $r \to t_2$ must carry (a function of) $W_2$.

But $r$ has only 2 incoming units of capacity. If $R_1 = 1$ and $R_2 = 1$, $r$ receives $W_1$ and $W_2$ (2 symbols) and must route $W_1$ to $t_1$ and $W_2$ to $t_2$. This requires 2 outgoing capacity, which $r$ has. So $(R_1, R_2) = (1, 1)$ is achievable.

Now modify: add a third sink $t_3$ wanting $W_1$, with $r \to t_3$ (cap 1). The edge $r \to t_3$ must also carry $W_1$. But $r$ only has 3 total outgoing capacity. If $R_1 = 1$, $R_2 = 1$, then $r$ needs to send $W_1$ to both $t_1$ and $t_3$ (2 edges) and $W_2$ to $t_2$ (1 edge) — this requires the full 3 outgoing edges, leaving no room for coding. Network coding ($W_1 \oplus W_2$ on one edge) doesn't help because $t_1$ and $t_2$ want different data.

The achievable sum rate is constrained by the need to route different information to different destinations, which the cut-set bound does not capture.

Path: $s \to a \to c \to t$, bottleneck = $\min(10, 7, 10) = 7$. Push flow 7. Residual: $s \to a$: 3, $a \to c$: 0, $c \to t$: 3.

Path: $s \to b \to t$, bottleneck = $\min(8, 9) = 8$. Push flow 8. Residual: $s \to b$: 0, $b \to t$: 1.

Path: $s \to a \to b \to c \to t$, bottleneck = $\min(3, 5, 3, 3) = 3$. Push flow 3. Residual: $s \to a$: 0, $a \to b$: 2, $b \to c$: 0, $c \to t$: 0.

No more augmenting paths from $s$ to $t$ in the residual graph. Total flow = $7 + 8 + 3 = 18$.

Min-cut verification: $S = \{s\}$, cap = $10 + 8 = 18$. Also $S = \{s, a, b\}$, cap = $7 + 3 + 9 = 19$. And $S = \{s, a, b, c\}$, cap = $10 + 9 = 19$. Min-cut = 18 at $S = \{s\}$. $\checkmark$

A network coding problem can be associated with a matroid through the entropy function of the edge random variables. The achievable rate region depends on which entropy vectors are realizable over the coding field.

Over $\mathbb{F}_q$, the set of realizable entropy vectors is the set of polymatroidal rank functions of $\mathbb{F}_q$-representable matroids. Over $\mathbb{F}_2$, this set is strictly smaller than over $\mathbb{F}_3$ or larger fields.

Dougherty, Freiling, and Zeger constructed a network coding instance where the rate vector $(1, 1, 1)$ for three source-sink pairs is achievable over $\mathbb{F}_q$ for $q \geq 3$ but not over $\mathbb{F}_2$, even with nonlinear coding.

The construction uses the Fano matroid, which is representable over $\mathbb{F}_2$ but not over fields of characteristic $\neq 2$, and its dual, the non-Fano matroid, which is representable over fields of characteristic $\neq 2$ but not over $\mathbb{F}_2$. A carefully designed network requires both representations simultaneously, forcing $q \geq 3$.

This shows that the choice of alphabet (field size) fundamentally affects the achievable rate region for multi-source network coding — unlike single-source multicast, where the alphabet only affects the probability of random codes succeeding. For multi-source problems, some rate tuples are inherently impossible over binary alphabets regardless of the coding scheme. $\blacksquare$

Each user needs one file it doesn't have. Without coding: transmit $W_2, W_3, W_4, W_1$ separately — 4 transmissions.

Notice the circular structure: user 1 wants $W_2$ (cached by user 2), user 2 wants $W_3$ (cached by user 3), etc.

Transmission 1: $W_2 \oplus W_3$. User 1 (has $W_1$, wants $W_2$): needs $W_3$ — cannot decode yet.

Better approach: Transmission 1: $W_1 \oplus W_2$. User 4 (has $W_4$, wants $W_1$): cannot decode. User 1 (has $W_1$, wants $W_2$): $W_2 = W_1 \oplus (W_1 \oplus W_2)$. $\checkmark$

Transmission 2: $W_3 \oplus W_4$. User 2 (has $W_2$, wants $W_3$): cannot decode. User 3 (has $W_3$, wants $W_4$): $W_4 = W_3 \oplus (W_3 \oplus W_4)$. $\checkmark$

Transmission 3: $W_2 \oplus W_4$. User 2 (has $W_2$, wants $W_3$): cannot decode.

Actually, with this demand pattern, we can do: $W_1 \oplus W_2$: serves user 1 (knows $W_1$, gets $W_2$) and user 4 needs another coded. $W_3 \oplus W_4$: serves user 3 (knows $W_3$, gets $W_4$). $W_1 \oplus W_3$: user 2 knows $W_2$... doesn't help. $W_2 \oplus W_3$: user 2 knows $W_2$, gets $W_3$. $\checkmark$ User 4 still needs $W_1$. From $W_1 \oplus W_2$: needs $W_2$. From $W_2 \oplus W_3$: can get $W_2$ if has $W_3$... chain.

The minimum with pairwise XOR: 2 transmissions. $W_1 \oplus W_3$ and $W_2 \oplus W_4$:

• User 1 (has $W_1$, wants $W_2$): gets $W_2 \oplus W_4$, but doesn't know $W_4$. This doesn't work either.

The optimal coded scheme: 2 transmissions using the right XORs. $W_2 \oplus W_1$ and $W_4 \oplus W_3$: User 1: has $W_1$, wants $W_2$ → from $W_1 \oplus W_2$: $W_2 = (W_1 \oplus W_2) \oplus W_1$. $\checkmark$ User 2: has $W_2$, wants $W_3$ → from $W_3 \oplus W_4$: needs $W_4$. Doesn't help.

Correct: 3 transmissions minimum for this demand pattern with binary XOR of pairs. The coded caching approach (Chapter 27) achieves 2 transmissions for $t = KM/N = 1$.

In the butterfly network, the critical edges are those crossing cuts. The index coding formulation creates one "message" per source symbol and assigns side information based on which other source symbols each sink can receive through non-bottleneck paths.

Specifically: the butterfly has source symbols $a, b$. Sink $t_1$ can receive $a$ directly (via $s \to u \to t_1$) but needs $b$. Sink $t_2$ can receive $b$ directly (via $s \to v \to t_2$) but needs $a$.

The equivalent index coding problem: receiver 1 wants $b$ and knows $a$; receiver 2 wants $a$ and knows $b$. The optimal index code: broadcast $a \oplus b$ (1 transmission). Receiver 1: $b = (a \oplus b) \oplus a$. Receiver 2: $a = (a \oplus b) \oplus b$.

The total rate: 2 source symbols delivered using the direct paths (2 uses) plus the index-coded broadcast (1 use on the bottleneck edge $w \to x$). Each sink recovers both symbols. Multicast rate = 2, matching the network coding solution.

The reduction shows that the bottleneck of the butterfly network is precisely the index coding problem on the shared edge $w \to x$, and the XOR solution is the optimal index code for the resulting side information structure. $\blacksquare$

(a) Practical adoption:

• Content distribution: Microsoft's Avalanche (2005) demonstrated RLNC in P2P, but BitTorrent remained dominant due to simplicity. Steinwurf's Kodo library provides commercial RLNC for storage and streaming.
• Wireless mesh: COPE (MIT, 2006) showed 2–4x gains in testbeds, but limited deployment due to protocol complexity.
• Distributed storage: Facebook's Warm Storage uses erasure codes (related to network coding) for data redundancy.
• 5G and beyond: Coded caching concepts are influencing edge computing architectures for content delivery.

(b) Barriers:

• Protocol inertia: TCP/IP assumes packet-level operations; integrating coding requires cross-layer design.
• Latency: RLNC adds buffering delay ($h$ packet times for decoding).
• Computational cost: GF(256) operations are cheap per-packet but add CPU load at scale.
• Complexity: network coding requires careful management of coding coefficients, linear independence, and recoding at intermediate nodes.

(c) Coded caching connection: Coded caching (Maddah-Ali–Niesen, 2014) is a form of network coding where the "network" consists of a server, edge caches, and users. The placement phase fills caches with uncoded content; the delivery phase uses coded multicast (XOR-like operations) to serve multiple users simultaneously. The coding gain is a direct consequence of the network coding principle: coded packets are useful to multiple receivers with different side information.

(d) Theory-practice gap: The gap is narrowing in specific domains (coded caching, distributed storage) but remains wide for general wireless network coding. The theoretical gains assume idealized models (noiseless links, perfect synchronization, known topology) that are hard to realize in practice. The most impactful legacy of network coding may be the conceptual shift — the idea that intermediate nodes should process data, not just route it — which now permeates edge computing, in-network computing, and programmable networks.