covers the max flow topic in [[00_Plan]]

Definitions¶

A flow network is a graph \(G(E,V, c)\), where \(c\) is the capacity of each edge. Intuitively, we can think of each edge as a one-way road, where capacity is the number of lanes

A flow is the specific amount of flow we push across each edge in \(G\)

A valid flow fulfills 2 conditions - no edge capacity is exceeded - all vertices other than s and t must conserve flow (release as much as it receives) Total flow is the flow leaving the source, which should equal the flow entering the sink in a valid flow. Gross flow is the flow on a directed edge \((u,v) \in E\) for any vertex, the gross flow entering an edge - gross flow leaving the edge should be zero (rule 2 of valid flow) only covers magnitude, not direction

Gross flow is defined with respect to edges, but we really care about flow with respect to vertices Net Flow : lets us define the net direction of flow across a vertex imagine if g(u,v)=3, and g(v,u)= 10, then f(u,v)=-7 - \(f(u,v) = -f(v,u)\) - this ensures no cycles length 1 or 2 - flow conservation: \(\sum_u f(u,v) = 0\) The net flow of each vertex aside from the source and sink is 0 Notes - f(u,v)=0 if \((u,v), (v,u)\) not in \(E\)
- \((u,v)\) and \((v,u)\) can't both be in gross flow and graph \(G(V,E)\) - why? what does this even mean?

Value of flow: \(|f| = \sum_v f(s,v)\) The value of a flow is the net flow out of the source

Maximum flow problem¶

• \(f=0\) is an allowed flow in any network (may be useful for induction)
• any feasible cycles are valid flows, although its value is zero
• For any path \(s-->t\) , any flow along that path \(\leq\) its least capacity is valid (limiting reagent)

Flow Decomposition Lemma¶

Any flow can be decomposed into a collection of s-t paths and flow cycles remember that flow is the amount of flow we push across each edge - it's not the graph itself. It directly follows that - Fact 1: flow decomposition leads to # s-t paths + # flow cycles \(\leq\) # edges of nonzero capacity - Fact 2: if \(|f| > 0\), there has to be \(\geq\) 1 s-t flow path (can't have only cycles) important insight: I think flow decomposition is useful because it lets us separate the useful (s-t paths) from the distracting (cycles)

FD lemma proven by induction, and the insight that because of flow conservation, each vertex \(v\) that receives flow must deliver it to another vertex. So we can continue to search the path that a vertex delivers flow to until we either 1) reach the sink or 2) return the same vertex

Finding a maximum flow¶

Let \(f*\) be a max flow in G, and \(F*\) be the total flow of \(f*\)

How can we check if F* > 0? If there's an \(s-->t\) path in G of positive capacity edges, then the path can support positive flow (connects later to augmenting paths)

S-T cuts¶

An S-T cut creates a disjoint subset of vertices \(S, V - S\) , where \(s \in S\), and \(t \in V-S\) I believe the subsets must be connected The capacity of a cut \(c(s)\) defines the total capacity of edges that leave S \(\(c(s) = c(S, V-S) = \sum_{u \in S} \sum_{v \in V-S} c(u,v)\)\) If there exists an s-t cut such that \(c(s) = 0\), then that means there's no viable s-t path (since S is entirely made up of cycles) intuitevly, if there's the capacity out of S is 0, then there's no way to transfer flow from S to T.

How can we certify that \(F*=0\)? show there's an ST cut with c(s)=0

S-t paths and s-t cuts are dual to each other

Flow of a cut : F(S) defines the net flow from S to T, including negative flow from T to S! consequently, we can have negative net flow from cycles

Fact 1: f(S) = f(S') for any two s-t cuts S and S all S-T cuts therefore have the same net flow the intuition is that when we decompose into cycles and s-t paths, the cycles don't contribute anything to the sink: only the s-t paths contribute. consequently, any flow that's leaving S either cancels out in a cycle, or makes it to t

Fact 1.5: \(|f| = f(S)\) for any cut \(S\) this holds from fact 1, since we can let \(S={s}\)

Note how many of these facts are derived from a combination of flow decomposition and flow conservation

Fact 2: Weak duality of flows and s-t cuts: \(F^* = f^*(S^*) \leq C(S^*)\) max flow is \(\leq\) capacity of min s-t cut

The s-t cut problem : given a flow graph, find an s-t cut of minimum capacity

remember, s-t cuts have the same net flow, but different minimum capacities further, capacities are a function of the network, while flows are a function of the specific flow identified

We want to increase a flow until it's a max flow by iteratively adding s-t paths and increasing flow until they're at the min capacity challenge is sometime we'll need to decrease flow in one area to increase it in another. this is resolved by residual networks

Residual Networks¶

Let f be a net flow on \(G=(V,E)\)
Residual network \(G_f(V, E_f)\) is a weighted, directed graph where for every \((u,v) \in E\), if there's residual capacity such that the edge can take more flow, then there's an edge in the residual network with weight equal to how much we can increase flow until it's at capacity \(c_f(u,v) = c(u,v) - f(u,v)\) \(c_f(v,u) = c(v,u) - f(v,u)\) the first term \(c_f(u,v)\) creates an edge if there's additionally flow we can push along an edge the second term \(c_f(v,u)\) creates an edge if we're already pushing flow along an edge, allowing us to decrease flow along the edge Bidirectional edges in \(G_f\): If \((u,v) \in E\) and \(0 < f(u,v) \leq c(u,v)\) i.e for any edge with nonzero flow, the residual will have an edge in the opposite direction with capacity equal to the flow we're pushing

Fact: \(|E_f| \leq 2|E|\)

Pushing flow on edges of the residual corresponds to either increasing flow on edges of G towards full capacity or decreasing flow on edges of G.

![[Pasted image 20221113180323.png|700]]

Augmenting Paths¶

Any \(s-t\) path in \(G_f\) is an augmenting path in G with respect to \(f\). The flow value can be increased along an augmenting path by the minimum capacity of the residual along that path

![[Pasted image 20221113180602.png|500]]

Max-Flow, Min-Cut Theorem¶

A max flow \(f\) admits no augmenting paths, and has an S-T cut with capacity equal to \(|f|\)

can there exist an F* < c(S,T) for all S,T? For the net flow \(f\), the following are equivalent: - \(|f| = c(S,T)\) for some cut \((S,T)\) - since c(S,T) provides an upper bound on the amount of flow that can exit a cut - f is a maximum flow - f admits no augmenting paths

Proof¶

![[Pasted image 20221113185547.png]] ![[Pasted image 20221113185555.png]]

Algorithms for max flows¶

Ford-Fulkerson Algorithm¶

Push flow through augmenting paths until no more exist Obviously correct because no augmenting paths --> max flow

Runtime¶

can have slow runtime because chosen augmenting paths may not be the most effective Each iteration takes \(O(|E|)\) to find and push flow through augmenting path

We can bound running time by defining a max capacity \(C\) that any edge can hold We may only be able to increase flow by 1 at each iteration, so num iterations \(\leq F* \leq c(\{s\}) \leq nC\) - \(F^* \leq c(\{s\})\) because flow cannot exceed the capacity of any s-t cut - \(c(\{s\}) \leq nC\) because the max capacity of each edge is \(C\), and the source could be connected to all \(n\) vertices

Total runtime is \(O(EVC) = O(EF^*)\) -pseudopolynomial algorithm: polynomial in sum of input numbers

Note that if we know the bound on \(C\), then the algorithm runs faster than edmonds-karp!

Gross inefficiency¶

Cycles can create cyclic alternating paths ![[Pasted image 20221113191604.png]]

Flow Integrality Theorem¶

If \(G=(v,E,s,t,c)\) has all integral capacities, then there exists a flow f with all integral values this is useful when we model real-world problems that require integral values as a flow problem. This helps us show correctness, and that the solution will be a valid integral solution to the problem

Edmonds-Karp Algorithm¶

choose the shortest augmenting path via BFS of augmenting paths \(O(E^2V)\) each BFS is \(O(|E|))\) at worst to find the shortest augmenting path. At most \(O(VE)\) augmenting paths can be found, since...? (edmonds-karp lemma) Every time, at least one of the edges becomes saturated (max possible flow), so O(|E|) visits to each edge, and the distance from the saturated edge to the source along the augmenting path increases monotinacally, such that the length of the augmenting path is at most \(|V|\)

Applications¶

Bipartite Graph Matching¶

Super simple flow formulation. We just add a source for one set and a sink on the other, each with edges of cap 1. Then just search for the max flow. Because each node on the right set has cap 1 to sink, it can only receive flow from one edge. Since each node on the left can only receive flow 1 from source, it can only deliver flow 1. notice that the proof is simple once we've figured out the formulation.

How could I have figured this out myself? Thinking about the relationship between nodes, we want to restrict the recipient to only connect to one L node, so we want the delivery edge to the sink to be 1. Likewise the L can only connect to one other vertex, so we want L to only have cap 1 to deliver, so source to each L node should also be 1. Thus, this becomes obvious when we think about how we want to restrict each node's interactions. note that we also preserve the original bipartite graph and add our own things ![[Pasted image 20221113212740.png]] ![[Pasted image 20221113212803.png]] Proof: - maximal matching is no greater than max flow - Suppose we have the maximal matching M - we can let the edges in the matching be the edges in the flow since the capacity is 1 between vertices. - a flow based on the maximal matching (where each edge between a match has a flow > 0) is \(|f|\), which obviously can't be greater than F, so \(|f| \leq F^*\) - max flow is no greater than maximal matching

Baseball Elimination¶

![[Pasted image 20221113220539.png]]

![[Pasted image 20221113220549.png]]

Tips¶

In general, a huge help would be the ability to draw connections between problems we've tried and the question being asked. And so every time I solve a question, definitely want to identify takeaways and the details in the question which let me solve it. - Oftentimes when we translate a problem to max flow, we have to create the source and sink as made-up nodes, rather than something already existing - To come up with translation between a problem and flow, identify the relationships and constraints that each relationship has - think about the restrictions in the problem, and how we can use capacity to create these restrictions. - Cuts can be meaningful. Think about the mars question and the machines question [[Flow]] from bipartite matching problem - to show a max flow gives us the exact value of the optimum for our task, we show that if we have the argmax for our task, the argmax is \(\leq F*\), and \(F^* \leq argmax\) - cuts don't actually have to be a single line or continuous. Can be scattered as well, as long as it's some partition of vertices! Writing out thoughts takes a lot of time. use many abbreviations, and try to keep things in head too

Problem Takeaways¶

Generally, quiz questions will have relatively intutive answers, not many "gotchas" don't have time to write out thoughts. use many abbreviations, take a deep breath before every question, think about things lucidly

Recitation Q1¶

![[Pasted image 20221114162217.png|700]] from the hint, we know that the min-cut is the key. We intutively understand immediately that a min-cut of the red vs blue would give us the solution. So how can we design a flow diagram where c(S) gives us the cost of making that partition? - every edge that crosses c(S) would be a border between red and blue, so we would need a fence (so \(c_f\)) between nodes - every node that gets sold must have an edge crossing S with cost of selling - be sure to draw a simple example problem to help reason and rapidly prototype