TY - GEN

T1 - Packing A-paths in group-labelled graphs via linear matroid parity

AU - Yamaguchi, Yutaro

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2014

Y1 - 2014

N2 - Mader's disjoint 5-paths problem is a common generalization of non-bipartite matching and Menger's disjoint paths problems. Lovasz (1980) suggested 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 (2003), which leads to faster algorithms. As a generalization of Mader's problem, Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour (2006) introduced a framework of packing non-zero A-paths in group-labelled graphs, and proved a min-max theorem. Chudnovsky, Cunningham, and Geelen (2008) provided an efficient combinatorial algorithm for this generalized problem. On the other hand, Pap (2007) introduced a framework of packing non-returning A-paths as a further genaralization. In this paper, we discuss a possible extension of Schri- jver's reduction technique to another framework introduced by Pap (2006), under the name of the subgroup model, which apparently generalizes but in fact is equivalent to packing non-returning .A-paths. We provide a necessary and sufficient condition for the groups in question to admit a reduction to the linear matroid parity problem. As a consequence, we give faster algorithms for important special cases of packing non-zero A-paths such as odd-length .4-paths. In addition, it turns out that packing non-returning A-paths admits a reduction to the linear matroid parity problem, which leads to the quite efficient solvability, if and only if the size of the input label set is at most four.

AB - Mader's disjoint 5-paths problem is a common generalization of non-bipartite matching and Menger's disjoint paths problems. Lovasz (1980) suggested 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 (2003), which leads to faster algorithms. As a generalization of Mader's problem, Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour (2006) introduced a framework of packing non-zero A-paths in group-labelled graphs, and proved a min-max theorem. Chudnovsky, Cunningham, and Geelen (2008) provided an efficient combinatorial algorithm for this generalized problem. On the other hand, Pap (2007) introduced a framework of packing non-returning A-paths as a further genaralization. In this paper, we discuss a possible extension of Schri- jver's reduction technique to another framework introduced by Pap (2006), under the name of the subgroup model, which apparently generalizes but in fact is equivalent to packing non-returning .A-paths. We provide a necessary and sufficient condition for the groups in question to admit a reduction to the linear matroid parity problem. As a consequence, we give faster algorithms for important special cases of packing non-zero A-paths such as odd-length .4-paths. In addition, it turns out that packing non-returning A-paths admits a reduction to the linear matroid parity problem, which leads to the quite efficient solvability, if and only if the size of the input label set is at most four.

UR - http://www.scopus.com/inward/record.url?scp=84902094567&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902094567&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973402.42

DO - 10.1137/1.9781611973402.42

M3 - Conference contribution

AN - SCOPUS:84902094567

SN - 9781611973389

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 562

EP - 569

BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

PB - Association for Computing Machinery

T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

Y2 - 5 January 2014 through 7 January 2014

ER -