Packing a-paths in group-labelled graphs via linear matroid parity

Mader's disjoint S-paths problem is a common generalization of non-bipartite matching and Menger's disjoint paths problems. Lovász [J. Combin. Theory Ser. B, 28 (1980), pp. 208- 236]) proposed a polynomial-time algorithm for this problem through a reduction to matroid matching. A more direct reduction to the linear matroid parity problem was given later by Schrijver [Combinatorial Optimization: Polyhedra and Efficiency, Springer-Verlag, Berlin, 2003], which led to faster algorithms. As a generalization of Mader's problem, Chudnovsky et al. [Combinatorica, 26 (2006), pp. 521-532] introduced a framework of packing non-zero A-paths in group-labelled graphs and proved a min-max theorem. Chudnovsky, Cunningham, and Geelen [Combinatorica, 28 (2008), pp. 145-161] provided an efficient combinatorial algorithm for this generalized problem. On the other hand, Pap [Combinatorica, 27 (2007), pp. 247-251] introduced a framework of packing non-returning A-paths as a further generalization. In this paper, we discuss possible extensions of Schrijver's reduction technique and the algorithm of Chudnovsky, Cunningham, and Geelen [Combinatorica, 28 (2008), pp. 145-161] to another framework introduced by Pap [A Constructive Approach to Matching and Its Generalizations, Ph.D. thesis, Institute of Mathematics, Eötvös Loránd University, Budapest, Hungary, 2006], under the name of the subgroup model, which apparently generalizes but in fact is equivalent to packing nonreturning A-paths. Extracting combinatorial aspects of Schrijver's reduction, we introduce the concept of coherent representation and provide a necessary and sufficient condition for the groups in question to admit a reduction to the linear matroid parity problem with coherent representations. As a consequence, we give faster algorithms for important special cases of packing nonzero A-paths. In addition, it turns out that packing nonreturning A-paths admits such a reduction to the linear matroid parity problem if and only if the size of the input label set is at most four, which leads to its efficient solvability in this special case.