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.