The Maximum Edge-Disjoint Paths Problem in Bidirected Trees.
A bidirected tree is the directed graph obtained from an undirected tree by replacing each undirected edge by two directed edges with opposite directions. Given a set of directed paths in a bidirected tree, the goal of the maximum edge-disjoint paths problem is to select a maximum-cardinality subset of the paths such that the selected paths are edge-disjoint. This problem can be solved optimally in polynomial time for bidirected trees of constant degree but is APX-hard for bidirected trees of arbitrary degree. For every fixed $\varepsilon >0$, a polynomial-time $(5/3+\varepsilon)$-approximation algorithm is presented.
Introduction
. Research on disjoint paths problems in graphs has a long
history [12]. In recent years, edge-disjoint paths problems have been brought into the
focus of attention by advances in the field of communication networks. Many modern
network architectures establish a virtual circuit between sender and receiver in order
to achieve guaranteed quality of service. When a connection request is accepted, the
network must allocate sufficient resources on all links along a path from the sender
to the receiver. Edge-disjoint paths problems are at the heart of the arising resource
allocation problems.
We study the maximum edge-disjoint paths problem (MEDP) for bidirected tree
networks. A bidirected tree is the directed graph obtained from an undirected tree
by replacing each undirected edge by two directed edges with opposite directions.
Bidirected tree networks have been studied intensively because they are a good model
for optical networks with pairs of unidirectional fiber links between adjacent nodes [26,
MEDP in bidirected trees is defined as follows. Given a bidirected tree E)
and a set P of simple, directed paths in T , the goal is to find a subset P
that the paths in P 0 are edge-disjoint and the cardinality of P 0 is maximized. We say
that an algorithm is a ae-approximation algorithm for MEDP if it always outputs a
subset of edge-disjoint paths whose cardinality is at least a (1=ae)-fraction of
the cardinality of an optimal solution.
The conflict graph of a set of directed paths in a bidirected tree is an undirected
graph with a vertex for each path and an edge between two vertices if the corresponding
paths intersect (i.e., if they share an edge). One can view MEDP in bidirected
trees as a maximum independent set problem in the conflict graph.
We assume that the given tree is rooted at an arbitrary node. For a node v, we
let p(v) denote the parent of v. The level of a node is then defined as its distance to
the root node. The root has level zero. We say that a path touches a node if it begins
at that node, passes through that node, or ends at that node. The level of a path is
the minimum of the levels of all nodes it touches. The unique node on a path whose
level is equal to the level of the path is the least common ancestor (lca) of the path.
A preliminary version of this article has appeared in the Proceedings of the 9th Annual International
Symposium on Algorithms and Computation ISAAC'98, LNCS 1533, pages 179-188, 1998.
y Institut f?r Informatik, TU M-unchen, 80290 M-unchen, Germany (erlebach@in.tum.de).
z IDSIA Lugano, Corso Elvezia 36, 6900 Lugano, Switzerland (klaus@idsia.ch).
We denote a path that begins at node u and ends at node v by (u; v) and its lca by
lca(u; v).
1.1. Results. First, in x2, we determine the complexity of MEDP in bidirected
trees: MEDP can be solved optimally in polynomial time in bidirected trees of constant
degree and in bidirected stars, but it is MAX SNP-hard in bidirected trees of
arbitrary degree. The main result of this paper is summarized by the following theorem

Theorem 1.1. For every fixed " ? 0, there is a polynomial-time approximation
algorithm for the maximum edge-disjoint paths problem in bidirected trees with
approximation ratio 5=3
The description of the algorithm and a proof that the claimed approximation ratio
is indeed achieved appear in x3. In x4, we discuss how our results can be generalized
to the weighted version of the problem and to the maximum path coloring problem.
1.2. Related work.
Path coloring in bidirected trees. Previous work on bidirected trees has focused
on the path coloring problem: Given a set of directed paths in a bidirected tree, assign
colors to the paths such that paths receive different colors if they share an edge. The
goal is to minimize the total number of colors used. This problem is NP-hard even
for binary trees [8, 24]. The best known approximation algorithms [11, 10] use at most
d(5=3)Le colors, where L is the maximum load (the load of an edge is the number
of paths using that edge) and thus a lower bound on the optimal solution. Previous
algorithms had used (15=8)L colors [26] and (7=4)L colors [18, 25] in the worst case.
For the special case of all-to-all path coloring, it was shown that the optimal number
of colors is equal to the maximum load [14].
Multicommodity flow in trees. Garg et al. [13] studied the integral multicommodity
flow problem in undirected trees, which is a generalization of MEDP in undirected
trees. They showed that the problem with unit edge capacities (equivalent to MEDP
in undirected trees) can be solved optimally in polynomial time. For undirected trees
with edge capacities one or two, they proved the problem MAX SNP-hard. They also
presented a 2-approximation algorithm for integral multicommodity flow in trees. It
works by considering the demands in order of non-increasing levels of their lcas and
by satisfying them greedily. This approximation algorithm can be adapted to MEDP
in bidirected trees, where it also gives a 2-approximation. The main idea that leads
to our improved approximation algorithm for MEDP in bidirected trees is to consider
all paths with the same lca simultaneously instead of one by one.
Online algorithms for MEDP in trees. MEDP has also been studied in the on-line
scenario, where the paths are given to the algorithm one by one. The algorithm must
accept or reject each path without knowledge about future requests. Preemption is not
allowed. It is easy to see that no deterministic algorithm can have a competitive ratio
better than the diameter of the tree in this case. Awerbuch et al. gave a randomized
algorithm with competitive ratio O(log n) for undirected trees with n nodes [2]. Their
algorithm works also for bidirected trees. An improved randomized algorithm with
competitive ratio O(log d) for undirected trees with diameter d was given in [3].
MEDP for other topologies. If MEDP is studied for arbitrary graphs, the algorithm
must solve both a routing problem and a selection problem. For arbitrary
directed graphs with m edges, MEDP was recently shown to be NP-hard to approximate
within m 1=2\Gamma" [16]. Approximation algorithms with approximation ratio
O( p
m) are known for the unweighted case [20, 28] and for the weighted case [22]. Better
approximation ratios can be achieved for restricted classes of graphs. For a class
EDGE-DISJOINT PATHS IN BIDIRECTED TREES 3
of planar graphs containing two-dimensional mesh networks, an O(1)-approximation
algorithm has been devised in [21].
2. Complexity results. MEDP in bidirected trees is NP-hard in general. This
can be proved by a reduction from 3D-matching that is similar to the reduction
used by Garg et al. to prove the NP-hardness of integral multicommodity flow in
undirected trees with edge capacities one and two [13]. We omit the details, because
the modification is straightforward. If we reduce from the bounded variant of the
3D-matching problem [19], the reduction is an L-reduction and an AP-reduction,
implying that MEDP in bidirected trees is MAX SNP-hard [27] and APX -hard [7].
This shows that there is no polynomial-time approximation scheme for the problem
Nevertheless, MEDP can be solved optimally in polynomial time if the input
is restricted in certain ways. First, consider the case that the maximum degree of
the given tree is bounded by a constant. The optimal solution can be computed by
dynamic programming in this case. We process the nodes of the tree in order of
non-increasing levels. At every node v, we record for each possible subset S of edge-disjoint
paths touching v and its parent (note that jSj - 2) the maximum number of
paths contained in the subtree rooted at v that can be accepted in addition to the
paths in S. Node v is processed only when these values are known for all its children.
We can then enumerate all possible edge-disjoint subsets of paths touching v. For
each such subset, we can look up the corresponding values stored at children of v
and update the values stored at v accordingly. Note that there are only polynomially
many subsets to consider at each node. When the root node has been processed, the
optimal solution can easily be constructed.
Another special case that can be solved optimally in polynomial time is the case
that the given bidirected tree T is a star, i.e., it contains only one node with degree
greater than one. MEDP in bidirected stars can be reduced to the maximum matching
problem in a bipartite graph as follows. First, we can assume without loss of generality
that every given path uses exactly two edges of the star; if a path uses only one
edge, we can add a new node to the star and extend the path by one edge without
changing the set of solutions. Now, observe that every path uses exactly one edge
directed towards the center and one edge directed away from the center of the star.
Construct a bipartite graph G by including a vertex for every edge of the star and
by adding an edge between two vertices u and v in G for every path in T that uses
the edges corresponding to u and v. Two paths in T are edge-disjoint if and only if
the corresponding edges in G do not share an endpoint. Sets of edge-disjoint paths
in T correspond to matchings in G. A maximum matching in G can be computed in
polynomial time [17].
The latter result can actually be generalized from stars to spiders. A spider is a
bidirected tree in which at most one node (the center) has degree greater than two.
MEDP in a bidirected spider can be solved in polynomial time using an algorithm
for the maximum-weight bipartite matching problem as a subroutine. The bipartite
graph G is constructed as above from the paths touching the center of the spider, and
the weight of an edge e in G specifies how many fewer paths not touching the center
of the spider can be accepted if the path corresponding to e is accepted. The details
are left to the reader.
3. Approximating the optimal solution. Fix any " ? 0. Let an instance of
the maximum edge-disjoint paths problem be given by a bidirected tree T and a set
4 T. ERLEBACH AND K. JANSEN
P of directed paths in T . Denote by P   an arbitrary optimal solution for the given
instance.
The algorithm proceeds in two passes. In the first pass, it processes the nodes
of T in order of non-increasing levels (i.e., bottom-up). Assume that the algorithm
is about to process node v. Let P v denote the subset of all paths (u; w) 2 P with
that do not intersect any of the paths that have been accepted by the
algorithm at a previous node and that do not use any edges that have been reserved or
fixed by the algorithm (see below). For the sake of simplicity, we can assume without
loss of generality that we have u otherwise, we
could add an additional child to v for each path in P v starting or ending at v and
make the path start or end at this new child instead. Every path uses exactly
two edges incident to v, and we refer to these two edges as the top edges of p. We say
that two paths are equivalent if they use the same
two edges incident to v, i.e., if their top edges are the same. For a set Q of paths with
the same lca, this defines a partition of Q into different equivalence classes of paths
in the natural way.
While the algorithm processes node v, it tries to determine for the paths in P v
whether they should be included in the solution (these paths are called accepted)
or not (these paths are called rejected ). Sometimes, however, the algorithm cannot
make this decision right away. In these cases the algorithm will leave some paths in
an intermediate state and resolve them later on. The possibilities for paths in such
intermediate states are
(i) undetermined paths,
(ii) groups of deferred paths,
(iii) groups of exclusive paths, and
(iv) groups of 2-exclusive paths.
We refer to undetermined paths and to paths in groups of exclusive paths and in
groups of 2-exclusive paths as unresolved paths and to paths in groups of deferred paths
as deferred paths. The status of unresolved paths is resolved at later nodes during the
first pass. The second pass of the algorithm proceeds top-down and accepts one path
from each group of deferred paths.
3.1. Paths in intermediate states. In the following we give explanations regarding
the possible groups of paths in intermediate states. First, the algorithm will
sometimes leave a single path p of P v in an undetermined state. If P v has only one
equivalence class of paths, accepting a path might cause the algorithm to
miss the chance of accepting two paths of smaller level (than v) later on. Hence, the
algorithm could at best achieve a 2-approximation. Therefore, instead of accepting or
rejecting the paths in P v right away, the algorithm picks one of them and makes it an
undetermined path. All other paths in P v , if any, are rejected, and the undetermined
path will be accepted or rejected at a later node.
A second situation in which the algorithm does not accept or reject all paths in
right away is sketched in Fig. 3.1. (Here and in the following, pairs of oppositely
directed edges are drawn as undirected edges in all figures.) In this situation, the
algorithm decides to accept one of several intersecting paths from P v , but it defers
the decision which one of them to accept. The intersecting paths are called a group
of deferred paths. All paths in a group of deferred paths use the same edge incident
to v and to a child c of v. In the figure, this is the edge (c; v). (The case that the
deferred paths share the edge (v; c) is symmetrical.) Furthermore, each deferred path
uses also an edge (v; c 0 ) connecting v and a child c 0 6= c, and not all of the deferred
EDGE-DISJOINT PATHS IN BIDIRECTED TREES 5
e
c
Fig. 3.1. A group of deferred paths.
c
c
Fig. 3.2. Possible configuration of a group of exclusive paths (left-hand side), and situation in
which both exclusive paths are blocked (right-hand side).
paths use the same such edge. If the algorithm decides to create a new group of
deferred paths, it marks the edge (c; v) as reserved (assuring that no path accepted
at a node processed after v can use the edge), but leaves all edges (v; c 0 ) for children
available. The reserved edge is indicated by a dashed arrow in Fig. 3.1. The
motivation for introducing groups of deferred paths is as follows: first, the reserved
edge blocks at most one path of smaller level that could be accepted in an optimal
solution; second, no matter which path using the edge (p(v); v) is accepted at a node
processed after v, that path uses at most one of the edges (v; c 0 ), and as there is still
at least one deferred path that does not use that particular edge (v; c 0 ), the algorithm
can pick such a deferred path in the second pass. When processing later nodes during
the first pass, the algorithm actually treats the group of deferred paths like a single
accepted path that uses only the reserved edge of the deferred paths.
A group of exclusive paths is sketched in Fig. 3.2 (left-hand side). Such a group
consists of one path q (called the lower path) contained in the subtree rooted at a
child c of v and one path p (called the higher path) with lca v that intersects q. At
most one of the two paths can be accepted, but if the algorithm picks the wrong one
this choice can cause the algorithm to accept only one path while the optimal solution
would accept the other path and one or two additional paths. Hence, the algorithm
defers the decision which path to accept until a later node. For now, it only marks
6 T. ERLEBACH AND K. JANSEN
Fig. 3.3. Group of 2-exclusive paths consisting of a pair of independent groups of exclusive paths.
the top edge of path q that is intersected by p as fixed. (Fixed edges are indicated by
dotted arrows in our figures.) Obviously, a group of exclusive paths has the following
property.
Property (E). If at most one path touching v but not using the fixed edge is
accepted at a later node, either p or q can still be accepted. Only when two paths
touching v are accepted at a later node, they can block p and q from being accepted.
The right-hand side of Fig. 3.2 shows how two paths accepted at a later node can
block both exclusive paths. While processing later nodes, the algorithm will try to
avoid this whenever possible.
The last types of unresolved paths are sketched in Figures 3.3 and 3.4. These
groups of 2-exclusive paths consist of a set of four paths at most two of which can
be accepted. More precisely, the first possibility for a group of 2-exclusive paths is
to consist of two independent groups of exclusive paths (Fig. 3.3), i.e., of two groups
of exclusive paths such that the fixed edge of one group is directed towards the root
and the fixed edge of the other group is directed towards the leaves. Furthermore,
the two groups must either be contained in disjoint subtrees (as shown in Fig. 3.3), or
only their lower paths are contained in disjoint subtrees and their higher paths do not
intersect each other. A pair of independent groups of exclusive paths has two fixed
edges: the fixed edges of both groups.
The second possibility for a group of 2-exclusive paths is to consist of a group of
exclusive paths contained in a subtree rooted at a child of v and two paths
with lca v that intersect the exclusive paths (but not their fixed edge) in a way such
that accepting p 1 and p 2 would block both of the exclusive paths from being accepted
(Fig. 3.4). Two edges are marked fixed, namely the top edge of the higher exclusive
path intersected by a path with lca v and the top edge of the lower exclusive path
intersected by a path with lca v. It is not difficult to show by case analysis that a
group of 2-exclusive paths has the following property.
Property (2E). If at most one path touching v but not using a fixed edge is
accepted at a later node, two paths from the group of 2-exclusive paths can still be
accepted. If two paths touching v but not using a fixed edge are accepted at a later
node, at least one path from the group of 2-exclusive paths can still be accepted.
While processing later nodes, the algorithm will try to avoid accepting two paths
touching v such that only one path from the group of 2-exclusive paths can be accepted

EDGE-DISJOINT PATHS IN BIDIRECTED TREES 7
vFig. 3.4. Further configurations of groups of 2-exclusive paths.
3.2. Invariants. In x3.4 we will present the details of how the algorithm proceeds
during the first pass. At the same time, we will show that the approximation
ratio achieved by the algorithm is 5=3 ". In order to establish this, we will prove
by induction that the following invariants can be maintained. These invariants hold
before the first node of T is processed, and they hold again each time an additional
node of T has been processed. A node v is called a root of a processed subtree if the
node v has already been processed but its parent has not.
Invariant A. For every root v of a processed subtree, all paths in that subtree
are accepted, rejected, or deferred except if one of the following cases occurs:
(i) The subtree contains one undetermined path. All other paths contained in
the subtree are accepted, rejected, or deferred. No edge in the subtree is marked fixed.
(ii) The subtree contains one group of exclusive paths. All other paths contained
in the subtree are accepted, rejected, or deferred. The only edge marked fixed in the
subtree is the one from the group of exclusive paths.
(iii) The subtree contains one group of 2-exclusive paths. All other paths contained
in the subtree are accepted, rejected, or deferred. The only edges marked fixed
in the subtree are the two from the group of 2-exclusive paths.
All accepted paths are edge-disjoint and do not contain any reserved edges. Every unresolved
path is edge-disjoint from all accepted paths and does not contain any reserved
edges. Every deferred path contains exactly one reserved edge: the reserved edge of
the group of deferred paths to which the path belongs. If a deferred path p intersects
an accepted or unresolved path q, then the level of q is smaller than that of p.
Invariant B. Let A be the set of all paths that have already been accepted by the
algorithm. Let F be the set of all paths in P whose lca has not yet been processed
and which are not blocked by any of the accepted paths, by reserved edges, or by fixed
edges. Let d be the number of groups of deferred paths that are contained in processed
subtrees. Let U be the set of all undetermined paths. Let X be the union of all groups of
exclusive paths and groups of 2-exclusive paths. Then there is a subset O ' F [U [X
of edge-disjoint paths satisfying the following conditions:
(a) jP   j - (5=3
(b) For every group of exclusive paths, O contains one path from that group; for
every group of 2-exclusive paths, O contains two paths from that group.
Intuitively, the set O represents a subset of P containing edge-disjoint paths that
could still be accepted by the algorithm and that has the following property: if the
algorithm accepts at least a 1=(5=3+ ")-fraction of the paths in O (in addition to the
8 T. ERLEBACH AND K. JANSEN
paths it has already accepted), its output is a (5=3 + ")-approximation of the optimal
solution.
Observe that the invariants are satisfied initially with
While it will be easy to see from the description of
the algorithm that Invariant A is indeed maintained throughout the first pass, special
care must be taken to prove that Invariant B is maintained as well.
3.3. The second pass. If the invariants are satisfied after the root node is
processed, we have jOj. At this
time, there can still be one undetermined path (which can, but need not be contained
in O: therefore, jOj 2 f0; 1g in this case) one group of exclusive paths (from which
O contains exactly one path, or one group of 2-exclusive paths (from which
O contains two edge-disjopint paths, 2). If there is an undetermined path, the
algorithm accepts it. If there is a group of exclusive paths, the algorithm accepts one
of them arbitrarily. If there is a group of 2-exclusive paths, the algorithm accepts two
edge-disjoint paths of them arbitrarily. The algorithm accepts at least jOj additional
paths in this way, and the resulting set A 0 of accepted paths satisfies jA
and, therefore, jP   j - (5=3
In the second pass, the algorithm processes the nodes of the tree in reverse order,
i.e., according to non-decreasing levels (top-down). At each node v that is the lca of
at least one group of deferred paths, it accepts one path from each of the groups of
deferred paths such that these paths are edge-disjoint from all previously accepted
paths and from each other. This can always be done due to the definition of groups
of deferred paths. Hence, the number of paths accepted by the algorithm increases
by d in the second pass, and the set A 00 of paths that are accepted by the algorithm in
the end satisfies jA 00
Theorem 1.1.
3.4. Details of the first pass. Assume that the algorithm is about to process
node v. Recall that P v ' P is the set of all paths with lca v that do not intersect
any previously accepted path nor any fixed or reserved edge. Let U v be the set of
undetermined paths contained in subtrees rooted at children of v. Let X v be the set
of all paths in groups of exclusive paths and groups of 2-exclusive paths contained
in subtrees rooted at children of v. In the following, we explain how the algorithm
processes node v and determines which of the paths in P v [U v [X v should be accepted,
rejected, deferred, or left (or put) in an unresolved state.
Observe that for a given set of paths with lca v the problem of determining a
maximum-cardinality subset of edge-disjoint paths is equivalent to solving MEDP in
a star and can thus be done in polynomial time by computing a maximum matching
in a bipartite graph (cf. x2). Whenever we use an expression like compute a maximum
number of edge-disjoint paths in S ' P v in the following, we imply that the computation
should be carried out by employing this reduction to maximum matching.
We will use the following property of bipartite graphs: for 2, the fact
that a maximum matching in a bipartite graph G has cardinality s implies that there
are s vertices in G such that every edge is incident to at least one of these s vertices.
(The property holds for arbitrary values of s and is known as the K-onig theorem [23];
see, e.g., the book by Berge [4, pp. 132-133].)
Observe that each child of the current node v is the root of a processed subtree,
which can, by Invariant A, contain at most one of the following: one undetermined
path, or one group of exclusive paths, or one group of 2-exclusive paths. Let k be
the number of children of v that have an undetermined path in their subtree, let ' be
EDGE-DISJOINT PATHS IN BIDIRECTED TREES 9
the number of children of v that have a group of exclusive paths, and let m be the
number of children of v that have a group of 2-exclusive paths. We use the expression
subtrees with exclusive paths to refer to all subtrees rooted at children of v with either
a group of exclusive paths or with a group of 2-exclusive paths.
Note that one main difficulty lies in determining which of the paths in U v [
should be accepted and which should be rejected. If k bounded by a
constant, all possible combinations of accepting and rejecting paths in U v [X v can be
tried out in polynomial time, but if k is large, the algorithm must proceed in
a different way in order to make sufficiently good decisions. The exact threshold for
determining when k considered large and, consequently, the running-time
of the algorithm depend on the constant ".
Let F , U , X , A and d denote the quantities defined in x3.2 at the instant just
before the algorithm processes node v. Let F 0 , U 0 , X 0 , A 0 and d 0 denote the respective
quantities right after node v is processed. Furthermore, denote by a v the number of
paths that are newly accepted while processing v and by d v the number of groups of
deferred paths that are newly created while processing v.
We can assume that there is a set O ' F [U [X of edge-disjoint paths satisfying
Conditions (a) and (b) of Invariant B before v is processed. In every single case of the
following case analysis, we show how to construct a set O 0 that satisfies Invariant B
after v is processed. O 0 is obtained from O by replacing paths, removing paths,
or inserting paths as required. In particular, O 0 must be a set of edge-disjoint paths
satisfying O 0 ' F 0 [U 0 [X 0 . Therefore, all paths intersecting a newly accepted path or
the reserved edge of a newly created group of deferred paths must be removed from O.
Note that at most two such paths can have smaller level than v, because all such paths
of smaller level must use the edge (v; p(v)) or (p(v); v). Paths that are rejected by the
algorithm must be removed or replaced in O. If a new group of exclusive paths or
group of 2-exclusive paths is created, O 0 must contain one or two paths, respectively,
from that group so that Condition (b) of Invariant B is maintained. Furthermore, we
must ensure that jO 0 j is smaller than jOj by at most ( 5
As the value jAj+d
increases by a v while v is processed (i.e., we have jA
this implies that Condition (a) of Invariant B holds also after v is processed, i.e.,
Case 1. 2="g. The algorithm can try out all combinations
of accepting or rejecting unresolved paths in the subtrees rooted at children of v:
for undetermined paths there are two possibilities (accepting or rejecting the path),
for groups of exclusive paths there are two possibilities (accepting the lower path or
accepting the higher path), and for groups of 2-exclusive paths there are either four
possibilities (in the case of a pair of independent groups of exclusive paths as shown
in Fig. 3.3 on page accepting the lower or higher path in one group and the lower
or higher path in the other group) or two relevant possibilities (in the cases shown
in Fig. 3.4 on page 7: accepting the lower or higher path of the group of exclusive
paths contained in the group of 2-exclusive paths and the edge-disjoint path among
the remaining two paths; note that accepting no path of the group of exclusive paths
and only the remaining two paths blocks more paths from F than any of the other
two possibilities, hence we do not need to consider this third possibility) of accepting
two edge-disjoint paths of the group. Hence, the number of possible combinations is
bounded from above by 2 k+' 4 O(1). For each combination fl, the algorithm
computes a maximum number s fl of edge-disjoint paths in P v not intersecting
any of the u fl paths from U v [X v that are (tentatively) accepted for this combination.
Let s be the maximum of u taken over all combinations fl. Note that s is the
cardinality of a maximum-cardinality subset of edge-disjoint paths in
and the algorithm does nothing and
proceeds with the next node. Otherwise, we distinguish the following cases.
Case 1.1.
Case 1.1.1. has only one equivalence class of paths, pick
one of them, say p, arbitrarily and make it an undetermined path. (Hence,
and U Reject all other paths in P v . If O contains a path p 0 6= p from P v ,
replace p 0 by p in O to obtain O 0 (in order to ensure O
O We have a j. Obviously, the invariants are satisfied.
If P v has more than one equivalence class of paths, there must be an edge e
incident to v that is shared by all paths in P v (as a consequence of the K-onig theorem).
Make P v a group of deferred paths with reserved edge e. We have a
O can contain at most one path intersecting edge e: either a path from P v or a path of
smaller level. It suffices to remove this path from O in order to obtain a valid set O 0 ,
and we get and the
invariants are satisfied.
Case 1.1.2. There is one child c of v that has an undetermined
path p with lca w in its subtree, possibly the algorithm does
nothing and leaves p in its undetermined state. If P v 6= ;, all paths in P v must
intersect p in the same edge, say in the edge (u; w) with (The case that
they intersect p in an edge (w; u) is symmetrical.) The algorithm picks an arbitrary
path q from P v and makes fp; qg a group of exclusive paths with fixed edge (u; w).
(Hence, other paths in P v are rejected, and we have
a must ensure that O 0 contains p or q in order to satisfy Condition (b)
of Invariant B. If O does not contain any path from P v [ U v , by Property (E) either
or q can be inserted into O after removing at most one path of smaller level. If
O contains a path p 0 from P v [ U v already, this path can be replaced by p or q if
and the invariants are satisfied.
Case 1.1.3. 1. There is one child of v that has a group of
exclusive paths in its subtree. As any path from P v could be combined with a path
from the group of exclusive paths to obtain two edge-disjoint paths and because we
have assumed must have Hence, the algorithm does nothing at
node v and leaves the group of exclusive paths in its intermediate state.
Case 1.2. 2. Observe that k 2. In many of the subcases of
Case 1.2, the algorithm will yield a v 2. If O contains at most one path from
removing that path and at most two paths of smaller level is clearly
sufficient to obtain a valid set O 0 in such subcases. Therefore, we do not repeat this
argument in every relevant subcase; instead, we discuss only the case that O contains
two paths from
Case 1.2.1. There is a subtree rooted at a child of v that
contains a group of 2-exclusive paths. We must have any path in P v
could be combined with two paths from X v to form a set of three edge-disjoint paths.
Hence, the algorithm does nothing at node v and leaves the group of 2-exclusive paths
in its unresolved state.
Case 1.2.2. There are two children of v whose subtrees contain
a group of exclusive paths. Note that this case, as any path
from P v could be combined with one exclusive path from each subtree to obtain a set
of three edge-disjoint paths.
EDGE-DISJOINT PATHS IN BIDIRECTED TREES 11
e
Fig. 3.5. Case 1.2.3.1: Pv contains two edge-disjoint paths (left-hand side); Case 1.2.3.2 (a):
The fixed edge and e have the same direction (right-hand side).
If the fixed edges of both groups of exclusive paths point in the same direction
(i.e., are both directed to the root or to the leaves), the algorithm accepts the lower
paths of both groups of exclusive paths. The higher paths are rejected, and no edge is
marked fixed anymore. We have a 0, and at most three paths must be
removed from O to obtain a valid set O 0 : the two paths from the groups of exclusive
paths that are contained in O, and at most one path of smaller level using the edge
between v and p(v) whose direction is opposite to the direction of the formerly fixed
edges.
If the fixed edges of the groups of exclusive paths point in different directions (i.e.,
one is directed towards the root and one towards the leaves), the groups represent a
pair of independent groups of exclusive paths, and the algorithm can create a new
group of 2-exclusive paths. Note that O contains two paths from the new group of
2-exclusive paths already, because it contained one path from each of the two groups
of exclusive paths in X v due to Condition (b) of Invariant B. Therefore, we can set
O and the invariants are satisfied.
Case 1.2.3. There is one child of v that has a group of
exclusive paths in its subtree and one child of v that has an undetermined path in its
subtree. All paths in P v must intersect the undetermined path, because otherwise a
path from P v could be combined with the undetermined path and an exclusive path
to obtain a set of three edge-disjoint paths.
Case 1.2.3.1. There are two edge-disjoint paths in P v . In this case, the situation
must be as shown on the left-hand side of Fig. 3.5: the two edge-disjoint paths from
must intersect the group of exclusive paths in a way that blocks all exclusive paths
from being accepted, and there cannot be any other kinds of paths in P v .
The algorithm accepts the lower path from the group of exclusive paths and the
undetermined path, and it rejects all other paths in marked
fixed anymore. We have a Note that any combination of two
edge-disjoint paths from P v [U v [X v blocks at least three of the four top edges of the
paths accepted by the algorithm. Hence, if O contains two paths from
it can contain at most one path of smaller level intersecting the paths accepted by
the algorithm, and it suffices to remove at most three paths from O to obtain a valid
e
e
Fig. 3.6. Cases 1.2.3.2 (b) and 1.2.3.2 (c): The fixed edge and e have different directions.
Case 1.2.3.2. All paths in P v intersect the same edge e of the undetermined path.
Case 1.2.3.2 (a). The direction of e is the same as that of the fixed edge of the
group of exclusive paths (see the right-hand side of Fig. 3.5). The algorithm accepts
the undetermined path and the lower path from the group of exclusive paths. All
other paths in are rejected, and no edge is marked fixed anymore. We have
a O contains two paths from P v [ use
the fixed edge and the edge e, and at most one further path from O can be blocked by
the paths accepted by the algorithm (because such a path must use the edge between
v and p(v) in the direction opposite to the direction of e). Thus, it suffices to remove
at most three paths from O to obtain a valid set O 0 .
Case 1.2.3.2 (b). The direction of e is different from that of the fixed edge, and
there is a path that does not intersect the higher exclusive path (see the left-hand
side of Fig. 3.6). The algorithm uses X v , p and the undetermined path together
to create a new group of 2-exclusive paths consisting of a pair of independent groups
of exclusive paths. All other paths is P v are rejected by the algorithm. In addition to
the fixed edge of the old group of exclusive paths, the edge e is marked fixed. Note
that O contains one path from X v due to Condition (b) of Invariant B. If O contains
the undetermined path or the path p, let O O contains a path other than p
from P v , replace this path either by p or by the undetermined path (one of these
must be possible). If O does not contain a path from P v [ U v but contains a path p 0
using the edge between v and p(v) in the direction given by edge e, replace p 0 either
by p or by the undetermined path (one of the two must be possible). If O does not
contain a path from P v [ U v and no path using the edge between v and p(v) in the
direction given by edge e, add either p or the undetermined path to O. In any case,
the invariants are satisfied. In particular, jO
Case 1.2.3.2 (c). The direction of e is different from that of the fixed edge, and
all paths in P v intersect the higher exclusive path (see the right-hand side of Fig. 3.6).
The algorithm accepts the undetermined path and the lower path from the group of
exclusive paths, and it rejects all other paths from marked fixed
anymore. We have a O contains two paths from
must contain at least one of the two paths accepted by the algorithm, and the other
path in O uses a top edge of the other path accepted by the algorithm. O contains at
most one path of smaller level intersecting the paths accepted by the algorithm, and
it suffices to remove at most three paths from O in order to obtain a valid set O 0 .
EDGE-DISJOINT PATHS IN BIDIRECTED TREES 13epe
pp c c" c'
pp
p'
c c" c'
Fig. 3.7. Case 1.2.4.1: Pv contains two edge-disjoint paths that block the exclusive paths.
Case 1.2.4. There is one child c of v that has a group of
exclusive paths in its subtree. Denote the higher and the lower path in the group of
exclusive paths by p and q, respectively. Assume without loss of generality that the
fixed edge e 0 of the group of exclusive paths is directed towards the root of the tree
(as shown in Fig. 3.7). Note that We distinguish further cases
regarding the maximum number of edge-disjoint paths in P v .
Case 1.2.4.1. There are two edge-disjoint paths p 1 and p 2 in P v . As
must intersect the exclusive paths in a way that blocks all of them from being
accepted. See Fig. 3.7. Let p 1 intersect p, and let p 2 intersect q. Let c 0 6= c be the
child of v such that p 1 uses the edges (c; v) and (v; c 0 ), and let c 00 6= c be the child
of v such that p 2 uses the edges (c 00 ; v) and (v; c). Note that c
the top edge of p intersected by p 1 be e 1 , and let the top edge of q intersected by p 2
be e 2 . As contains only two edge-disjoint paths, every path p must
either intersect edge e 1 , or intersect edge e 2 , or intersect both p 1 and p 2 . (The latter
case is possible only if c 0 6= c 00 and if all paths in P v that intersect e 1 use the edges
(c; v) and (v; c 0 ) and all paths in P v that intersect e 2 use the edges (c 00 ; v) and (v; c); in
that case, p 0 must use as shown on the right-hand side of Fig. 3.7.)
Case 1.2.4.1 (a). All paths in P v that intersect e 1 use the edges (c; v) and (v; c 0 ),
and all paths in P v that intersect e 2 use the edges
First, assume that all paths in P v intersect either e 1 or e 2 . Note that there are
exactly two equivalence classes of paths in P v in this case. See Fig. 3.7 (left-hand
side). The algorithm uses the group of exclusive paths and one representative from
each of the two equivalence classes of paths in P v to create a group of 2-exclusive
paths. All other paths in P v are rejected. The fixed edge e 0 of the group of exclusive
paths is no longer marked fixed, instead the edges e 1 and e 2 are marked fixed. If O
contains two paths from P v [X v , one of them must be from X v due to Condition (b)
of Invariant B and the other can be replaced by a path in the new group of 2-exclusive
paths. Otherwise, it is possible to remove the path from X v and at most one additional
path from O such that the resulting set contains no path from P v [ X v , at most one
14 T. ERLEBACH AND K. JANSEN
path of smaller level touching v, and no path of smaller level intersecting a fixed edge
of the new group of 2-exclusive paths. By Property (2E), two paths from the new
group of 2-exclusive paths can then be inserted into that set to obtain O 0 . We have
and the invariants are satisfied.
Now, assume that there is a path p 0 2 P v that intersects neither e 1 nor e 2 . As
noted above, we must have c 0 6= c 00 in this case, and p 0 must use the edges
Fig. 3.7 (right-hand side). The algorithm accepts the lower path from the
group of exclusive paths and the path p 0 , and it rejects all other paths in
No edge is marked fixed anymore. We have a Note that any
combination of two edge-disjoint paths from blocks at least three of the four
top edges of the paths accepted by the algorithm. Hence, if O contains two paths
from can contain at most one path of smaller level intersecting the paths
accepted by the algorithm, and it suffices to remove at most three paths from O to
obtain a valid set O 0 .
Case 1.2.4.1 (b). There are at least two equivalence classes of paths in P v intersecting
the higher path of the group of exclusive paths. The algorithm accepts the
lower path of the group of exclusive paths and makes the paths in P v intersecting the
higher path a group of deferred paths. All other paths in P v [X v are rejected, and no
edge is marked fixed anymore. The reserved edge of the group of deferred paths is the
top edge shared by all these paths. If O contains two paths from P v [ X v , note that
one of the two paths must be from X v (due to Condition (b) of Invariant B) and that
these two paths also block the top edges of the lower path of the group of exclusive
paths. Hence, O cannot contain any path of smaller level intersecting the lower path,
and it can contain at most one path of smaller level intersecting the reserved edge of
the newly deferred paths. It suffices to remove at most three paths from O to obtain
a valid set O 0 .
Case 1.2.4.1 (c). There is only one equivalence class of paths in P v intersecting
the higher path of the group of exclusive paths, and there are at least two equivalence
classes of paths in P v intersecting the lower path of the group of exclusive paths.
The algorithm accepts the higher path of the group of exclusive paths and makes the
paths in P v intersecting the lower path a group of deferred paths. All other paths
in are rejected, and no edge is marked fixed anymore. The reserved edge of
the group of deferred paths is the top edge shared by all these paths. If O contains
two paths from note that one of the two paths must be from X v (due to
Condition (b) of Invariant B) and that these two paths also block edge e 1 . Hence, O
cannot contain any path of smaller level intersecting e 1 , and it can contain at most
one path of smaller level intersecting the reserved edge of the newly deferred paths or
the top edge of the higher path that is directed towards the leaves, because all such
paths must use the edge (p(v); v). It suffices to remove at most three paths from O
to obtain a valid set O 0 .
Case 1.2.4.2. P v does not contain two edge-disjoint paths. Let e be an edge
incident to v such that all paths in P v use edge e.
Case 1.2.4.2 (a). has at least two different
equivalence classes of paths. The algorithm makes all paths in P v a new group of
deferred paths with reserved edge e and accepts q, the lower path of the group of
exclusive paths. Path p is rejected, and no edge in this subtree is marked fixed
anymore. We have a O contains two paths from P v [ X v , these paths
block two of the three top edges blocked by the algorithm: the fixed edge e 0 of the
group of exclusive paths and edge e. O can contain at most one path of smaller level
Fig. 3.8. Case 1.2.5 (a): All sets of two edge-disjoint paths use the same four top edges (left-
hand side); Case 1.2.5 (b): there is only one equivalence class of paths using edge e 1 , but more than
one class using edge e2 (right-hand side).
that intersects the path accepted by the algorithm or the reserved edge of the new
group of deferred paths, and it suffices to remove at most three paths from O to obtain
a valid set O 0 .
Case 1.2.4.2 (b). e 6= (v; c 0 ) for all children c 0 6= c of v, or P v has only one
equivalence class of paths. If there is a path p that does not intersect q, the
algorithm accepts p 0 and q. If all paths in P v intersect q, the algorithm accepts p and
an arbitrary path from P v . In both cases, all other paths in P v [X v are rejected, and
no edge in this subtree is marked fixed anymore. We have d 2. Assume
that O contains two paths from P v [ X v . We will show that it suffices to remove at
most three paths from O to obtain a valid set O 0 .
If the algorithm has accepted p, O must also contain p and a path from P v , thus
blocking at least three of the four top edges of the paths accepted by the algorithm.
At most one further path in O can be blocked by the paths accepted by the algorithm.
Now assume that the algorithm has accepted q. Observe that the two paths from
that are in O must also use the edges e 0 and e, thus blocking two of the four
top edges of paths accepted by the algorithm. If e and e 0 have the same direction,
O can contain at most one path of smaller level intersecting the paths accepted by
the algorithm, because such a path must use the edge (p(v); v). If P v has only one
equivalence class of paths, the paths from P v [X v that are in O block three of the four
top edges of paths accepted by the algorithm, and again it suffices to remove at most
one path of smaller level from O. Finally, consider the case that P v has more than
one equivalence class of paths and that e = (v; c). Since edge e blocks more paths of
smaller level than the top edge of q that is directed towards the leaves, the two paths
from P v [X v that are in O do in fact block at least as many paths of smaller level as
three of the four top edges of the paths accepted by the algorithm.
Case 1.2.5. there must be two edges incident to v such
that all paths in P v use at least one of these two edges (by the K-onig theorem). Let
e 1 and e 2 be two such edges.
Case 1.2.5 (a). All possible sets of two edge-disjoint paths from P v use the same
four edges incident to v. See the left-hand side of Fig. 3.8 for an example. The
algorithm picks two arbitrary edge-disjoint paths from P v , accepts them, and rejects
all other paths from P v . We have a O contains two paths from P v ,
removing these two paths is sufficient to obtain a valid set O 0 , because they use the
same top edges as the paths accepted by the algorithm and O cannot contain any
further path intersecting the paths accepted by the algorithm.
In the following, let D be the set of paths in P v that intersect all other paths
from P v . In other words, a path p 2 P v is in D if P v does not contain a path q that is
edge-disjoint from p. Note that if Case 1.2.5 (a) does not apply, it follows that either
the paths in P v n D using edge e 1 or those using edge e 2 must have more than one
Fig. 3.9. Case 1.2.5 (c): Configurations in which two groups of deferred paths can be created.
equivalence class of paths.
Case 1.2.5 (b). There is only one equivalence class C of paths in P v n D using
more than one equivalence class of paths in P v n D using edge e 2 and not
intersecting a path from C. See the right-hand side of Fig. 3.8. (The case with e 1
and e 2 exchanged is symmetrical. Furthermore, note that the case that there is only
one equivalence class C of paths in P v n D using edge e 1 and only one equivalence
class of paths in P v n D using edge e 2 and not intersecting a path from C satisfies
the condition of Case 1.2.5 (a).) The algorithm picks a path p from C arbitrarily,
accepts p, and makes the paths using edge e 2 and not intersecting p a group of deferred
paths with reserved edge e 2 . All other paths in P v are rejected. We have a
O contains two paths from P v , these paths must also use both top edges of p
and the newly reserved edge, and thus removing these two paths from O is sufficient
to obtain a valid set O 0 .
Case 1.2.5 (c). There is more than one equivalence class of paths in P v n D using
there is more than one equivalence class of paths in P v n D using edge e 2 ,
and Case 1.2.5 (a) does not apply. The algorithm makes the paths in P v n D using e 1
a group of deferred paths with reserved edge e 1 and the paths in P v n D using e 2 a
group of deferred paths with reserved edge e 2 . All other paths in P v are rejected. Note
that no matter which paths of smaller level are accepted by the algorithm later on,
there are still two paths, one in each of the two groups of newly deferred paths, that
are edge-disjoint from these paths of smaller level and from each other. (Otherwise,
Case 1.2.5 (a) would apply.) We have a 2. If O contains two paths
from P v , these paths use e 1 and e 2 as well, and removing these two paths from O
is sufficient to obtain a valid set O 0 , because O cannot contain any further path
intersecting a reserved edge of the newly deferred paths.
Case 1.2.6. There is one child of v that has an undetermined
path p in its subtree. Let P 0
denote the set of paths in P v that do not intersect p.
We begin by making some simple observations. First, P 0
v must not contain two edge-disjoint
paths. Hence, there must be an edge e incident to v that is shared by all
paths in P 0
v . Second, implies that the maximum number of edge-disjoint paths
in P v is at most two. So there must be two edges e 1 and e 2 incident to v such that
every path in P v uses at least one of these two edges.
Let the lca of the undetermined path be v 0 , and let c be the child of v whose
subtree contains the undetermined path (possibly
of v 0 such that the undetermined path uses the edges (v 1
a number of subcases regarding the number of equivalence classes in P 0
v .
Case 1.2.6 (a). P 0
v is empty. Let P 1 and P 2 denote the sets of paths in P v
that intersect p in the edge (v in the edge (v respectively. Note that
the algorithm accepts an arbitrary
path from P i if P i has only one equivalence class of paths and creates a new group
of deferred paths from P i otherwise. The undetermined path p is rejected. We have
EDGE-DISJOINT PATHS IN BIDIRECTED TREES 17
v'
v' v'
v"
v"
Fig. 3.10. Case 1.2.7: v has two children with undetermined paths in their subtrees.
2. If O contains two paths from P v [ U v , removing these two paths is
sufficient, because they block at least as many paths of smaller level as the newly
accepted paths or newly reserved edges.
Case 1.2.6 (b). P 0
v has one equivalence class of paths. The algorithm accepts
an arbitrary path from P 0
v and the undetermined path p. All other paths in P v are
rejected. We have a Assume that O contains two paths from P v [U v .
If O contains p, O must also contain a path from P 0
v , and it suffices to remove these
two paths from O to obtain a valid set O 0 . If O does not contain p but contains a
path from P 0
must also contain a path from P v that intersects p; these two paths
block at least three of the four top edges blocked by the algorithm, and it suffices to
remove these two paths and at most one path of smaller level. Finally, if O contains
neither p nor a path from P 0
must contain two paths from P v that intersect p in
different top edges and at least one of which intersects also a top edge of the paths in
suffices to remove at most three paths from O to obtain a valid set O 0 .
Case 1.2.6 (c). P 0
v has more than one equivalence class of paths. Let e be the
edge incident to v that is shared by all paths in P 0
v . The algorithm accepts the
undetermined path p and creates a new group of deferred paths from the paths in
. All other paths in P v are rejected. We have a 1. Assume that O
contains two paths from P v [ U v . If O contains p, O must also contain a path from
v , and it suffices to remove these two paths from O to obtain a valid set O 0 . If O
does not contain p but contains a path from P 0
must contain a path from P v that
intersects these two paths block at least two of the three top edges blocked by the
algorithm, and it suffices to remove these two paths and at most one path of smaller
level. Finally, if O contains neither p nor a path from P 0
must contain two paths
from P v that intersect p in different top edges; again, these two paths block at least
two of the three top edges blocked by the algorithm, and it suffices to remove at most
three paths from O to obtain a valid set O 0 .
Case 1.2.7. Two children of v have undetermined paths
in their subtrees. Denote the undetermined paths by p and q. See Fig. 3.10. As
every path in P v must intersect at least one undetermined path. In addition,
if there are two paths in P v that intersect one undetermined path in different top
edges, at least one of them must also intersect the other undetermined path. Let P 1
and P 2 denote the sets of paths in P v that intersect p and q, respectively. Note that
Case 1.2.7 (a). There are edge-disjoint paths p 1 and p 2 in P v such that p 1 intersects
p in a top edge e 1 but does not intersect q, and p 2 intersects q in a top edge
e 2 but does not intersect p, and such that e 1 and e 2 have different directions (i.e.,
one is directed towards the root, and the other is directed towards the leaves). The
algorithm makes p, q, p 1 and p 2 a group of 2-exclusive paths consisting of a pair of
independent groups of exclusive paths and rejects all other paths from P v . The edges
e 1 and e 2 are marked fixed. If O contains two paths from the new group of 2-exclusive
paths already, let O Otherwise, it is possible to replace paths in O by paths
from the new group of 2-exclusive paths to obtain O 0 . In any case, jO
Case 1.2.7 (b). If the condition for Case 1.2.7 (a) does not hold, the algorithm
accepts p and q and rejects all paths from P v . We have a
that O contains two paths from P v [ U v . If O contains p and q, it suffices to remove
these two paths. If O contains only one of p and q, say p, it must contain a path from
P v that intersects q, and these two paths block three of the four top edges blocked
by the algorithm. If O contains neither p nor q, it must contain two paths from P v .
If at least one of these two paths in O intersects both p and q, these two paths again
block at least three of the four top edges blocked by the algorithm. If both paths in
O intersect only one of p and q, it must be the case that one of them intersects p in
an edge e 1 and one of them intersects q in an edge e 2 . If e 1 and e 2 have the same
direction, O can contain at most one path of smaller level intersecting a path accepted
by the algorithm. If e 1 and e 2 have different directions, the condition of Case 1.2.7 (a)
applies.
Case 1.3. s - 3. The algorithm accepts the s paths and rejects all other paths
from this subtree is marked fixed anymore. As s is the
maximum number of edge-disjoint paths in can contain at most s
paths from P v [U v [X v . Furthermore, O can contain at most two paths from F using
the edges (v; p(v)) or (p(v); v), and these are the only two further paths in O that
could possibly be blocked by the s paths accepted by the algorithm. Hence, a valid
set O 0 can be obtained from O by deleting at most s paths. As s
the invariants are maintained.
Case 2. 2="g. In this case, the algorithm cannot try out all
possibilities of accepting or rejecting unresolved paths in polynomial time. Instead,
it calculates only four candidate sets of edge-disjoint paths from
chooses the largest of them.
For obtaining two of the four sets, we employ a method of removing paths from
an arbitrary set S of edge-disjoint paths in P v such that ' exclusive paths from
X v can be accepted in addition to the paths remaining in S. The resulting set of
edge-disjoint paths in S [X v has cardinality jSj where r is the number
of paths that were removed from S. The details of the method and a proof that
will be presented later in Lemma 3.1. With this tool we are ready
to describe the candidate sets S 1
be the subset of paths
in P v that do not intersect any undetermined path in U v .
1. Compute a maximum number s 1 of edge-disjoint paths in P 0
v . S 1 is obtained
by taking these paths, all k undetermined paths, and as many additional edge-disjoint
paths from X v as possible. We have
undetermined paths and at least m paths from groups of 2-exclusive paths in X v due
to Property (2E).
2. S 2 is obtained from S 1 by removing r of the s 1 paths in S
such that ' +2m exclusive paths can be accepted. S 2 contains ' +2m exclusive paths,
and according to Lemma 3.1 only r - m)=3 of the s 1 paths in S
were removed to obtain S 2 . As S 2 still contains the k undetermined paths, we have
In addition, we have jS
EDGE-DISJOINT PATHS IN BIDIRECTED TREES 19
because S 2 contains all k undetermined paths from U v and ' exclusive paths.
3. S 3 is obtained by first computing a maximum number s 3 of edge-disjoint
paths in P v and then adding as many edge-disjoint paths from X v [ U v as possible.
We have jS 3 j - s 3 +m, because S 3 contains at least m paths from groups of 2-exclusive
paths in X v due to Property (2E).
4. S 4 is obtained from S 3 by removing r of the s 3 paths in S 3 " P v from S 3 such
that '+2m exclusive paths can be accepted, in the same way as S 2 is obtained from S 1 .
according to Lemma 3.1, we have jS 4 j - m+(2=3)(s 3 +'+m).
The algorithm accepts the paths in that set S i with maximum cardinality and
rejects all other paths from P v [U v [X v . We have a
Note that a v - jS 2 j - maxf3; 2="g and that this implies 2 - "a v .
Let O be the number of paths from P v that are
contained in O v and that intersect at least one of the k undetermined paths. Observe
that O v can contain at most k \Gamma b 0 =2 undetermined paths from U v . Note that the
maximum number of edge-disjoint paths in P v is s 3 and that the maximum number
of edge-disjoint paths in P 0
v is s 1 . Using jO
and using jO
With this upper bound on jO v j and the lower bounds on the cardinalities of the
four sets S i , we can now prove that at least one of the sets S i satisfies jO
it suffices to remove at most jO paths from O in order
to obtain a valid set O 0 , this implies that the invariants are maintained. If
we have jO
the following cases.
Case 2.1. ff ? 3=2. If '
we have a v - jS 3
use (3.1) and a v - jS 4 j to bound
the ratio between jO
a v
a v
Case 2.2.
we have a v - jS 3
a
use (3.1) and a v - jS 2 j to bound the ratio between jO
a v
a v
20 T. ERLEBACH AND K. JANSEN
c
e
a d
Fig. 3.11. Set of edge-disjoint paths in Pv .
Case 2.3. ff - 4=3. From (3.1) we get jO 2m, and we have
a
We have shown that jO holds in all subcases of Case 2. To
complete the description of Case 2, we still have to explain the method for removing
paths from S 1 and S 3 in order to obtain S 2 and S 4 , respectively. The method takes
an arbitrary set S of edge-disjoint paths in P v and removes paths from S to obtain
a set S 0 such that every subtree with exclusive paths is touched by at most one path
in S 0 . The motivation for this is that S can cause all paths from a group of exclusive
paths to be blocked only if two paths from S intersect the corresponding subtree
(Property (E)). Similarly, if only one path from a group of 2-exclusive paths can be
accepted, S must contain two paths from P v that intersect the corresponding subtree
(Property (2E)).
The method proceeds as follows. Consider a graph G with the paths in S as its
vertices and an edge between two paths if they touch the same child of v. G has
maximum degree two and consists of a collection of chains and cycles. Note that
every edge of G corresponds to a child of v that is touched by two paths in S. We
are interested in the maximal parts of chains and cycles that consist entirely of edges
corresponding to children of v that are the roots of subtrees with exclusive paths.
There are the following possibilities for such parts:
(i) A cycle such that all paths on the cycle have both endpoints in a subtree
with exclusive paths.
(ii) A chain such that the paths at both ends have only one endpoint in a subtree
with exclusive paths, while the internal paths have both endpoints in subtrees with
exclusive paths.
(iii) A chain such that the path at one end has only one endpoint in a subtree
with exclusive paths, while all other paths have both endpoints in a subtree with
exclusive paths.
(iv) A chain such that all its paths have both endpoints in a subtree with exclusive
paths.
Note that every such maximal part of a cycle or chain has length (number of paths)
at least two, because it contains at least one edge. The method for removing paths
proceeds as follows. Cycles of even length and chains are handled by removing every
other path from S, starting with the second path for chains. Cycles of odd length are
handled by removing two consecutive paths in one place and every other path from
the rest of the cycle.
Consider the example depicted in Fig. 3.11. The node v has eight children, named
a to h, and six of them (c to h) are roots of subtrees with exclusive paths (indicated
EDGE-DISJOINT PATHS IN BIDIRECTED TREES 21
e-a
g-h
a-d
d-c
h-f
f-g
c-b
Fig. 3.12. Graph G representing the structure of the paths.
by an exclamation mark). A set S of edge-disjoint paths in P v is sketched. The graph
G obtained from this set is shown in Fig. 3.12, and the label of a vertex in G is u-w
if the corresponding path begins in the subtree rooted at u and ends in the subtree
rooted at w. With respect to (i)-(iv) above, G contains a cycle of type (i) with length
three (containing the paths f -g, g-h, and h-f) and a chain of type (ii) with length
three (containing the paths a-d, d-c, and c-b). According to the rules given above,
three paths would be removed from S: two paths, say f -g and g-h, from the cycle,
and the path d-c from the chain of length three.
It is easy to see that this process always ensures that in the end S contains, for
each subtree with exclusive paths, at most one path with an endpoint in that subtree.
Hence, due to Properties (E) and (2E), S can be filled up with edge-disjoint exclusive
paths until it contains all exclusive paths.
Lemma 3.1. Let v be a node with '+m children with exclusive paths. Let S ' P v
be a set of edge-disjoint paths. Let S 0 ' S be the set of paths obtained from S by
removing paths according to the method described above. Let
Proof. Let a be the number of cycles of type (i), and let a i , 1 - i - a, be
the length of the ith cycle. Denote the number of chains of type (ii) by b and their
lengths by b i , 1 - i - b. Denote the number of chains of type (iii) by c and their
lengths by c i , Denote the number of chains of type (iv) by d and their
lengths by d d. Note that a As the number of
paths contained in the union of all these chains and cycles is at most s, we have
P a
Furthermore, considering the number
of children with exclusive paths covered by each chain or cycle, we obtain
P a
in the latter inequality and adding up the two inequalities, we obtain
P a
Taking into account
that
P a
\Sigma a i\Upsilon
c and that da i =2e - (2=3)a i
for a i - 2, the lemma follows.
In the example displayed in Fig. 3.11, we had
sufficient to remove
3 .
3.5. Running-time of the algorithm. The running-time of our algorithm is
polynomial in the size of the input for fixed " ? 0, but exponential in 1=". Let a
bidirected tree E) with n nodes and a set P containing h directed paths in T
(each path specified by its endpoints) be given. For arbitrary " ? 0, we claim that
our approximation algorithm can be implemented to run in time
O
The details of the implementation as well as experimental results will be reported
in [9].
22 T. ERLEBACH AND K. JANSEN
Note that we can choose n) and still achieve running-time polynomial
in the size of the input. The resulting algorithm achieves approximation ratio
therefore, asymptotic approximation ratio 5=3. (If the optimal
solution contains many paths, n must also be large, and the approximation ratio gets
arbitrarily close to 5=3.)
4. Generalizations. There are several generalizations of MEDP. First, it is
meaningful to consider the weighted version of the problem, where each path has a
certain weight and the goal is to maximize the total weight of the accepted paths.
The weighted version of MEDP can still be solved optimally in polynomial time in
bidirected stars and spiders (by reduction to maximum-weight matching in a bipartite
graph) and in bidirected trees of bounded degree (by a minor modification of the
dynamic programming procedure given in x2).
Another generalization of MEDP is the MaxPC problem. For a given bidirected
tree set P of directed paths in T , and number W of colors, the maximum
path coloring (MaxPC) problem is to compute a subset P 0 ' P and a W -coloring of P 0 .
The goal is to maximize the cardinality of P 0 . The MaxPC problem is equivalent to
finding a maximum (induced) W -colorable subgraph in the conflict graph of the given
paths. Studying MaxPC is motivated by the admission control problem in all-optical
WDM (wavelength-division multiplexing) networks without wavelength converters:
every wavelength (color) can be used to establish a set of connections provided that the
paths corresponding to the connections are edge-disjoint, and the number of available
wavelengths is limited [5]. The weighted variant of MaxPC is interesting as well.
MaxPC and weighted MaxPC can both be solved optimally in polynomial time
for bidirected stars by using an algorithm for (the weighted version of) the capacitated
b-matching problem [15, pp. 257-259]. If the number W of colors and the maximum
degree of the bidirected tree are both bounded by constants, MaxPC and weighted
MaxPC can be solved optimally in polynomial time by dynamic programming (similar
to the procedure in x2). MaxPC is NP-hard for arbitrary W in bidirected binary trees
(because path coloring is NP-hard) and for bidirected trees of arbitrary
degree (because it is equivalent to MEDP in this case).
In order to obtain approximation algorithms for MaxPC with arbitrary number W
of colors, a technique due to Awerbuch et al. [1] can be employed. It allows reducing
the problem with W colors to MEDP with only a small increase in the approximation
ratio. The technique works for MaxPC in arbitrary graphs G; we discuss it here only
for trees. Let an instance of MaxPC be given by a bidirected tree
set P of paths in T , and a number W of colors. An approximation algorithm A for
arbitrary number W of colors is obtained from an approximation algorithm A 1 for
one color (i.e., for the maximum edge-disjoint paths problem) by running W copies
of A 1 , giving as input to the ith copy the bidirected tree T and the set of paths that
have not been accepted by the first copies of A 1 (see Fig. 4.1). The output of A
is the union of the W sets of paths output by the copies of A 1 , and the paths in the
ith set are assigned color i.
In [1] it is shown that the algorithm A obtained using this technique has approximation
ratio at most ae +1 if A 1 has approximation ratio ae, even if different colors are
associated with different network topologies. For identical networks, which we have
in our application, the approximation ratio achieved by A can even be bounded by
aeW which is smaller than 1=(1 \Gamma e \Gamma1=ae ) for all W . This bound is
mentioned in the journal version of [1] and can be viewed as an adaptation of a similar
result in [6]. It can be proved easily using the fact that if A has selected p k paths after
Algorithm A
Input: bidirected tree T , set P of paths, number W of colors
Output: disjoint subsets P 1 ,. ,P W of P (each P i is edge-disjoint)
begin
to W do
begin
Fig. 4.1. Reduction from many colors to one color.
running k copies of A 1 , there is still a set of at least (jP
among the remaining paths and the next copy of A 1 accepts at least a (1=ae)-fraction
of this number. The reduction works also for the weighted case.
Since we have an optimal algorithm for MEDP in bidirected trees of bounded
degree and (5=3 ")-approximation algorithms for MEDP in arbitrary bidirected
trees, we can employ the above technique and obtain approximation algorithms with
bidirected trees of bounded degree and with
ratio approximately 2:22 for MaxPC in arbitrary bidirected trees.

Acknowledgments

. The authors are grateful to Stefano Leonardi for pointing
out the reduction from MaxPC with arbitrary number of colors to MaxPC with one
color and to Adi Ros'en for informing them about the improved analysis for the ratio
obtained by this reduction in the case of identical networks for all colors and for
supplying a preliminary draft of the journal version of [1].



--R


Competitive non

Graphs and Hypergraphs
Special issue on Dense Wavelength Division Multiplexing Techniques for High Capacity and Multiple Access Communication Systems
Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms
Structure in approximation classes
Call scheduling in trees

Optimal wavelength routing on directed fiber trees
An optimal greedy algorithm for wavelength allocation in directed tree networks


Colouring paths in directed symmetric trees with applications to WDM routing



Efficient wavelength routing on directed fiber trees
Maximum bounded 3-dimensional matching is MAX SNP-complete
Approximation algorithms for disjoint paths problems

Approximating disjoint-path problems using greedy algorithms and packing integer programs

A note on optical routing on trees
Improved access to optical bandwidth in trees
Efficient access to optical bandwidth
Computational Complexity
Improved approximations for edge-disjoint paths
--TR

--CTR
Thomas Erlebach , Klaus Jansen, Implementation of approximation algorithms for weighted and unweighted edge-disjoint paths in bidirected trees, Journal of Experimental Algorithmics (JEA), 7, p.6, 2002
R. Sai Anand , Thomas Erlebach , Alexander Hall , Stamatis Stefanakos, Call control with k rejections, Journal of Computer and System Sciences, v.67 n.4, p.707-722, December
Thomas Erlebach , Klaus Jansen, Conversion of coloring algorithms into maximum weight independent set algorithms, Discrete Applied Mathematics, v.148 n.1, p.107-125,
approximation algorithms;bidirected trees;edge-disjoint paths