Discrete Mathematics 308 (2008) 1472–1488
Packing non-returning A-paths algorithmically
Department of Operations Research, Eötvös University, Pázmány P. s. 1/C, Budapest, H-1117 Hungary
Received 12 December 2005; received in revised form 2 October 2006; accepted 11 July 2007
Available online 29 August 2007
We construct a combinatorial algorithm to ﬁnd a maximum packing of fully node-disjoint non-returning A-paths.
© 2007 Elsevier B.V. All rights reserved.
Keywords: Disjoint paths; Matching
The path-packing problem considered in this paper is a common generalization of non-bipartite matching, node-
disjoint s–t paths, A-paths, and non-zero A-paths. Mader’s theorem  on fully node-disjoint A-paths is one of the most
general results in this area. Chudnovsky et al.  proved a slight generalization of Mader’s theorem, their result concerns
packing non-zero A-paths. For this result, the author  gave a short proof—in fact for a slightly stronger result on non-
returning A-paths. All these results are direct generalizations of the Berge–Tutte formula for non-bipartite matching.
Edmonds  constructed a polynomial time algorithm for non-bipartite matching, which uses an augmentation structure
called the alternating forest. A desired combinatorial algorithm for path-packing could be a direct generalization of
Edmonds’ matching algorithm. Such an algorithm is not known, the reason for this is probably that the alternating
forest structure is not easy to generalize to the framework of path-packing. Note that two other approaches have already
resulted in polynomial time algorithms for path-packing. First, Lovász  noticed that Mader’s path-packing problem
reduces to the general framework of matriod matching, and he made use of general results from that framework. Second,
Chudnovsky et al.  constructed another algorithm by setting up a long list of feasible path-packings in the search of
an augmentation. Their algorithmic proof also implies a structural decomposition, which generalizes the well-known
Edmonds–Gallai decomposition of non-bipartite matching (see [3,5]). Now, in this paper, we will propose another
algorithm for a slightly more general path-packing problem. Most operations of this algorithm are local manipulations
rather than a global augmentation structure. Our results also imply the so-called dragon-decomposition of criticals,
which is a generalization of the odd ear-decomposition of factor-critical graphs.
Research is supported by OTKA Grants T 037547 and TS 049788, by European MCRTN Adonet, Contract Grant no. 504438 and by the Egerváry
Research Group of the Hungarian Academy of Sciences.
E-mail address: firstname.lastname@example.org.
The author is a member of the Egerváry Research Group (EGRES).
0012-365X/$ - see front matter © 2007 Elsevier B.V. All rights reserved.