Multicommodity flows in certain planar directed networks (Q753654)

For an undirected network with \(K=2\) commodities, the max-flow min-cut theorem holds and a polynomial time algorithm is known. \textit{H. Okamura} and \textit{P. D. Seymour} [J. Comb. Theory, Ser. B 31, 75-81 (1981; Zbl 0465.90029)] have shown that, if all sources and sinks are placed on the boundary of the outer face of a given planar undirected graph, the max- flow min-cut theorem holds for general k. Contrary to the result, for directed networks, the max-flow min-cut theorem does not hold even with \(K=2\). Not many tractable classes are known except a class of planar directed networks in which all sources are on the left side of the boundary while all sinks are on the right side, and furthermore the order of commodities of sources and the order of commodities of sinks appear in the same order. In this paper, class CB (capacity balanced) of directed networks is first introduced and a polynomial time graph theoretic algorithm is developed to compute a feasible flow. Its running time is O(K\(| V|)\) for a CB network with K commodities and \(| V|\) nodes. A network in CB satisfies the following conditions: (1) The graph is directed, planar and acyclic. (2) All nodes without entering arcs and all nodes without outgoing arcs are located on the boundary of the outer face of the graph. (3) Each commodity has exactly one source and one sink, where the sink is located on the boundary. (4) Each node is capacity balanced. It can also be shown that the integral flow property holds for CB, i.e., an integral feasible flow exists if the network is feasible and the arc capacities are all integers. Secondly, class CS (capacity semi-balanced), and extension of CB is considered, and CS is shown to be reducible to CB. This means that CS also has a polynomial time graph theoretic algorithm and the integral flow property. This class contains a certain multi-item multi-stage production scheduling problem as a special case, indicating its practical importance.