On Integer Multiflow Maximization.
Generalizing the two-commodity flow theorem of Rothschild and Whinston [Oper. Res., 14 (1966), pp. 377--387] and the multiflow theorem of Lovsz [Acta Mat. Akad. Sci. Hungaricae, 28 (1976), pp. 129--138] and Cherkasky [Ekonom.-Mat. Metody, 13 (1977), pp. 143--151], Karzanov and Lomonosov [Mathematical Programming,  O. I. Larichev, ed., Institute for System Studies, 1978, pp. 59--66] in 1978 proved a min-max theorem on maximum multiflows.  Their original proof is quite long and technical and relies on earlier investigations into  metrics.  The main purpose of the present paper is to provide a relatively simple proof of this theorem.  Our proof relies on the locking theorem, which is another result of Karzanov and Lomonosov, and the polymatroid intersection theorem of Edmonds [Combinatorial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, and J. Schnheim, eds., Gordon and Breach, 1970, pp. 69--87]. For completeness, we also provide a simplified proof of the locking theorem.  Finally, we introduce the notion of a node demand problem and, as another application of the locking theorem, we derive a feasibility theorem concerning it.The presented approach gives rise to (combinatorial) polynomial-time algorithms.
INTRODUCTION
E) and be two undirected graphs so that T ' V . We call a path of G H-
admissible if it connects two nodes x; y of T so that xy 2 F . G will be called a supply graph, H a
demand graph and the elements of T terminals while the other elements of V are called inner nodes.
The maximization problem consists of finding a maximum number of edge-disjoint H-admissible paths.
If H consists of one edge, then Menger's theorem gives an answer.
In general, the problem is NP-complete even in the special case when G is Eulerian. graph is called
Eulerian if the degree of every node is even.) There are, however, important special cases when the problem
is tractable. Rothschild and Whinston [1966] proved a max-flow min-cut type theorem when (G; T ) is inner
Eulerian and H consists of two edges. (We say that the pair (G; T ) is inner Eulerian if the degree d(v) is
even for every inner node v). Another result is due, independently, to L. Lov'asz [1976] and B.V. Cherkasskij
[1977]. They solve the maximization problem when H is a complete graph and G is inner Eulerian. In [1978]
A.V. Karzanov and M.V. Lomonosov found a common generalization of these two theorems. Their original
proof is rather lengthy and technical and it is certainly much more difficult than those of the two special cases
mentioned above. Details of these proofs were described in [Karzanov, 1979] and [Lomonosov, 1985]. Later
Karzanov ([1985] and [1987]) exhibited another proof which was based on the splitting-off technique and gave
rise to a strongly polynomial solution algorithm. However, this latter proof was also rather complicated.
The main contribution of this paper is a relatively simple proof of the theorem of Karzanov and Lomonosov.
The proof relies on two ingredients; the so-called locking theorem, another result of Karzanov and Lomonosov
* Department of Operations Research, E-otv-os University, M'uzeum krt. 6-8, Budapest, Hungary, H-1088.
Research of this author was partially supported by the Hungarian National Foundation for Scientific Research
Grants OTKA T17580 and was partially carried out while the author visited IMAG of Universit'e de Grenoble,
BP 53, 38041 Grenoble, Cedex, France.
# Institute for System Analysis, Prospect
IMAG, Universit'e J. Fourier, BP 53, 38041 Grenoble, Cedex, France. Research of this and the first author
was partially supported by the European project DONET.
[1978], and the polymatroid intersection theorem of J. Edmonds [1970]. For completeness, we will also provide
a simplified proof of the locking theorem. Since both of these ingredients can be solved by a (combinatorial)
polynomial-time algorithm, the approach gives rise to an alternative strongly polynomial-time algorithm for
the (capacitated) maximization problem in question which is faster than that in [Karzanov, 1985].
In what follows we do not distinguish between a one-element set fxg and its only element x. For a set
X and an element t let denote the union of X and t. For a vector m we use the notation
family of pairwise disjoint non-empty subsets of a set S is called a sub-partition
of S. For two elements s; t a set X is called a t-s-set if t 2 X; s 62 X: An integer-valued vector
or function is called even if each of its values is an even integer. For a polyhedron P we use the notation
For a graph E) the cut [X; denotes the set of edges with precisely one end-node in X. Its
cardinality is denoted by d(X)(= is called the degree function of G. Let d(X; Y ) denote
the number of edges with one and in X \Gamma Y and the other in Y \Gamma X. Let -
It is easy to prove that d satisfies the following identities for every pair X;Y of subsets of V .
Let A and B be two disjoint subsets of V . A path connecting an element of A and an element of B
is called an (A; B)-path. A path connecting two distinct elements of A is called an A-path. -(A; B; G)
or simply -(A; B) stands for the maximum number of edge-disjoint (A; B)-paths. By Menger's theorem
One may consider a fractional version of the edge-disjoint paths problem. Let G and H be as before.
By an H-multiflow or briefly multiflow x we mean a family fP of paths of G along with
non-negative coefficients ff so that each P i connects the end-nodes of a demand edge. x is called
integer-valued if each ff i is an integer.
If each P i connects an element of A and an element of B (that is, when H is a complete bipartite graph with
bipartition (A; B), we speak of an (A; B)-flow. For an H-multiflow x let x(e) :=
E)
and x(t) :=
ends at called c-admissible
if x(e) - c(e) for every e 2 E.
2. THE LOCKING PROBLEM
E) be a graph and T ' V a subset of terminal nodes. For a subset A ' T the notation
will be abbreviated by -(A; G) or by -(A) when no confusion can arise. Throughout the
paper we assume that the current (G; T ) is inner Eulerian.
Lov'asz [1976] and Cherkassky [1977] proved the following theorem.
THEOREM 2.1 For an inner Eulerian pair (G; T ) the maximum number of edge-disjoint T -paths is equal
to (
An equivalent formulation is as follows.
THEOREM 2.1' Given an inner Eulerian pair (G; T ), there is a family F of edge-disjoint T -paths in G so
that F contains -(t) paths ending at t for each t 2 T .
In other words there is a single family of edge-disjoint T -paths that includes maximum families of edge-disjoint
simultaneously for all t 2 T .
Karzanov and Lomonosov [1978] extended this theorem. To formulate their result let us say that a family
F of edge-disjoint T -paths locks a subset A ' T if F contains -(A) A)-paths. Furthermore, we
say that F locks a family L of subsets of T if F locks all members of L.
Theorem 2.1' asserts that there is a family F of paths that locks all singletons of T . Is it always possible
to find a family of edge-disjoint T -paths that locks a specified family L? The answer, in general, is no, as
is shown by the following example. Here L consists of three pairwise crossing sets. (Two subsets X;Y of T
are called crossing if none of
Fig. 1
This example indicates why it is natural to require L to be 3-cross-free. A family L of subsets of T is
called has no three pairwise crossing members.
LOCKING THEOREM 2.2 [Karzanov and Lomonosov, 1978], [Karzanov 1984], [Lomonosov, 1985] Let
(G; T ) be inner Eulerian and L a 3-cross free family of subsets of T . Then there is a family of edge-disjoint
T -paths that locks L.
A proof of a slightly weaker version was sketched in [Karzanov and Lomonosov, 1978]. The present proof
relies on an idea of splitting used already in [Karzanov, 1984] but is technically simpler. Splitting off a
pair of adjacent edges of a graph G means an operation that replaces e and f by a new
edge connecting x and t (this way we may introduce parallel edges between x and t.) The resulting graph is
denoted by G ef .
Proof. We may assume that T \Gamma A 2 L for each A 2 L because for A 2 L adding T \Gamma A to L affects neither
3-cross-freeness nor lockability. Also assume that G is connected.
We proceed by induction on the number of edges incident to the elements of . If this number is
zero, then the statement is trivial. Therefore there is an edge st with . We are going to
show that there is an edge
From this the theorem follows since, by induction, there is a family F of T -paths of G ef locking L. If a
path uses the new edge h of G ef having arisen from the splitting of e; f , then revise F by replacing
in P by e and f . By (2.1) the revised F locks L in G.
Proof. Since Analogously,
Therefore, by (1.1),
from which the claim follows. ffl
Call a set X ' V tight if is closed under complementation,
tight. Because (G; T ) is inner Eulerian, a pair of edges
precisely if
there is no tight set X with t; x 2 s: (2:2)
There are no three maximal tight t-s-sets.
Proof. Let X;Y; Z be maximal tight t-s-sets. Since L is 3-cross-free, two of the three sets X "T; Y "T; Z "T ,
say are non-crossing.
Then either . In the first two cases
that X [ Y is tight contradicting the maximality of X and Y . In the last case, by applying Claim 1 to
contradicting the existence of edge st. ffl
Let S denote the set of neighbours of s.
CLAIM 3 It is not possible to cover S by two tight t-s-sets.
Proof. Suppose that S ' X[Y where X and Y are tight t-s-sets. Let ff := d(s;
By symmetry we may assume that ff - fi. implies that d(X+s) -(X "T ).
On the other hand, since fl is positive, we have
By Claims 2 and 3 there is an edge satisfying (2.2) and then (2.1) holds; the proof of the Locking
Theorem is complete. ffl ffl
One may be interested in other possible locking theorems when, rather than 3-cross-freeness,
some other property is assumed for the family L ' 2 T to be locked. On the negative side, Karzanov and
Pevzner [1979] showed that for every L including three pairwise crossing sets there is a graph G and a
subset T of its nodes so that (G; T ) is inner Eulerian and there is no family of T -paths locking all members
of L. On the other hand, there are other locking theorems when some restrictions are imposed on the
relationship of G and the family L. For example, let G be a planar Eulerian graph and let T :=
denote the nodes of its outer face in the cyclic order. If we define L to consist of all subsets of T of form
though L is not 3-cross free when k - 4, the locking theorem holds. (This
is a theorem equivalent, by planar dualization, to a result of Hurkens, Schrijver and Tardos [1988/89].
We will need a slight extension of Theorem 2.2. Let Z be a non-negative integer-valued function
on T . A family F of edge-disjoint T -paths is called m-independent if every terminal t 2 T is the end
of at most m(t) members of F . Let -m (A) denote the maximum number of edge-disjoint m-independent
A)-paths. We say that a family F of edge-disjoint T -paths m-locks a subset A ' T if F is m-
independent and contains -m (A) A)-paths. Furthermore, we say that F m-locks a family L of
subsets of T if F m-locks all members of L.
The following theorem is a straightforward consequence of Theorem 2.2 and will be used in the proof of
Theorem 4.3.
THEOREM 2.3 Let G be inner-Eulerian and L a 3-cross free family of subsets of T . Let Z+ be a
vector so that m(t) + d(t) is even for t 2 T . Then there is a family F of edge-disjoint T -paths that m-locks
L.
Proof. Let G 0 be a graph arising from G by splitting every node t 2 T in the following sense: add a new
node t 0 along with m(t) parallel edges between t and t 0 , and replace each edge xt of G by xt 0 . The result
immediately follows when Theorem 2.2 is applied to (G
3. FLOWS AND POLYMATROIDS
A non-negative set-function called a polymatroid function if
1.
2. b is monotone increasing, i. e.
3. b is submodular, i.e.
The degree-function d of a graph G satisfies properties 1 and 3 but typically not 2.
A polyhedron P (b) := fx is called a polymatroid. It is
called integral if every vertex of P is integer-valued.
The concept of a polymatroid was introduced by J. Edmonds [1970]. He proved that a polymatroid
uniquely determines its defining polymatroid function. Furthermore, a polymatroid is integral if and only if
b is integer-valued.
For a polymatroid P (b) the face B(b) of P (b) is called the basis polyhedron
and its elements are the bases. Edmonds also proved the following result.
THEOREM 3.1 [Edmonds, 1970] For an (integral) polymatroid P (b) and an (integer-valued) vector x 2
P (b) there is an (integer-valued) basis y with y - x.
The polymatroid intersection theorem of Edmonds states that the linear system of two polymatroids is
totally dual integral (TDI). Here we need only the following consequence.
THEOREM 3.2 [Edmonds, 1970] For two polymatroid functions a and b defined on the power set of T
Furthermore, if a and b are integer-valued, the maximum is attained by an integer vector.
It follows that there is a vector x in P (a) " P (b) and a bipartition fA; Bg of T so that
if a and b are integral-valued, then so is x.
E) be a graph endowed with a capacity function c be a subset of nodes and
there is a c-admissible (A; B)-flow x for which
for every v 2 Ag:
For
f A is submodular and monotone increasing. By a multiterminal version of the Max-flow Min-cut
theorem a vector m 2 R A
belongs to PA if and only if m(X) - f A (X): Therefore PA is a polymatroid.
Furthermore, if c and m are integer-valued, then there is a c-admissible integer-valued (A; B)-flow x for
which
E) be an Eulerian graph and T a subset of nodes. Define c by
be a partition of T and - i := -(T denote the direct sum of polymatroids
LEMMA 3.3 Let q be an integer basis of P . Then there is a family F of edge-disjoint T -paths connecting
distinct members of T so that each t 2 T is the end-point of exactly q(t) paths of F .
Proof. For each T i 2 T let X i be a minimal subset of V for which
claim that these sets are disjoint. If, indirectly,
contradicting the
minimality of X i .
We claim that there is a family F 0 of edge-disjoint paths in G connecting distinct X i 's and not using
edges induced by any X i so that F 0 contains - ending in X i for each i (1 - i - k). Indeed,
apply Theorem 2.1' to the pair (G where the graph G 0 arises from G by contracting each X i into a node
denoted by t i and T 0 := g.
Since q is a basis of P , for each T i there is a family F 0
i of q(T i
connecting T i and so that each t 2 T i is the end-node of q(t) members of F 0
i . For each member of
erase the edges outside X i and denote by F i the family of the resulting paths. By glueing together the
paths in F 0 and the paths in F i we obtain a family F of paths satisfying the requirements. ffl
LEMMA 3.4 Let q be an integer basis of P and m an integer vector for which m - q. Then an m-
independent family F of T -paths that m-locks T contains at least q(T )=2 paths connecting distinct members
of
Proof. By Lemma 3.3, - q (T i implies that -m - q : Since F m-locks T ,
there are -m (T i connecting T i and k from which the
lemma follows. ffl
REMARK Since q is a basis, F contains at most q(T i F contains at most
q(T )=2 paths connecting distinct members of T . That is, the number of such paths in F is precisely q(T )=2
but we will not need this fact.
Let A and B be two partitions of T and let L := A[B. Let H be a demand graph on T so that uv is an
edge of H if and only if no X 2 L includes both u and v.
For set-function defined by a We have seen above
that a i is a polymatroid function. Define b j analogously for B. For
a
Then a and b are polymatroid functions. Let P (a) and P (b) be the polymatroids defined by a and b,
respectively.
be an arbitrary even vector in P (a) " P (b) and h := m 0 (T )=2. Then there are h
edge-disjoint H-admissible paths.
Proof. Since G is Eulerian, P (a=2)(= P (a)=2) is an integral polymatroid. By applying Theorem 3.1 to
P (a=2) and to x := m 0 =2 we obtain that there is an even bases m a of P (a) so that m a - m 0 . Analogously,
there is an even bases m b of P (b) so that m b - m 0 . Define a vector m by m(t) := max(m a (t); m b (t)) for
is even and m a Hence
Since L is 3-cross free, we can apply Theorem 2.3. Let F denote the family of m-independent T -paths
provided by the theorem. Then jF
We are going to prove that the number h 0 of H-admissible paths in F is at least h. (Note that a path is
not H-admissible precisely if it connects two nodes belonging to the same member of L.)
By applying Lemma 3.4 with the choice T := A; P := P (a); q := m a , we obtain that there are at most
\Gammam a (T )=2 paths in F having both end-nodes in the same member of A. Analogously, there are at most
having both end-nodes in the same member of B:
Hence
(Note that an element t 2 T need not be the end-node of exactly m 0 (t) members of the family assured by
Lemma 3.5. For further comments, see the beginning of Section 6.)
4. MAXIMIZATION
E) be a supply graph and
Throughout this section we assume that the pair (G; T ) is inner Eulerian, that is, d(v) is even for every
stands for the degree function of G.
The maximization form of the edge-disjoint paths problem consists of finding a maximum number
-(G; H) of edge-disjoint H-admissible paths. We can easily get an upper bound on -. Let us call a
sub-partition of V admissible if T ' [X i and each stable in
Clearly,
The value
will be called the value of the sub-partition. Let - (G; H) denote the
minimum value of an admissible sub-partition. We have - .
The following example shows that we do not have equality, in general.
Fig. 2
There are two known special cases when equality holds. Theorem 2.1 shows that this is the case if H is a
complete graph on T . Reformulating Theorem 2.1 we have:
THEOREM 4.1 Suppose that (G; T ) is inner Eulerian and the demand graph H is complete. Then
Another special case for which - is when H consists of two edges, that is,
THEOREM 4.2 Suppose that (G; T ) is inner Eulerian and H consists of two edges
This is a theorem of Rothschild and Whinston. Actually, they proved it in the following simpler form.
THEOREM 4.2' [Rothschild and Whinston, 1966] Suppose that (G; T ) is inner Eulerian and H consists
of two edges is the minimum cardinality - 0 of a cut [X; of G for which
(The equivalence of the two forms, that is, - 0 , may be proved as follows. Since a cut [X;
which provides an admissible partition of special form, clearly - 0 - . To see the
other direction let P:= fX be a minimal admissible sub-partition of G for which k is minimum.
since jT j - 4, we have
exactly two terminal nodes, not connected in H. Furthermore,
if, say, would also be an admissible partition whose value is not bigger
than that of fX is another optimal admissible partition and hence -
If k - 3, then there are two members of P, say X 1 and X 2 , such that each contains one terminal node
and these two terminal nodes, say s are not connected in H. But now by replacing X 1 and X 2 by
another minimal admissible sub-partition contradicting the minimum choice of k. ffl )
Let us call a graph bi-stable if there are two partitions A and B of T such that for x; y 2 T xy
is an edge of H precisely if x and y belong to different parts of A and different parts of B. It is easily seen
that a graph is bi-stable if and only if its complement is the line-graph of a bipartite graph. (It can also be
shown that bi-stable graphs are those for which the family of maximal stable sets of H can be partitioned
into two parts, each consisting of disjoint sets.)
Clearly, a clique, or more generally a complete k-partite graph is bi-stable and 2K 2 is also bi-stable.
Therefore Theorems 2.1 and 2.2 are special cases of the following.
THEOREM 4.3 [Karzanov, 1985], [Lomonosov, 1985] Suppose that (G; T ) is inner Eulerian and
is bi-stable. Then -(G;
A proof of a slightly weaker, half-integral, version was sketched already in [Karzanov and Lomonosov,
1978]. The reader may feel that bi-stable demand graphs form a rather peculiar class of graphs and there
may be larger, more natural classes of graphs for which - holds. Karzanov and Pevzner [1979], however,
showed that if bi-stable and contains no isolated nodes, then there is a supply graph
so that -(G;
In Section 6 we outline our original plan of proof, which was intended to use only the Polymatroid
Intersection Theorem and we point out why that attempt failed. This perhaps will help the reader understand
how we were led to invoke the locking theorem in the proof below.
Proof. By (4.1) we have -(G; To see the other direction, first we prove that the theorem
follows from its special case when the graph is completely Eulerian. So suppose the theorem is true for
is Eulerian and we want to prove it for (G; H) when G is inner Eulerian. Let K
denote the set of nodes of G with odd degree. Since (G; T ) is inner Eulerian K ' T . If K is empty, we
are done. If not, for a new node t, let T 0 t. Let E
respectively, the maximum and minimum in question concerning (G By the assumption -
Obviously, there is an optimal solution to the maximization problem concerning which every
edge xt; x 2 K, is itself a path in the solution. Thus we have - be an
optimal admissible sub-partition for M. Since every edge xt; x 2 T , belongs to
Hence M\GammafXg is an admissible sub-partition for (G; H) and therefore -
can conclude that -
Let A and B be the two partitions of T defining the bi-stable graph H. Note that each stable set of
H is a subset of some S 2 A [ B. Let a and b be defined by (3.1). Since P (a)=2 and P (b)=2 are integral
polymatroids, by Theorem 3.2 there exist an even vector m 0 in P (a) " P (b) and a bi-partition fA; Bg of T
so that
and hence we have
in G. Hence the proof will be complete if we find an admissible sub-partition of value To
this end let us assume that A is a maximal subset of T for which A and B := T \Gamma A satisfy (4.2). We claim
that
Indeed, if we have
from which m 0
that is, the bipartition fA would also satisfy (4.2),
contradicting the maximal choice of A. (Note that, because of this choice of A and B, the role of A and B
will not fully symmetric.)
For each A i 2 A for which A " A i is non-empty there exists a set X
and Here the last equality follows from (4.2) and from the definition of
a. Analogously, for each is non-empty there exists a set Y j for which
Assume that both X i and Y j are chosen minimal and let
non-emptyg.
LEMMA 4.4 K is an admissible sub-partition of value
Proof. Clearly each element of T belongs to at least one member of K and we show that no more than one.
That is, we claim that
and
We have m 0
Hence (4.4a) must hold for otherwise there is an element t 2 (X
would violate (4.3).
Also,
for every
(4.4b) is not true and there is an element t 2 (Y
j is a proper
subset of Y j contradicting the minimal choice of Y j . Hence the proof of (4.4) is complete.
We claim that K is a sub-partition. Assume to the contrary that L " K 6= ; for some K;L 2 K. By the
definition of K and by (4.4) we have ;: The minimal choice of the members of K implies that
By its definition, K is admissible and its value is (
By Lemmata 3.5 and 4.4 and by (4.2) we have and the proof of
Theorem 4.3 is complete. ffl ffl
In this section we briefly outline how the proof above gives rise to a strongly polynomial (combinatorial)
algorithm in the capacitated case. (Informally, a polynomial-time algorithm is strongly polynomial if the
number of steps does not depend on the magnitude of the occurring capacities and costs).
The input of the algorithm consists of two graphs E) and . G is endowed
with a non-negative rational capacity function We assume that by two
partitions of T so that xy 2 F if and only if each A i and each
contains at most one of x and y. (Note that if a graph H is given by its incidence matrix, one can test
H efficiently for bi-stability. Namely, decide first by enumeration whether there are more than 2jT j maximal
stable sets of H. If the answer is yes, then H is not bi-stable. If the answer is no, then H is bi-stable if and
only if the intersection graph of the maximal stable sets is bipartite.)
The output of the algorithm consists of a c-admissible H-multiflow x so that
and of an admissible sub-partition of V . Moreover, if c is integer-valued and
Eulerian in the sense that ffi c (v) is even for every node v 2 V , then the output x is integer-valued, as well.
Actually, we will assume that c is integer-valued and Eulerian. If this is not the case, one can multiply
through the capacities by 2N where N denotes the least common denominator of the capacities. If c is inner
Eulerian, we can apply the reduction described in Section 4 to obtain a completely Eulerian case.
First we remark that the proof of the Locking Theorem immediately provides a polynomial-time algorithm
for the set-system L= A[B when c is identically 1. It is not difficult to show that, for general integer-valued
Eulerian c, if in every step one splits off as much capacities as possible, then the algorithm is strongly
polynomial (cf. [Karzanov, 1984]). In what follows we comment on the use of the polymatroid intersection
algorithm to construct an even vector m 0 and an admissible sub-partition occurring in the proof of Theorem
4.3.
For disjoint sets X;Y ' V let - c (X; Y ) denote the value of a flow between X and Y . With the help of a
Max-flow Min-cut (MFMC) computation - c (X; Y ) can be computed in (strongly) polynomial time.
For be a set function defined by a analogously.
For
(b) be the polymatroids
defined by a and b. It is known from polymatroid theory that P
c is Eulerian, both a=2 and b=2 are integer-valued and hence P (a)=2 and P (b)=2 are integral polymatroids.
Therefore, if z is an integer-valued vector in P
an even vector in P (a) " P (b) for which m 0 (V ) is maximum. By the Polymatroid Intersection Theorem 3.2
there is bi-partition fA; Bg of T so that
There is a (combinatorial) strongly polynomial algorithm, due to P. Sch-onsleben [1980], to compute z
(and hence m 0 ) and fA; Bg. This algorithm works if an oracle is available to minimize
a vector. In our case this oracle can indeed be constructed
by invoking the MFMC algorithm and this way one obtains a purely combinatorial strongly polynomial
algorithm for computing m 0 and A; B satisfying (4.2). Using the proofs of Claims 1 and 2 in the proof of
Theorem 4.3, one may compute in strongly polynomial time an integer-valued maximum multiflow and an
admissible sub-partition of minimum value.
Karzanov [1985] described a more direct way to compute m 0 and a minimal admissible sub-partition.
His method consists of one MFMC computation on an appropriately defined auxiliary digraph on jV jjT j
nodes and its complexity is O('(jT jjV j)) where '(n) denotes the complexity of an MFMC computation on
a network with n nodes.
Next, the even basis m a of P (a) defined in the proof of Theorem 4.3 can be constructed
by jAj (resp., jBj) MFMC computations. Thus vector m defined in (4.4) can be computed from m 0 in
O(jT j'(jV j)) steps.
The m-locking problem can be solved by applying at most O(jV splitting-off operations at every node v 2
each operation consists of finding jAj+jBj maximum flows in G. This requires O(jV j 2 (jAj+jBj)'(jV j))
or O(jV j 2 jT j'(jV j)) operations.
Thus the overall complexity of the algorithm is O(jV one uses an MFMC
algorithm of complexity upper bound for the running time of the
algorithm (to be compared with the complexity of the algorithm in [Karzanov, 1985].
6. NODE-DEMAND PROBLEMS
The reader might have a feeling that invoking the locking theorem in the proof above contains a seemingly
unnecessary twist. In fact, originally we tried to prove Theorem 4.3 by using the following more natural and
direct approach but an example below will show why our attempt failed.
Recall that the polymatroid intersection theorem ensured the existence of a maximum even vector m 0 in
precisely - (G; H). Theorem 4.3 would follow if there existed a system of
H-feasible paths so that each t 2 T is the end-node of precisely m 0 (t) of them. Unfortunately, such a system
need not always exist as is shown by the following example.

Figure
Demand graph H is defined by the partitions A := ffv
Here is an admissible sub-partition of value 3, that is, the maximum -(G; H) is
at most 3. On the other hand there are three H-admissible edge-disjoint paths in G, namely, P 1 :=
Hence the value of the primal and dual optima is
3. It can easily be checked that this system of paths is the only optimal solution. The bad thing is that
two nodes (v 1 and v 4 ) are the end-nodes of just one (that is, an odd number) of paths. Therefore there is no
hope to obtain these paths by first determining an optimal even vector m 0 in the intersection of the two
polymatroids in question and find then H-admissible paths so that each node t 2 T is the end-node of m 0 (t)
of them. Furthermore one must insist of the evenness of m 0 since the Locking Theorem is true only for such
vectors.
(Incidentally, vector m 0 := (2; 2; 2; 0) is an optimal element of the polymatroid intersection and fA :=
;g is a bi-partition of T satisfying (4.2). Vector m arising in the proof is m := (2; 2; 2; 2). When
Theorem 2.3 is applied to this m we obtain a family F of four paths, namely,
Among these paths P 4 is the only non-H-admissible and
we obtain as an optimal solution to the maximization problem.)
Though this direct approach to the maximization problem did not prove successful, it led us to the
following problem, to be considered for its own sake.
E) be a graph Z+ be a
demand function. The node-demand problem consists of finding a system of H-admissible paths so that
each terminal t is the end-node of precisely m(t) paths. We call the problem and also the vector m feasible
when such a solution exists.
The node-demand problem is called Eulerian if it is inner Eulerian and m(t)+d(t) is even for each t 2 T .
We call a demand graph H two-covered (one-covered) if every node t 2 T belongs to at most two (exactly
one) maximal stable sets of H. Note that bi-stable graphs are always two-covered but a 5-element circuit,
for example, is two-covered and not bi-stable. It can be shown that a graph H is two-covered if and only if
H is the complement of the line graph of a triangle-free graph.
THEOREM 6.1 Suppose that the node-demand problem defined by (G; H;m) is Eulerian and H is two-
covered. Then it is feasible if and only if the following condition holds:
for every is stable in H.
Proof. Since S is stable in H, in a solution to the node-demand problem each path with an end-node in S
has the other end-node in T \Gamma S. Among these m(S) paths at most m(X " may end in X \Gamma S and
hence at least m(S) must end outside X from which (6.1) follows.
To prove the sufficiency first observe that the family L of maximal stable sets of H is 3-cross-free. Indeed,
for a contradiction, let stable sets of H which are pairwise crossing. Since H is 2-
there are distinct elements a
is stable and a maximal stable set S containaing a; b; c is distinct from each S i . But then the element a (and
b; c, as well) would belong to more than two maximal stable sets contradicting that H is two-covered.
any stable set S of H.
Proof. Recall that -m (S) was defined to be the maximum number of edge-disjoint paths connecting S
so that each x 2 T is the end-node of at most m(x) ot them. By a version of Menger theorem
apply the edge-disjoint undirected version
of the Menger theorem to the graph arising from G by adding two new nodes s; t so that s (respectively, t)
is connected to each node x in S (resp, in T \Gamma S) by m(x) new parallel edges.)
If X denotes the set where the minimum is attained, then, by (6.1), we have -m
and the claim follows. ffl
Apply Theorem 2.3 to G; m;L and consider the path system F provided by the theorem (where L is the
collection of maximal stable sets of H).
is a solution to the node demand problem.
Proof. Let S be an element of L, that is, a maximal stable set of H. Since F locks S, F contains
connecting S and T \Gamma S. This shows that each node x in S is the end-node of precisely
m(x) members of F and that each path in F having an end-node in S must have the other end-node in
Because every node x of H belongs to a maximal stable set of H, x is the end-node of precisely m(x)
members of F . Moreover, since every pair of non-adjacent nodes x; y of H belong to a maximal stable set
of H, no path in F may connect x and y, that is, F consists of H-feasible paths. ffl ffl
REMARK The condition in Theorem 6.2 may be formulated in an equivalent form. By taking S :=
in (6.1), we see that (6.1) implies
for every maximal stable set Z of H. Conversely, we claim that (6.1) follows from (6.1'). Indeed, let Z be a
maximal stable set of H including S. Then m(S) - m(X "Z) -
and (6.1) follows.
(6.1') has the advantage that there are only a few maximal stable sets in a two-covered graph (at most
2jT j). On the other hand, in the proof above it is slightly easier to work with (6.1).



--R

A solution of a problem of multicommodity flows in a network


Combinatorial methods to solve cut-determined multiflow problems
in: Finite and Infinite Sets
On multicommodity flow problems with integer-valued optimal solutions
A class of maximum multicommodity flows with integer-valued optimal solutions
Systems of flows in undirected networks in: Mathematical Programming
A complete description of the class of cut-nondetermined maximum multicommodity flow problems
Combinatorial approaches to multiflow problems
Combinatorial approaches to multiflow problems
On some connectivity properties of Eulerian graphs

Ganzzahlige Polymatroid Intersections Algorithmen
--TR

--CTR
Michael Lomonosov, On return path packing, European Journal of Combinatorics, v.25 n.1, p.35-53, January 2004
multiflow;locking;network flows;node demands;polymatroid