In a directed acyclic network G, certain arcs are colored blue, while others are colored red. Consider the problem of covering the blue arcs by directed paths, which can start and end at any node (these paths can contain arcs of any color). Show that the minimum number of directed paths needed to cover the blue arcs is equal to the maximum number of blue arcs that satisfy the property that no two of these arcs belong to the same path. Will this result be valid if G contains directed cycles? (Hint: Use the min-flow maxcut theorem stated in Exercise 6.18.)
Exercise 6.18
Minimum flow problem. The minimumjlow problem is a close relative of the maximum flow problem with nonnegative lower bounds on arc flows. In the minimum flow problem, we wish to send the minimum amount of flow from the source to the sink, while satisfying given lower and upper bounds on arc flows.
(a) Show how to solve the minimum flow problem by using two applications of any maximum flow algorithm that applies to problems with zero lower bounds on arc flows. (Hint: First construct a feasible flow and then convert it into a minimum flow.)
(b) Prove the following min-flow max-cut theorem. Let the floor (or lower bound on
