Homework #4 Solution

Sharing this PDF file in any way, e.g., via email, uploading to a web site (personal, public, commercial) is




unauthorized.




This file is copyrighted material. Copyright held by Professor Dimitris Achlioptas and UC Santa Cruz.







Each problem is worth 25 points. You should assume that you have access to an algorithm that finds the maximum flow in a graph. So, for each problem, it is enough to describe the instance of the flow problem that you need solved and prove that you can use the answer to the flow problem to always give the correct answer for the problem at hand.




Reminder: For each of the four problems you receive 6 of the 25 points if you write nothing about the problem. If you feel that you have a partial answer worth more than 6 points, e.g., you have an algorithm but can’t prove it correct, or your algorithm can be proven correct but is too slow, you can still write this information as long as you begin your answer by assessing your work. If we find your work as assessed, you will receive at least 6 points.




Achliopolis Vegan Hotdog Mogul



Your algorithm to achieve maximum wisdom was perfect. You achieved enough wisdom to realize that knowledge is a poor substitute for cold hard cash. You have decided to capitalize on your “Achliopolis vegan hot-dog eating champion” fame and open up a chain of vegan hot-dog restaurants all over Achliopolis. Luckily for you, “Ben’s Wing Shack”, an unpopular local chain, has recently gone under. As a result you have acquired n different restaurant locations and k supply warehouses. You now have to determine which warehouse will supply each restaurant.




If a restaurant r is more than m miles from warehouse w, then r can’t have w as its supplier; those vegan hot dogs will rot during transport! Additionally, each warehouse only stores enough vegan dogs at any given time to be the supplier of at most c restaurants.




Given the number and positions of restaurants and warehouses, m, and c, construct a polynomial time algorithm that determines whether there is an assignment of restaurants to warehouses such that no warehouse supplies more than c restaurants and no restaurant is supplied by a warehouse more than m miles away.




Training Day



You have established your vegan hot-dog chain, but now you need to get some vegan hot dog chefs in the kitchens.




You have n chefs to train, and each must take two classes: one on bun toasting and one on sauce squirting.




Kostas is the best bun-toaster in Achliopolis. He has agreed to teach your chefs how to toast buns. He has scheduled several different sessions which your chefs may attend, though the maximum attendance of each session may vary. Let B be the set of bun-toasting classes offered and let bk be the number of chefs that can attend the k-th class. Additionally, you have paid Kostas to train exactly n students, so the sum of bk over all of Kostas’ classes is exactly n.




Wei-Lin is the best sauce-squirter in Achliopolis. His deal with you is the same as Kostas’s. We will denote Wei-Lin’s classes as S and let sk represent the number of students that can attend his k-th class. Again, the sum of sk over all of Wei-Lin’s classes is exactly n.




Each student gives you two lists Bi B and Si S of which classes they are available to attend. Give a polynomial time algorithm that assigns each student to a bun-toasting and a sauce-squirting class for which they are available, or proves that no such assignment is possible.

The Mayor of Achliopolis



After conquering the business world with your vegan hot-dog chain, you decided to conquer the political world. First stop, Achliopolis. You easily won the election to become Mayor of Achliopolis, but you must do a good job if you want to keep climbing the ladder!




You have a collection of n different cronies working in City Hall. Each crony belongs to one of three political parties: the Left Wing, the Right Wing, and the Bird Wing. You have to form several different committees, each of which is vitally important to your success as Mayor. Each committee must be made up of at least k cronies in order to appear as if it is accomplishing something. Each crony is very busy and can sit on at most 3 committees. Depending on each crony’s skill set, you have limited the set of committees they are eligible to sit on. You also know that if any committee is comprised entirely of cronies from the same party, the people of Achliopolis will smell corruption and turn against you.




You are given a set of committees C, n cronies, and the minimum committee size k. Let Ci C denote the subset of committees that crony i is qualified to sit on. Give an algorithm that determines whether there is an assignment of cronies to committees for which they are qualified, so that every committee has k members, no crony is assigned to more than 3 committees, and no committee is made up of cronies from a single party.




Special edge



Let G be a directed graph with source vertex s and sink vertex t, and assume that all edge capacities are non-



negative integers. Let G0 be the network obtained by reducing the capacity of exactly one, arbitrary edge, say e , by x. Prove that:

maxflow(G0) maxflow(G) x :




Let G be a graph as above except that exactly one edge e has positive, non-integer capacity. Prove that exactly one of the following is always true:



Every minimum s t cut of G contains e .



There is a maximum flow in G where every edge in G has an integral flow value.




















































































2