15-451 Algorithms: recitation notes 10/20/10
* Network flow, Ford-Fulkerson
* A few problems you can use max flow to solve
=========================================================================
NETWORK FLOW, FORD-FULKERSON
============================
- Pick some flow graph and run through the Ford-Fulkerson algorithm for
finding a max flow, having the class help construct the new residual
graphs. Can also keep track of flows in a separate "flow graph"
using "flow/capacity" notation on the edges.
PROBLEMS YOU CAN USE NETWORK FLOW TO SOLVE
==========================================
PROBLEM 1:
---------
Say you have a graph G and a collection of source/sink pairs
(s_1,t_1),(s_2,t_2),...,(s_k,t_k). You want to route a path from each
s_i to corresponding t_i that don't overlap in any edges (if
possible). E.g., think of routing calls in a network where no two
calls can share an edge. Turns out this problem is NP-complete. But
what if we don't care which s_i goes to which t_j so long as it's 1-1?
E.g., s's might be different people who want to download a movie, and
t's might be different sites that have the movie.
Any ideas? Use network flow. super-source connected to all s_i and
super-sink connected to all t_i. All edges of capacity 1. Model
undirected edge as edge in each direction. Claim: this has a flow of
value k iff original problem has a solution. Any integral max flow
gives a solution. What if flow uses some edge in both directions?
PROBLEM 2:
---------
Here is an application to 3-D image processing. The way you get a 3-D
image is you take a stereo camera that produces two pictures, and then
you match them together to produce a single image, where each pixel is
labeled with its depth in the image. The problem is that this process
can produce a lot of noise because of mistakes in matching things up.
So you need a way to fix those mistakes. One approach is to use the
fact that in general, most objects have small boundaries, which means
that most pairs of neighboring pixels will be at the same depth.
Can formalize the problem like this: Given a pixel image I, where each
pixel is 0 or 1 (indicating close or far --- in actual applications,
usually have many depth levels, but we will just consider 2 levels),
we want to find the best modification I' of I using the following
criteria: let's say we have to pay $a for each bit of I that we flip,
and we have to pay $b for each pair of neighboring pixels in I' that
are at different depths. For instance, if we decide to not change I
at all (I' = I) then we pay b*(# neighboring pixels in I that are at
different levels). If we decide to just make all depths equal to 0,
we pay a*(# of ones in I).
How can we solve for the best I'? Claim: can set this up as a min-cut
problem, and solve using our max-flow algorithms.
Here's how we do it: set up 0-source and 1-sink. Connect source to
all 0s, and sink to all 1's by edges of capacity a. Connect
neighboring pixels by edge of capacity b. Claim: any solution
corresponds to a cut, with cost = value of cut, and vice-versa. More
specifically, cutting an edge from s corresponds to flipping a 0 to a
1, cutting edge into t corresponds to flipping a 1 to a 0, and cutting
an edge between two neighboring pixels corresponds to paying $b for
having the pixels at different depths. So, given a cut, we can
associate the solution in which everything s can reach is labeled 0
and everything else is labeled 1. So, we just want the min S-T cut.
=======================================================================
Mini 4 problems from last semester
1. (a) What is the maximum s-t flow in the graph G below?
(b) Draw the residual graph you get at the very end of running the
Ford-Fulkerson algorithm on this graph. (There is more than
one legal answer)
3 5
s------->a-------->b
| ^ |
|4 |3 |4
| | |
v 5 | 2 v
c------->d-------->t
2. Suppose we use the Ford-Fulkerson algorithm to solve a Maximum
Bipartite Matching problem. The very first path P found will
necessarily have only 3 edges in it, but it is possible for later
iterations to find paths of more than 3 edges. E.g., in the
example in class on Tuesday, the last path found had 5 edges. Give
an example of a bipartite graph where it is possible for one of the
paths found to use 9 edges.