Previous Next 
Maxflow ReductionsIn this section, we consider a number of reductions to the maxflow problem in order to demonstrate that the maxflow algorithms of s 22.2 and 22.3 are important in a broad context. We can remove various restrictions on the network and solve other flow problems; we can solve other network and graphprocessing problems; and we can solve problems that are not network problems at all. This section is devoted to examples of such uses—to establish maxflow as a general problemsolving model. We also consider relationships between the maxflow problem and problems that are more difficult so as to set the context for considering those problems later on. In particular, we note that the maxflow problem is a special case of the mincostflow problem that is the subject of s 22.5 and 22.6, and we describe how to formulate maxflow problems as LP problems, which we will address in Part 8. Mincost flow and LP represent problemsolving models that are more general than the maxflow model. Although we normally can solve maxflow problems more easily with the specialized algorithms of s 22.2 and 22.3 than with algorithms that solve these more general problems, it is important to be cognizant of the relationships among problemsolving models as we progress to more powerful ones. We use the term standard maxflow problem to refer to the version of the problem that we have been considering (maxflow in edgecapacitated stnetworks). This usage is solely for easy reference in this section. Indeed, we begin by considering reductions that show the restrictions in the standard problem to be essentially immaterial, because several other flow problems reduce to or are equivalent to the standard problem. We could adopt any of the equivalent problems as the "standard" problem. A simple example of such a problem, already noted as a consequence of Property 22.1, is that of finding a circulation in a network that maximizes the flow in a specified edge. Next, we consider other ways to pose the problem, in each case noting its relationship to the standard problem. Maxflow in general networks Find the flow in a network that maximizes the total outflow from its sources (and therefore the total inflow to its sinks). By convention, define the flow to be zero if there are no sources or no sinks. Property 22.14 The maxflow problem for general networks is equivalent to the maxflow problem for stnetworks. Proof: A maxflow algorithm for general networks will clearly work for stnetworks, so we just need to establish that the general problem reduces to the stnetwork problem. To do so, first find the sources and sinks (using, for example, the method that we used to initialize the queue in Program 19.8), and return zero if there are none of either. Then, add a dummy source vertex s and edges from s to each source in the network (with each such edge's capacity set to that edge's destination vertex's outflow) and a dummy sink vertex t and edges from each sink in the network to t (with each such edge's capacity set to that edge's source vertex's inflow). Screenshot illustrates this reduction. Any maxflow in the stnetwork corresponds directly to a maxflow in the original network. Screenshot Reduction from multiple sources and sinksThe network at the top has three sources (0, 1, and 2) and two sinks (5 and 6). To find a flow that maximizes the total flow out of the sources and into the sinks, we find a maxflow in the stnetwork illustrated at the bottom. This network is a copy of the original network, with the addition of a new source 7 and a new sink 8. There is an edge from 7 to each originalnetwork source with capacity equal to the sum of the capacities of that source's outgoing edges, and an edge from each originalnetwork sink to 8 with capacity equal to the sum of the capacities of that sink's incoming edges. Vertexcapacity constraints Given a flow network, find a maxflow satisfying additional constraints specifying that the flow through each vertex must not exceed some fixed capacity. Property 22.15 The maxflow problem for flow networks with capacity constraints on vertices is equivalent to the standard maxflow problem. Proof: Again, we could use any algorithm that solves the capacityconstraint problem to solve a standard maxflow problem (by setting capacity constraints at each vertex to be larger than its inflow or outflow), so we need only to show a reduction to the standard maxflow problem. Given a flow network with capacity constraints, construct a standard flow network with two vertices u and u* corresponding to each original vertex u, with all incoming edges to the original vertex going to u, all outgoing edges coming from u*, and an edge uu* of capacity equal to the vertex capacity. This construction is illustrated in Screenshot. The flows in the edges of the form u*v in any maxflow for the transformed network give a maxflow for the original network that must satisfy the vertexcapacity constraints because of the edges of the form uu*. Screenshot Removing vertex capacitiesTo solve the problem of finding a maxflow in the network at the top such that flow through each vertex does not exceed the capacity bound given in the vertexindexed array capV, we build the standard network at the bottom: Associate a new vertex u* (where u* denotes u+V) with each vertex u, add an edge uu* whose capacity is the capacity of u, and include an edge u*v for each edge uv. Each uu* pair is encircled in the diagram. Any flow in the bottom network corresponds directly to a flow in the top network that satisfies the vertexcapacity constraints. Allowing multiple sinks and sources or adding capacity constraints seem to generalize the maxflow problem; the interest of Properties 22.14 and 22.15 is that these problems are actually no more difficult than the standard problem. Next, we consider a version of the problem that might seem to be easier to solve. Acyclic networks Find a maxflow in an acyclic network. Does the presence of cycles in a flow network make more difficult the task of computing a maxflow? We have seen many examples of digraphprocessing problems that are much more difficult to solve in the presence of cycles. Perhaps the most prominent example is the shortestpaths problem in weighted digraphs with edge weights that could be negative (see ), which is simple to solve in linear time if there are no cycles but NPcomplete if cycles are allowed. But the maxflow problem, remarkably, is no easier for acyclic networks. Property 22.16 The maxflow problem for acyclic networks is equivalent to the standard maxflow problem. Proof: Again, we need only to show that the standard problem reduces to the acyclic problem. Given any network with V vertices and E edges, we construct a network with 2V + 2 vertices and E + 3V edges that is not just acyclic but has a simple structure. Let u* denote u+V, and build a bipartite digraph consisting of two vertices u and u* corresponding to each vertex u in the original network and one edge uv* corresponding to each edge uv in the original network with the same capacity. Now, add to the bipartite digraph a source s and a sink t and, for each vertex u in the original graph, an edge su and an edge u*t, both of capacity equal to the sum of the capacities of u's outgoing edges in the original network. Also, let X be the sum of the capacities of the edges in the original network, and add edges from u to u*, with capacity X + 1. This construction is illustrated in Screenshot. Screenshot Reduction to acyclic networkEach vertex u in the top network corresponds to two vertices u and u* (where u* denotes u+V) in the bottom network, and each edge uv in the top network corresponds to an edge uv* in the bottom network. Additionally, the bottom network has uncapacitated edges uu*, a source s with an edge to each unstarred vertex, and a sink t with an edge from each starred vertex. The shaded and unshaded vertices (and edges which connect shaded to unshaded) illustrate the direct relationship among cuts in the two networks (see text). To show that any maxflow in the original network corresponds to a maxflow in the transformed network, we consider cuts rather than flows. Given any stcut of size c in the original network, we show how to construct an stcut of size c + X in the transformed network; and, given any minimal stcut of size c + X in the transformed network, we show how to construct an stcut of size c in the original network. Thus, given a minimal cut in the transformed network, the corresponding cut in the original network is minimal. Moreover, our construction gives a flow whose value is equal to the minimalcut capacity, so it is a maxflow. Given any cut of the original network that separates the source from the sink, let S be the source's vertex set and T the sink's vertex set. Construct a cut of the transformed network by putting vertices in S in a set with s and vertices in T in a set with t and putting u and u* on the same side of the cut for all u, as illustrated in Screenshot. For every u, either su or u*t is in the cut set, and uv* is in the cut set if and only if uv is in the cut set of the original network; so the total capacity of the cut is equal to the capacity of the cut in the original network plus X. Given any minimal stcut of the transformed network, let S^{*} be s's vertex set and T^{*} t's vertex set. Our goal is to construct a cut of the same capacity with u and u* both in the same cut vertex set for all u so that the correspondence of the previous paragraph gives a cut in the original network, completing the proof. First, if u is in S^{*} and u* in T^{*}, then uu* must be a crossing edge, which is a contradiction: uu* cannot be in any minimal cut, because a cut consisting of all the edges corresponding to the edges in the original graph is of lower cost. Second, if u is in T^{*} and u* is in S^{*}, then su must be in the cut, because that is the only edge connecting s to u. But we can create a cut of equal cost by substituting all the edges directed out of u for su, moving u to S^{*}. Given any flow in the transformed network of value c + X, we simply assign the same flow value to each corresponding edge in the original network to get a flow with value c. The cut transformation at the end of the previous paragraph does not affect this assignment, because it manipulates edges with flow value zero. The result of the reduction not only is an acyclic network, but also has a simple bipartite structure. The reduction says that we could, if we wished, adopt these simpler networks, rather than general networks, as our standard. It would seem that perhaps this special structure would lead to faster maxflow algorithms. But the reduction shows that we could use any algorithm that we found for these special acyclic networks to solve maxflow problems in general networks, at only modest extra cost. Indeed, the classical maxflow algorithms exploit the flexibility of the general network model: Both the augmentingpath and preflowpush approaches that we have considered use the concept of a residual network, which involves introducing cycles into the network. When we have a maxflow problem for an acyclic network, we typically use the standard algorithm for general networks to solve it. The construction of Property 22.16 is elaborate, and it illustrates that reduction proofs can require care, if not ingenuity. Such proofs are important because not all versions of the maxflow problem are equivalent to the standard problem, and we need to know the extent of the applicability of our algorithms. Researchers continue to explore this topic because reductions relating various natural problems have not yet been established, as illustrated by the following example: Maxflow in undirected networks An undirected flow network is a weighted graph with integer edge weights that we interpret to be capacities. A circulation in such a network is an assignment of weights and directions to the edges satisfying the conditions that the flow on each edge is no greater than that edge's capacity and that the total flow into each vertex is equal to the total flow out of that vertex. The undirected maxflow problem is to find a circulation that maximizes the flow in specified direction in a specified edge (that is, from some vertex s to some other vertex t). This problem perhaps corresponds more naturally than the standard problem to our liquidflowingthroughpipes model: It corresponds to allowing liquid to flow through a pipe in either direction. Property 22.17 The maxflow problem for undirected stnetworks reduces to the maxflow problem for stnetworks. Proof: Given an undirected network, construct a directed network with the same vertices and two directed edges corresponding to each edge, one in each direction, both with the capacity of the undirected edge. Any flow in the original network certainly corresponds to a flow with the same value in the transformed network. The converse is also true: If uv has flow f and vu flow g in the undirected network, then we can put the flow f – g in uv in the directed network if f g; g – f in vu otherwise. Thus, any maxflow in the directed network is a maxflow in the undirected network: The construction gives a flow, and any flow with a higher value in the directed network would correspond to some flow with a higher value in the undirected network; but no such flow exists. Screenshot Reduction from undirected networksTo solve a maxflow problem in an undirected network, we can consider it to be a directed network with edges in each direction. Note that the residual network for such a network has four edges corresponding to each edge in the undirected network. This proof does not establish that the problem for undirected networks is equivalent to the standard problem. That is, it leaves open the possibility that finding maxflows in undirected networks is easier than finding maxflows in standard networks (see Exercise 22.81). In summary, we can handle networks with multiple sinks and sources, undirected networks, networks with capacity constraints on vertices, and many other types of networks (see, for example, Exercise 22.79) with the maxflow algorithms for stnetworks in the previous two sections. In fact, Property 22.16 says that we could solve all these problems with even an algorithm that works for only acyclic networks. Next, we consider a problem that is not an explicit maxflow problem but that we can reduce to the maxflow problem and therefore solve with maxflow algorithms. It is one way to formalize a basic version of the merchandisedistribution problem described at the beginning of this chapter. Feasible flow Suppose that a weight is assigned to each vertex in a flow network and is to be interpreted as supply (if positive) or demand (if negative), with the sum of the vertex weights equal to zero. Define a flow to be feasible if the difference between each vertex's outflow and inflow is equal to that vertex's weight (supply if positive and demand if negative). Given such a network, determine whether or not a feasible flow exists. Screenshot illustrates a feasibleflow problem. Screenshot Feasible flowIn a feasibleflow problem, we specify supply and demand constraints at the vertices in addition to the capacity constraints on the edges. We seek any flow for which outflow equals supply plus inflow at supply vertices and inflow equals outflow plus demand at demand vertices. Three solutions to the feasibleflow problem at left are shown on the right. Supply vertices correspond to warehouses in the merchandisedistribution problem, demand vertices correspond to retail outlets, and edges correspond to roads on the trucking routes. The feasibleflow problem answers the basic question of whether it is possible to find a way to ship the goods such that supply meets demand everywhere.
Property 22.18 The feasibleflow problem reduces to the maxflow problem. Proof: Given a feasibleflow problem, construct a network with the same vertices and edges but with no weights on the vertices. Instead, add a source vertex s that has an edge to each supply vertex with weight equal to that vertex's supply and a sink vertex t that has an edge from each demand vertex with weight equal to the negation of that vertex's demand (so that the edge weight is positive). Solve the maxflow problem on this network. The original network has a feasible flow if and only if all the edges out of the source and all the edges into the sink are filled to capacity in this flow. Screenshot illustrates an example of this reduction. Developing classes that implement reductions of the type that we have been considering can be a challenging softwareengineering task, primarily because the objects that we are manipulating are represented with complicated data structures. To reduce another problem to a standard maxflow problem, should we create a new network? Some of the problems require extra data, such as vertex capacities or supply and demand, so creating a standard network without these data might be justified. Our use of edge references plays a critical role here: If we copy a network's edges and then compute a maxflow, what are we to do with the result? Transferring the computed flow (a weight on each edge) from one network to another when both are represented with adjacency lists is not a trivial computation. With edge references, the new network has copies of references, not edges, so we can transfer flow assignments right through to the client's network. Program 22.6 is an implementation that illustrates some of these considerations in a class for solving feasibleflow problems using the reduction of Property 22.16. A canonical example of a flow problem that we cannot handle with the maxflow model, and that is the subject of s 22.5 and 22.6, is an extension of the feasibleflow problem. We add a second set of edge weights that we interpret as costs, define flow costs in terms of these weights, and ask for a feasible flow of minimal cost. This model formalizes the general merchandisedistribution problem. We are interested not just in whether it is possible to move the goods but also in what is the lowestcost way to move them. All the problems that we have considered so far in this section have the same basic goal (computing a flow in a flow network), so it is perhaps not surprising that we can handle them with a flownetwork problemsolving model. As we saw with the maxflow–mincut theorem, we can use maxflow algorithms to solve graphprocessing problems that seem to have little to do with flows. We now turn to examples of this kind. Maximumcardinality bipartite matching Given a bipartite graph, find a set of edges of maximum cardinality such that each vertex is connected to at most one other vertex. For brevity, we refer to this problem simply as the bipartitematching problem except in contexts where we need to distinguish it from similar problems. It formalizes the jobplacement problem discussed at the beginning of this chapter. Vertices correspond to individuals and employers; edges correspond to a "mutual interest in the job" relation. A solution to the bipartitematching problem maximizes total employment. Screenshot illustrates the bipartite graph that models the example problem in Screenshot. Screenshot Bipartite matchingThis instance of the bipartitematching problem formalizes the jobplacement example depicted in Screenshot. Finding the best way to match the students to the jobs in that example is equivalent to finding the maximum number of vertexdisjoint edges in this bipartite graph. It is an instructive exercise to think about finding a direct solution to the bipartitematching problem, without using the graph model. For example, the problem amounts to the following combinatorial puzzle: "Find the largest subset of a set of pairs of integers (drawn from disjoint sets) with the property that no two pairs have the same integer." The example depicted in Screenshot corresponds to solving this puzzle on the pairs 06, 07, 08, 16, and so forth. The problem seems straightforward at first, but, as was true of the Hamiltonpath problem that we considered in (and many other problems), a naive approach that chooses pairs in some systematic way until finding a contradiction might require exponential time. That is, there are far too many subsets of the pairs for us to try all possibilities; a solution to the problem must be clever enough to examine only a few of them. Solving specific matching puzzles like the one just given or developing algorithms that can solve efficiently any such puzzle are nontrivial tasks that help to demonstrate the power and utility of the networkflow model, which provides a reasonable way to do bipartite matching. Property 22.19 The bipartitematching problem reduces to the maxflow problem. Proof: Given a bipartitematching problem, construct an instance of the maxflow problem by directing all edges from one set to the other, adding a source vertex with edges directed to all the members of one set in the bipartite graph, and adding a sink vertex with edge directed from all the members of the other set. To make the resulting digraph a network, assign each edge capacity 1. Screenshot illustrates this construction. Screenshot Reduction from bipartite matchingTo find a maximum matching in a bipartite graph (top), we construct an stnetwork (bottom) by directing all the edges from the top row to the bottom row, adding a new source with edges to each vertex on the top row, adding a new sink with edges to each vertex on the bottom row, and assigning capacity 1 to all edges. In any flow, at most one outgoing edge from each vertex on the top row can be filled and at most one incoming edge to each vertex on the bottom row can be filled, so a solution to the maxflow problem on this network gives a maximum matching for the bipartite graph. Now, any solution to the maxflow problem for this network provides a solution to the corresponding bipartitematching problem. The matching corresponds exactly to those edges between vertices in the two sets that are filled to capacity by the maxflow algorithm. First, the network flow always gives a legal matching: Since each vertex has an edge of capacity one either coming in (from the sink) or going out (to the source), at most one unit of flow can go through each vertex, implying in turn that each vertex will be included at most once in the matching. Second, no matching can have more edges, since any such matching would lead directly to a better flow than that produced by the maxflow algorithm. For example, in Screenshot, an augmentingpath maxflow algorithm might use the paths s06t, s17t, s28t, s49t, s510t, and s3607111t to compute the matching 07, 111, 28, 36, 49, and 510. Thus, there is a way to match all the students to jobs in Screenshot. Program 22.7 is a client program that reads a bipartitematching problem from standard input and uses the reduction described in this proof to solve it. What is the running time of this program for huge networks? Certainly, the running time depends on the maxflow algorithm and implementation that we use. Also, we need to take into account that the networks that we build have a special structure (unitcapacity bipartite flow networks)—not only do the running times of the various maxflow algorithms that we have considered not necessarily approach their worstcase bounds, but also we can substantially reduce the bounds. For example, the first bound that we considered, for the generic augmentingpath algorithm, provides a quick answer. Corollary The time required to find a maximumcardinality matching in a bipartite graph is O(VE). Proof: Immediate from Property 22.6. The operation of augmentingpath algorithms on unitcapacity bipartite networks is simple to describe. Each augmenting path fills one edge from the source and one edge into the sink. These edges are never used as back edges, so there are at most V augmenting paths. The VE upper bound holds for any algorithm that finds augmenting paths in time proportional to E.
Table 22.3 shows performance results for solving random bipartitematching problems using various augmentingpath algorithms. It is clear from this table that actual running times for this problem are closer to the VE worst case than to the optimal (linear) time. It is possible, with judicious choice and tuning of the maxflow implementation, to speed up this method by a factor of (see Exercises 22.91 and 22.92). This problem is representative of a situation that we face more frequently as we examine new problems and more general problemsolving models, demonstrating the effectiveness of reduction as a practical problemsolving tool. If we can find a reduction from a given problem to a known general model such as the maxflow problem, we generally view that as a major step toward developing a practical solution, because it at least indicates not only that the problem is tractable, but also that we have numerous efficient algorithms for solving the problem. In many situations, it is reasonable to use an existing maxflow class to solve the problem and move on to the next problem. Table 22.3. Empirical study for bipartite matching
The corresponding results for undirected graphs, and for vertex connectivity for digraphs and for undirected graphs, involve reductions similar to those considered here and are left for exercises (see Exercises 22.94 through 22.96). Now we turn to algorithmic implications of the direct connection between flows and connectivity that is established by the maxflow–mincut theorem. Property 22.5 is perhaps the most important algorithmic implication (the mincut problem reduces to the maxflow problem), but the converse is not known to be true (see Exercise 22.47). Intuitively, it seems as though knowing a mincut should make easier the task of finding a maxflow, but no one has been able to demonstrate how. This basic example highlights the need to proceed with care when working with reductions among problems. Still, we can also use maxflow algorithms to handle numerous connectivity problems. For example, they help solve the first nontrivial graphprocessing problems that we encountered, in . Edge connectivity What is the minimum number of edges that need to be removed to separate a given graph into two pieces? Find a set of edges of minimal cardinality that does this separation. Vertex connectivity What is the minimum number of vertices that need to be removed to separate a given graph into two pieces? Find a set of vertices of minimal cardinality that does this separation. These problems also are relevant for digraphs, so there are a total of four problems to consider. As with Menger's theorem, we consider one of them in detail (edge connectivity in undirected graphs) and leave the others for exercises. Property 22.21 The time required to determine the edge connectivity of an undirected graph is O(E^{2}). Proof: We can compute the minimum size of any cut that separates two given vertices by computing the maxflow in the stnetwork formed from the graph by assigning unit capacity to each edge. The edge connectivity is equal to the minimum of these values over all pairs of vertices. We do not need to do the computation for all pairs of vertices, however. Let s* be a vertex of minimal degree in the graph. Note that the degree of s* can be no greater than 2E/V. Consider any minimum cut of the graph. By definition, the number of edges in the cut set is equal to the graph's edge connectivity. The vertex s* appears in one of the cut's vertex sets, and the other set must have some vertex t, so the size of any minimal cut separating s* and t must be equal to the graph's edge connectivity. Therefore, if we solve V1 maxflow problems (using s* as the source and each other vertex as the sink), the minimum flow value found is the edge connectivity of the network. Now, any augmentingpath maxflow algorithm with s* as the source uses at most 2E/V paths; so, if we use any method that takes at most E steps to find an augmenting path, we have a total of at most (V – 1)(2 E/V)E steps to find the edge connectivity and that implies the stated result. This method, unlike all the other examples of this section, is not a direct reduction of one problem to another, but it does give a practical algorithm for computing edge connectivity. Again, with a careful maxflow implementation tuned to this specific problem, we can improve performance—it is possible to solve the problem in time proportional to VE (see reference section). The proof of Property 22.21 is an example of the more general concept of efficient (polynomialtime) reductions that we first encountered in and that plays an essential role in the theory of algorithms discussed in Part 8. Such a reduction both proves the problem to be tractable and provides an algorithm for solving it—significant first steps in coping with a new combinatorial problem. We conclude this section by considering a strictly mathematical formulation of the maxflow problem, using linear coding (LP) (see ). This exercise is useful because it helps us to see relationships to other problems that can be so formulated. The formulation is straightforward: We consider a system of inequalities that involve one variable corresponding to each edge, two inequalities corresponding to each edge, and one equation corresponding to each vertex. The value of the variable is the edge flow, the inequalities specify that the edge flow must be between 0 and the edge's capacity, and the equations specify that the total flow on the edges that go into each vertex must be equal to the total flow on the edges that go out of that vertex. Screenshot illustrates an example of this construction. Any maxflow problem can be cast as a LP problem in this way. LP is a versatile approach to solving combinatorial problems, and a great number of the problems that we study can be formulated as linear programs. The fact that maxflow problems are easier to solve than LP problems may be explained by the fact that the constraints in the LP formulation of maxflow problems have a specific structure not necessarily found in all LP problems. Screenshot LP formulation of a maxflow problemThis linear program is equivalent to the maxflow problem for the sample network of Screenshot. There is one inequality for each edge (which specifies that flow cannot exceed capacity) and one equality for each vertex (which specifies that flow in must equal flow out). We use a dummy edge from sink to source to capture the flow in the network, as described in the discussion following Property 22.2. Even though the LP problem is much more difficult in general than are specific problems such as the maxflow problem, there are powerful algorithms that can solve LP problems efficiently. The worstcase running time of these algorithms certainly exceeds the worstcase running of the specific algorithms that we have been considering, but an immense amount of practical experience over the past several decades has shown them to be effective for solving problems of the type that arise in practice. The construction illustrated in Screenshot indicates a proof that the maxflow problem reduces to the LP problem, unless we insist that flow values be integers. When we examine LP in detail in Part 8, we describe a way to overcome the difficulty that the LP formulation does not carry the constraint that the results have integer values. This context gives us a precise mathematical framework that we can use to address ever more general problems and to create ever more powerful algorithms to solve those problems. The maxflow problem is easy to solve and also is versatile in its own right, as indicated by the examples in this section. Next, we examine a harder problem (still easier than LP) that encompasses a stillwider class of practical problems. We discuss ramifications of building solutions to these increasingly general problemsolving models at the end of this chapter, setting the stage for a full treatment in Part 8. Exercises

Previous Next 