15-451/651 Algorithms: recitation notes 10/16/13
* More problems solvable using Network Flows
=========================================================================
In case you didn't get a chance to cover any of the problems from last
time, they are at the end of the writeup.
PROBLEM 1:
----------
Given a digraph, a *cycle cover* is a set of arcs that form
vertex-disjoint cycles, such that every vertex in the graph is part of
at least one cycle. (By the vertex-disjointness of the cycles, each node
is part of exactly one cycle.) How do you find a cycle cover efficiently
(or report no cycle cover exists)?
(a) Observe that we have a set of arcs E' subset of E such that each
vertex has exactly one incoming arc and exactly one outgoing arc, if and
only if E' forms a cycle cover of the graph.
(b) How do you find one? use bipartite matchings! Given G = (V,E), form
the graph H whose vertex set is two copies of V (call them V_L and V_R)
so that each vertex v has two copies (called v_L and v_R as well).
For each arc (u,v) in E, add an arc (u_L, v_R) to H. Now find a perfect
matching in H. Observe that every perfect matching in H corresponds to a
cycle cover in G.
Aside: Such cycle covers arise in problems of kidney matching, where
each vertex corresponds to a donor-recipient pair such that the donor's
kidney cannot be given to that recipient. An arc (u,v) means the donor
of u can give her kidney to the recipient of v. A cycle cover is what
we'd like to find. Ideally we'd like to find cycle covers with short
cycles --- that turns out to be a harder problem.
PROBLEM 2: A GENERAL FLOW MODEL
-------------------------------
We've been studying maximum s-t flows, but everything we've said also
works for the following problem: find a capacity-respecting flow of
value d going from s to t (if possible). Basically, you can find a
maximum flow: if this has value less than d then you say "Not possible",
else you can drop part of this flow and return a flow of value d.
Yet another way of phrasing the question is: find a flow with excess
(-d) at s and excess d at t. (Recall: excess at a node is the total flow
in minus the total flow out.) The excess at all other nodes must be 0,
i.e., there is flow conservation at the non {s,t} nodes. Different
wording, same problem.
Now suppose I gave you target excess values b_v for each node. I.e., you
want a flow that achieves excess b_v at each node. (Call this the b-flow
problem.) How do you do this?
Ideas? [Reduce to sending d units of flow from s to t.] Suggestions?
Observation: The total excess must be 0. I.e., \sum_v b_v = 0. (By
conservation of mass, flow must start somewhere and end somewhere.) So
unless b_v = 0 for all nodes (in which case the empty flow is a
solution), some nodes must have positive excess, others negative, and
any remaining ones zero excess.
Good. Now you can reduce the b-flow problem to your familiar s-t
flow problem. Add a new "supersource" S, and "supersink" T. For each v
with b_v < 0, add a new arc (S,v) with capacity (-b_v). For each v with
b_v > 0, add a new arc (v,T) with capacity b_v. Try to send
B = sum_{v with positive b_v} b_v
amount of flow from S to T.
If there was a solution to b-flow there is a solution to this instance
by adding the flows on the new arcs, from S to the negative b_v guys and
from the positive b_v guys to T. And similarly if there is a solution to
this instance, you can get a solution to the b-flow instance by dropping
the flows on the new arcs.
Note: this is pretty much what you did in bipartite perfect matching,
there you want to send one unit of flow from the left guys (they have
b_v = -1) and receive one unit of flow at the right guys (have b_v = 1).
PROBLEM 2b:
What if, in addition to sending d units of flow from s to t, each edge
has both an upper *and* a lower bound. I.e., you want to find a flow
such that edge e carries *at least* l_e flow and at most c_e flow. How
do you solve this problem?
Anyone? [Reduce to the previous problem.] Anyone?
Easy. Start off with b_s = -d, and b_t = d. Next, "send" the l_e flows
along the edge. I.e., if l_{uv} = 5, then set b_u = 5 and b_v -=
5. (You've sent the 5 units of flow from u to v, so u has a deficit of 5
and wants 5 extra units, whereas v has 5 extra units and needs to get
rid of it.) Do this for every edge. This gives you a final vector of b_v
values. Now do as above.
------------------------------------------------------------
PROBLEM 1(LAST TIME):
---------------------
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 find 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 watch a movie, and
t's might be different sites that can stream that 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 (LAST TIME):
----------------------
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 the pictures 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 smooth
boundaries, which means that most pairs of neighboring pixels should 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, so
I is a 0/1 matrix), 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.