Remember Ford-Fulkerson…
With no smart choice of augmenting paths, we had a terrible worst-case runtime:
O(m f*), where f* is the value of the max flow
Copyright By PowCoder代写 加微信 powcoder
Today: in all of our examples, f* is going to be small.
For this reason, today, we don’t need to think about any fancy augmenting path choices like Edmonds-Karp, capacity scaling, etc.
The capacities are already small.
———-
Here’s a valid matching:
Invalid one:
can’t use vertex a twice like this.
———-
Bipartite Matching
Here is the undirected graph that we used today:
A matching with 2 edges (that cannot be extended any further):
{(v2, v6), (v4, v8)}
A matching with 3 edges; a maximum matching here:
{(v0, v6), (v2, v7), (v3, v8)}
———-
The goal is to construct a flow network for arbitrary instances of the maximum-matching problem. Four concerns:
1. The above graph has no source vertex.
2. The above graph has no sink vertex.
3. The above graph is undirected (not directed).
4. The above graph has no edge capacities.
Here is the flow network that we get by following the approach discussed today:
That is: you add an edge from s to each vertex in L. You make each undirected edge u–v into the directed edge u->v. And you add an edge from each vertex in R to t.
Now we will find a maximum flow in the flow network. What does that give us?
1. It gives us the number of edges in a maximum-matching, and
2. It also gives us the edges themselves
So we have reduced maximum-matching to maximum-flow.
The proof that our reduction is correct goes in two steps:
1. If M is a matching in G, then there is a flow in G’ with value |M|.
For this direction, we are given that there is a matching M in G with |M| edges. To find a flow in G’ with value |M|, give a flow of 1 to 3 edges for each edge (u, v) in M: (s, u), (u, v), (v, t).
Prove to yourself that this is a valid flow with value |M|!
The intuition for why the flow has value |M| is that each of the |M| edges causes 1 flow to be added on an edge from s.
2. If there is a flow in G’ with value M, then there is a matching in G with M edges.
Check the slides for the details.
With this proof, we can find a maximum-matching by finding a maximum-flow.
———-
Claim: In any given maximum flow of G, there is no cycle that carries flow
This is still a max flow (flow value 1), and it pushes flow along a cycle.
You can remove the flow along the cycle without changing the value of the flow.
———-
Edge-Disjoint Paths
These are edge-disjoint:
a->b->c->d
a->c->g->d
Let’s say we want to find the maximum number of edge-disjoint paths from v0 to v7.
Set s = v0, t = v7
Now we have to set edge capacities
Let’s try setting each edge capacity to 1
Is this a correct reduction?
G is original graph; G’ is flow network.
To construct G’ from G: set s to be a, set t to be b, set each edge capacity to 1.
1. If there are k edge-disjoint paths in G, then there’s a flow with value k in G’.
For each edge-disjoint path in G, I want 1 unit of flow to go through G’.
Think about v0->v1->v6->v7
Take each of these edges, and put flow 1 on the edge.
That gives me 1 unit of flow leaving v0.
I do that for each path… we get a flow value of k.
2. Now for the other half of the proof:
We’re given a flow in G’ with value k.
What we have to do is find k edge-disjoint paths in original graph G.
Imagine that G’ has some flow with value k > 0.
This must mean that there is some edge that carries 1 flow from the source.
So vertex a has 1 unit of flow coming in from s.
Therefore, it must have 1 unit of flow leaving a.
Now b has 1 flow coming in, so…
Where do we hope we end up?
s->a->b->…->…->t
If we can do this, then this is one of the k paths that we need.
Then we can remove the flow along this path; this decreases the value of the flow from k to k-1. Now, inductively, find k-1 paths in the remaining flow of value k-1.
s->a->b->…->…->t
this may not happen.
We might instead have
s->a->b->c->d->…->…->b
(See this week’s handout, question 1) If you have a cycle that carries flow, then we can remove the flow on this cycle without decreasing the flow value.
Remove the flow on this cycle -> what’s left?
We still have a flow of value k, and we have one fewer cycle.
You can’t remove cycles forever; eventually, our path from s has to take us to t.
Here’s a question: value of max flow == max number of edge-disjoint paths.
e.g. you return a value of 2
But how do you find what those paths are, using the max flow?
Keep finding paths from s to t that carry flow; if you find a cycle, remove its flow and try again.
———-
We’ve discussed two max flow reductions so far.
How can you tell that a problem can be reduced to max flow?
One signal: does it involve some sort of matching?
e.g. matching vertices in bipartite graphs
e.g. matching a sequence of edges in a path in the edge-disjoint paths problem
How about min cut then?
Remember a cut: partition of vertices so that s is in one set and t is in the other.
({s, v2, v4}, {t, v1, v3})
You’re splitting up the vertices here.
For each vertex, you’re deciding which type of vertex it is. i.e. does it go with s or does it go with t?
Super famous example of min cut reduction: image segmentation.
You have an image with a bunch of pixels; think of each pixel as a vertex.
Your job is to segment the image into foreground and background.
For each pixel, decide whether it goes in the foreground (that’s one type of vertex) or background (that’s the other type of vertex).