MATHEMATICAL ENGINEERINGTECHNICAL REPORTS

Shortest Disjoint Non-zero A-paths
via Weighted Matroid Matching

Yutaro YAMAGUCHI(Communicated by Satoru IWATA)METR 2015–20

June 2015

DEPARTMENT OF MATHEMATICAL INFORMATICSGRADUATE SCHOOL OF INFORMATION SCIENCE AND TECHNOLOGYTHE UNIVERSITY OF TOKYOBUNKYO-KU, TOKYO 113-8656, JAPANWWW page: http://www.keisu.t.u-tokyo.ac.jp/research/techrep/index.html

The METR technical reports are published as a means to ensure timely dissemination ofscholarly and technical work on a non-commercial basis. Copyright and all rights therein
are maintained by the authors or by other copyright holders, notwithstanding that they
have oﬀered their works here electronically. It is understood that all persons copying thisinformation will adhere to the terms and constraints invoked by each author’s copyright.
These works may not be reposted without the explicit permission of the copyright holder.

Shortest Disjoint Non-zero A-paths
via Weighted Matroid Matching
Yutaro Yamaguchi∗

Abstract
The problem of packing non-zero A-paths in group-labeled graphs was introduced by
Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour (2006), which commonly
generalizes several disjoint paths problems, e.g., Mader’s disjoint S-paths problem. Tanigawa and Yamaguchi (2013) showed a reduction of this problem to matroid matching, whichleads to alternative proofs for a min-max formula due to Chudnovsky et al. and its eﬃcientsolvability. In addition, Yamaguchi (2014) provided a reduction to linear matroid parity
under some condition for groups, which leads to faster algorithms than the ﬁrst one due toChudnovsky, Cunningham, and Geelen (2008). In this paper, we extend these reductions
to a weighted version, and present various cases that can be solved in polynomial time byweighted linear matroid parity algorithms thanks to Iwata (2013) and Pap (2013).

1

Introduction

1.1

Packing Non-zero A-paths

Let Γ be a group. A Γ-labeled graph is a directed graph G = (V, E) with each edge labeled by anelement of Γ, i.e., with a mapping ψG : E → Γ called a label function. The label of an undirected
walk W = (v0 , e1 , v1 , e2 , v2 , . . . , el , vl ) in G (i.e., vi ∈ V for each i = 0, 1, . . . , l and ei = vi−1 vi ∈E or ei = vi vi−1 ∈ E for each i = 1, 2, . . . , l) is deﬁned as ψG (W ) := ψG (el ) · · · ψG (e2 ) · ψG (e1 )if ei = vi−1 vi for every i, and otherwise by replacing the corresponding label ψG (ei ) with its
inverse ψG (ei )−1 for each i with ei = vi vi−1 . A walk is called balanced (or a zero walk) if its
label is the identity element 1Γ of Γ, and unbalanced (or a non-zero walk) otherwise. For aprescribed terminal set A ⊆ V , an A-path is a path (a walk intersecting each vertex at mostonce) that starts and ends in A and does not intersect A in between.
The problem of packing non-zero A-paths, introduced by Chudnovsky et al. [4], is to ﬁnd a
maximum number of vertex-disjoint non-zero A-paths in a given Γ-labeled graph. It generalizes
Mader’s disjoint S-paths problem [14] (see [17, Chapter 73]) and packing odd-length A-paths,
depending on the choice of the group Γ (see [4, Section 2]). For this problem, a min-max formulaand a polynomial-time algorithm were given by Chudnovsky et al. [4] and Chudnovsky et al. [3],respectively.
In this paper, we deal with a weighted version of this problem: to minimize the total lengthof a designated number of vertex-disjoint non-zero A-paths for a given edge length.
Problem 1 (Shortest Disjoint Non-zero A-paths).
Input A Γ-labeled graph G = (V, E), a terminal set A ⊆ V , a nonnegative edge length ℓ ∈ RE
≥0 ,and a positive integer k.
Find A family P of vertex-disjoint non-zero A-paths in G such that |P| = k and the total
length ℓ(E(P)) of the edges used in P is minimized.
∗

Department of Mathematical Informatics, University of Tokyo, Tokyo 113-8658, Japan. Supported by JSPS
Fellowship for Young Scientists. Email: yutaro yamaguchi@mist.i.u-tokyo.ac.jp1Even for such a weighted version of Mader’s disjoint S-paths problem, any polynomialtime algorithm was not known, while Karzanov [9] had shown one for a similar problem in theedge-disjoint A-paths setting (which is a special case of Mader’s setting), whose full proof had
been left to an unpublished paper [8]. Karzanov’s problem can be solved by ﬁnding shortestk vertex-disjoint S-paths for possible k, where the number of iterations is at most |A|/2 andcan be reduced to O(log |A|) by binary search. It should be remarked that Hirai and Pap [6]discussed a generalization of Karzanov’s setting, in which each pair of two terminals has weight.

1.2

Matroid Matching

The matroid matching problem introduced by Lawler [11] commonly generalizes the matroidintersection problem and the non-bipartite matching problem. This problem cannot be solvedin polynomial time in general, but is known to be eﬃciently solvable as well as to admit a goodcharacterization when the matroid in question is linearly represented (or in a more generalsituation) due to Lovász [12, 13].
We here describe the problem setting. A pair of a ﬁnite set S and an integer-valued set
function f : 2S → Z is called a 2-polymatroid if(1) f (∅) = 0,
(2) f (X) ≤ f (Y ) for each X ⊆ Y ⊆ S,(3) f (X) + f (Y ) ≥ f (X ∪ Y ) + f (X ∩ Y ) for each X, Y ⊆ S, and(4) f ({e}) ≤ 2 for each e ∈ S.
A subset X ⊆ S is called a matching in a 2-polymatroid (S, f ) if f (X) = 2|X|, and a base if
f (X) = 2|X| = f (S).
The matroid matching problem is to ﬁnd a maximum matching in a given 2-polymatroid.
In this paper, we utilize a weighted version: to minimize the total weight of a base.
Problem 2 (Weighted Matroid Matching).
Input A 2-polymatroid (S, f ) and a weight vector w ∈ RS .
Find A base X ⊆ S in (S, f ) such that the total weight w(X) is minimized.
A 2-polymatroid (S, f ) is said to be linearly represented over a ﬁeld F if we have a matrix
Z = (Ze )e∈S ∈ Fd×2S obtained by concatenating d × 2 matrices Ze ∈ Fd×2 (e ∈ S) such thatf (X) = rank Z(X) for every X ⊆ S, where d is a positive integer and Z(X) = (Ze )e∈X denotes
the submatrix of Z obtained by selecting the corresponding columns. A subset X ⊆ S is calleda parity base for Z if rank Z(X) = 2|X| = rank Z.
In the linearly represented case, the matroid matching problem is called the linear matroid
parity problem, for which various polynomial-time algorithms have been proposed, e.g., by
Gabow and Stallmann [5], Orlin [15], and Cheung et al. [2]. As announced by Iwata [7] andPap [16], the following weighted version is also solved in polynomial time.
Problem 3 (Weighted Linear Matroid Parity).
Input A ﬁnite set S, a matrix Z ∈ Fd×2S over a ﬁeld F, and a weight vector w ∈ RS .
Find A parity base X ⊆ S for Z such that the total weight w(X) is minimized.

1.3

Results

With the aid of a generalized frame matroid, Tanigawa and the author [18] showed a reduction of
the problem of packing non-zero A-paths to the matroid matching problem, which also implies
the min-max formula [4] and the polynomial-time solvability [3]. In addition, the author [19]clariﬁed a neccesary and suﬃcient condition for the groups in question to admit a natural, more
direct reduction to the linear matroid parity problem, which leads to much faster algorithms.
2

Using a trick shown in the next section, the following theorem can be derived from a reduction of packing non-zero A-paths to matroid matching due to Tanigawa and the author [18].
Theorem 1. Shortest Disjoint Non-zero A-paths reduces to Weighted Matroid Matching.
In the same way, the next theorem can be obtained from a more direct reduction to linear
matroid parity due to the author [19]. Deﬁne PGL(n, F) := GL(n, F)/⟨In ⟩, where GL(n, F)
denotes the general linear group of degree n over a ﬁeld F (i.e., the set of all nonsingular n × nmatrices over F with the ordinary multiplication), In ∈ GL(n, F) the n × n identity matrix,and ⟨y⟩ the 1-dimensional subspace of a linear space Λ spanned by a vector y ∈ Λ \ {0} (i.e.,⟨y⟩ = { ky | k ∈ F } when Λ is a linear space over a ﬁeld F).
Theorem 2. Letbe a)⟩group and F a ﬁeld. If there exists a homomorphism ρ : Γ → PGL(2, F)( ) Γ ⟨(
such that ρ(α) 10 ̸∈ 10 for every α ∈ Γ \ {1Γ }, then Shortest Disjoint Non-zero A-pathsin Γ-labeled graphs reduces to Weighted Linear Matroid Parity over F.
Thanks to Iwata [7] and Pap [16], Theorem 2 leads to the ﬁrst polynomial-time algorithm
for the weighted version of Mader’s disjoint S-paths problem (see Section 3.1). In Section 3,
we present other solvable cases, and it is still open whether Shortest Disjoint Non-zero Apaths (as well as Weighted Matroid Matching derived from it by Theorem 1) is eﬃciently
solvable or not.

2

Proofs2.1

Construction of Auxiliary GraphFirst we construct a common auxiliary Γ-labeled graph from a given Γ-labeled graph G = (V, E)
with terminal set A ⊆ V . We may assume that |A| ≥ 2k, since otherwise there cannot be afeasible solution.
The construction is summarized as follows. Add |A| − 2k extra terminals so that each extra
terminal is adjacent to every original terminal by an edge with an arbitrary non-zero label.
Besides, add two other extra terminals b1 , b2 so that there is an edge from b1 to b2 with a
non-zero label and b1 is adjacent to all original non-terminal vertices.
Formally, for the vertex set, let ai (i = 1, 2, . . . , |A|−2k) and bj (j = 1, 2) be distinct vertices
not in V , and deﬁne A1 := { ai | i = 1, 2, . . . , |A| − 2k }, A2 := {b1 , b2 }, V ′ := V ∪ A1 ∪ A2 ,and A′ := A ∪ A1 ∪ A2 . Next, for the edge set, let E1 := { eit = ai t | ai ∈ A1 , t ∈ A },E2 := { ev = b1 v | v ∈ V \ A }, and E ′ := E ∪ E1 ∪ E2 ∪ {e′ = b1 b2 }. Finally, for the label
function of G′ := (V ′ , E ′ ), extend ψG : E → Γ to ψG′ : E ′ → Γ as follows: for each edge e ∈ E ′ ,{ψG (e) (e ∈ E),
ψG′ (e) :=α(e ∈ E ′ \ E),where 1Γ ̸= α ∈ Γ.

2.2

Proof of Theorem 1

For the resulting graph G′ = (V ′ , E ′ ) with terminal set A′ ⊆ V ′ , consider the 2-polymatroid′
constructed in [18], whose ground set is the edge set E ′ . Deﬁne a weight vector w ∈ RE as
follows: for each e ∈ E ′ ,{ℓe (e ∈ E),
we :=
(1)
0 (e ∈ E ′ \ E).
Note that to minimize the total weight makes incentive to take edges in E ′ \ E rather than inE, since ℓe ≥ 0 for every e ∈ E.
3

We omit the construction procedure of the 2-polymatroid correspinding to G′ (see [18]), andonly show its properties as follows. We denote the 2-polymatroid by (E ′ , f ), and by C(F ) the
family of maximal connected subsets of an edge set F ⊆ E ′ .
Claim 3 (From Tanigawa–Yamaguchi [18, Lemma 3.1]).
f (E ′ ) = 2|V ′ | − |A′ | = 2(|V | − k + 1).
Claim 4 (Tanigawa–Yamaguchi [18, Lemma 3.2]). An edge set F ⊆ E ′ satisﬁes f (F ) = 2|F |if and only if• F contains no cycle, and• for each F ′ ∈ C(F ), we have |V (F ′ ) ∩ A′ | ≤ 2 and the A′ -path between the two terminals
is non-zero if |V (F ′ ) ∩ A′ | = 2.
Suppose that G contains k vertex-disjoint non-zero A-paths. By extending the edge set ofsuch paths using edges in E1 ∪ E2 ∪ {e′ }, we can obtain a spanning forest F ⊆ E ′ such that
|V (F ′ ) ∩ A′ | = 2 and the A′ -path between the two terminals is non-zero for each F ′ ∈ C(F ),since each unused terminal can be connected to an extra terminal in A1 by an edge in E1 (andvice versa), each unused non-terminal can be connected to the extra terminal b1 ∈ A2 by anedge in E2 , and b1 , b2 ∈ A2 are adjacent by a non-zero edge e′ . Then, the number of connectedcomponents of G′ [F ] is k + (|A| − 2k) + 1 = |A| − k + 1, and hence, by Claims 3 and 4, we have()
f (F ) = 2|F | = 2 |V ′ | − (|A| − k + 1) = 2(|V | − k + 1) = f (E ′ ),which means that F is a base in (E ′ , f ). Therefore, for each family P of k vertex-disjoint nonzero A-paths in G, there exists a base FP in (E ′ , f ) with w(FP ) = ℓ(E(P)) (recall the deﬁnition′(1) of the weight w ∈ RE ).
To the contrary, for each base F in (E ′ , f ), there exists a family PF of k vertex-disjoint
non-zero A-paths in G with E(PF ) ⊆ F (hence, we have ℓ(E(PF )) ≤ w(F )) as follows. Thus
we have done, i.e., shortest k vertex-disjoint non-zero A-paths in G can be obtained by ﬁndinga minimum-weight base in (E ′ , f ).
Claim 5. For a base F in (E ′ , f ), the subgraph G′ [F ] is a spanning forest with |A| − k + 1
connected components, each of which contains exactly one non-zero A′ -path.
Proof. By the ﬁrst condition in Claim 4, F contains no cycle. Since |A′ | = |A| + (|A| − 2k) + 2 =2(|A|−k +1) and each F ′ ∈ C(F ) intersects at most two terminals in A′ by the second conditionin Claim 4, there are at least |A| − k + 1 connected components in G′ [F ]. Hence, we have
|F | ≤ |V ′ | − (|A| − k + 1) = |V | − k + 1.

(2)

Recall that 2|F | = f (F ) = f (E ′ ) = 2(|V | − k + 1) by Claim 3, which implies that the equality
holds in (2). This means that G′ [F ] has exactly |A|−k +1 connected components, each of whichcontains exactly two terminals in A′ and the A′ -path between the two terminals is non-zero by
the second condition in Claim 4. Then, F is obviously spanning.
Claim 6. For a base F in (E ′ , f ), the subgraph G[F ∩ E] contains k vertex-disjoint non-zeroA-paths in G.
Proof. By Claim 5, there are |A| − k + 1 connected components in G′ [F ] each of which contains
exactly one non-zero A-paths. Since there is only one edge e′ = b1 b2 ∈ E ′ incident to the extra
terminal b2 ∈ A2 , the connected component containing b2 must contain b1 ∈ A2 . Besides, sinceeach edge in E ′ incident to each extra terminal ai ∈ A1 ends an original terminal in A, theconnected component containing ai must contain some original terminal in A. The numberof such connected components is |A1 | = |A| − 2k, and hence the number of the connectedcomponents containing non-zero A-paths in G is |A| − k + 1 − (|A| − 2k + 1) = k.
4

2.3

Proof of Theorem 2

For the Γ-labeled graph G′ = (V ′ , E ′ ) with terminal set A′ ⊆ V ′ constructedin Section 2.1,⟨( )⟩consider the matrix constructed in [19] with a 1-dimensional subspace Y = 10 ⊆ F2 , whose′
column set is associated with the edge set E ′ . Deﬁne a weight vector w ∈ RE in the same way
as the previous section (see (1)).
′′
Formally, let us construct a matrix Z ∈ F2V ×2E as follows, where Zv,e ∈ F2×2 denotes the′′
2×2 submatrix of Z corresponding
vertex(1to) a ⟨()⟩ v ∈ V and an edge e ∈ E . Fix a homomorphism′1ρ : Γ → PGL(2, F) such that ρ(α) 0 ̸∈ 0 for every α ∈ Γ \ {1Γ }. For each edge e = uv ∈ E
and each vertex w ∈ V ′ , deﬁne(w = u),I2′
Zw,e := −ρ(ψG′ (e)) (w = v),O2(w ∈ V ′ \ {u, v}),
where O2 ∈ F2×2 denotes the 2 × 2 zero matrix. Next, for each non-terminal vertex v ∈ V ′ \ A′
′ . Finally, for each terminal t ∈ A′ and each edge e ∈ E ′ ,and each edge e ∈ E ′ , let Zv,e := Zv,e()
′ by eliminating the ﬁrst row using the vector 1 ∈ Y ,let Zt,e be the matrix obtained from Zt,e0i.e., replacing each entry in the ﬁrst row with 0.
′′Then, the following claim holds for the resulting matrix Z ∈ F2V ×2E . Recall that C(F )denotes the family of maximal connected subsets of an edge set F ⊆ E ′ .
Claim 7 (Yamaguchi [19, Lemmas 3.2 and 3.3]). An edge set F ⊆ E ′ satisﬁes rank Z(F ) = 2|F |if each F ′ ∈ C(F ) satisﬁes the following condition (b) or (c), and only if (a), (b), or (c):(a) |V (F ′ ) ∩ A′ | = 0 and G′ [F ′ ] contains exactly one non-zero cycle;(b) |V (F ′ ) ∩ A′ | ≤ 1 and G′ [F ′ ] contains no cycle;(c) |V (F ′ ) ∩ A′ | = 2, G′ [F ′ ] contains no cycle, and the A′ -path between the two terminals is
non-zero.
This claim implies the following claim.
Claim 8. An edge set F ⊆ E ′ is a parity base for Z if F is spanning in G′ with each F ′ ∈ C(F )satisfying Condition (c) in Claim 7, and only if F is spanning in G′ with (a) or (c).
Proof. By the construction of Z, we haverank Z ≤ 2|V ′ | − |A′ | = 2(|V | − k + 1).
Suppose that G contains k vertex-disjoint non-zero A-paths. By extending the edge set of suchpaths using edges in E1 ∪E2 ∪{e′ }, we can obtain a spanning forest F ⊆ E ′ with each F ′ ∈ C(F )satisfying Condition (c) (cf. the argument just after Claim 4). Since the number of connectedcomponents of G′ [F ] is k + (|A| − 2k) + 1 = |A| − k + 1, by the “if” part of Claim 7, we have()
rank Z(F ) = 2|F | = 2 |V ′ | − (|A| − k + 1) = 2(|V | − k + 1) ≥ rank Z ≥ rank Z(F ).
Hence, rank Z = 2(|V | − k + 1), and the “if” part follows from Claim 7.
The converse direction is also derived from Claim 7. Note that, for a parity base F ⊆ E ′ forZ, there are at most |A| − k + 1 connected components in G′ [F ] that contain no cycle becauseof the rank, and hence there cannot be a connected component of type (b).
By the same discussion as that between Claims 4 and 5 in Section 2.2, shortest k vertexdisjoint non-zero A-paths in G can be obtained by ﬁnding a minimum-weight parity base forZ. Note again that, we have incentive to take extra edges in E ′ \ E rather than original edgesin E because of the deﬁnition (1) of the weight w, and hence the total length of any connectedcomponent of type (a) in Claim 7 in a minimum-wight parity base for Z is 0.
5

3

Applications

In this section, we present various cases to which Theorem 2 is applicable. Then, Shortest Disjoint Non-zero A-paths can be solved in polynomial time via Weighted Linear
Matroid Parity with the aid of Iwata [7] and Pap [16]. We also refer the readers to [19, Section 5] for further explanation for the following examples.

3.1

Infinite Cyclic Group Z (Including Mader’s S-paths)

For the inﬁnite cyclic group Z, there exists a desired homomorphism ρ : Z → PGL(2, Q) deﬁned
as follows:()
1 0
ρ(i) :=(i ∈ Z).
i 1
It should be remarked that the weighted version of Mader’s disjoint S-paths can be formulated as Shortest Disjoint Non-zero A-paths in Z-labeled graphs, and hence it can besolved via Weighted Linear Matroid Parity. We again emphasize that this is the ﬁrst
polynomial-time algorithm for this problem.

3.2

Finite Cyclic Groups Zn (Including Odd-length A-paths)

For a ﬁnite cyclic group Zn = Z/nZ (n ≥ 2), there exists a desired homomorphism ρ : Zn →PGL(2, R) deﬁned as follows:

iπ 
iπ
− sin
cos

n
n  (i ∈ Z ).
ρ(i) := 

n
iπ
iπ
cos
sin
n
n
It should be remarked that the problem of shortest disjoint odd-length A-paths can beformulated as Shortest Disjoint Non-zero A-paths in Z2 -labeled graphs, and hence it canbe solved via Weighted Linear Matroid Parity. In the case of Z2 = {0, 1}, there exists a
simpler representation ρ′ over an arbitrary ﬁeld such that
(
)
(
)
1 0
0 1
′
′
ρ (0) =, ρ (1) =
.
0 1
1 0

3.3

Finitely Generated Abelian Groups

Suppose that k = 1 and a ﬁnitely generated abelian group Γ is given as decomposed into p
cyclic groups (cf. the fundamental theorem of ﬁnitely generated abelian groups). In this case,because of the above two examples, one can solve Shortest Disjoint Non-zero A-paths bysolving Weighted Linear Matroid Parity repeatedly p times.
While Kobayashi and Toyooka [10] gave an algebraic algorithm for the case when k = 1 andΓ is a ﬁxed ﬁnite abelian group inspired by the work of Björklund and Husfeldt [1], our result
provides a combinatorial solution to a more general case.

3.4

Dihedral Groups Dn

Even when Γ is non-abelian, there exists a solvable case. For the dihedral group Dn of degreen ≥ 3, i.e., Dn = ⟨ r, R | rn = R2 = id, rR = Rrn−1 ⟩, there exists a desired homomorphism
ρ : Dn → PGL(2, R) deﬁned as follows:

j
π
π
iπ
iπ  
cos
sin
cos
− sin

n+1
n+1 
n
n 
ρ(ri Rj ) := 
(0 ≤ i ≤ n − 1, j ∈ {0, 1}).

π
π 
iπ
iπ
sin
−
cos
cos
sin
n+1
n+1
n
n
6

References[1] A. Björklund, T. Husfeldt: Shortest two disjoint paths in polynomial time. Proceedings of the 41st International Colloquium on Automata, Languages, and Programming(ICALP 2014), pp. 211–222, 2014.
[2] H. Y. Cheung, L. C. Lau, K. M. Leung: Algebraic algorithm for linear matroid parity problem. Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms(SODA 2011), pp. 1366–1382, 2011.
[3] M. Chudnovsky, W. H. Cunningham, J. Geelen: An algorithm for packing non-zero Apaths in group-labelled graphs. Combinatorica, 28 (2008), pp. 145–161.
[4] M. Chudnovsky, J. Geelen, B. Gerards, L. Goddyn, M. Lohman, P. Seymour: Packing
non-zero A-paths in group-labelled graphs. Combinatorica, 26 (2006), pp. 521–532.
[5] H. N. Gabow, M. Stallmann: An augmenting path algorithm for linear matroid parity.
Combinatorica, 6 (1986), pp. 123–150.
[6] H. Hirai, G. Pap: Tree metrics and edge-disjoint S-paths. Mathematical Programming,
147 (2014), pp. 81–123.
[7] S. Iwata: A weighted linear matroid parity algorithm. Proceedings of the 8th JapaneseHungarian Symposium on Discrete Mathematics and Its Applications, pp. 251–259, 2013.
[8] A. V. Karzanov: Edge-disjoint T -paths of minimum total cost. Technical Report, STANCS-92-1465, Department of Computer Science, Stanford University, 1993.
[9] A. V. Karzanov: Multiﬂows and disjoint paths of minimum total cost. Mathematical
Programming, 78 (1997), pp. 219–242.
[10] Y. Kobayashi, S. Toyooka: Finding a shortest non-zero path in group-labeled graphs.
Mathematical Engineering Technical Reports, METR 2015-19, University of Tokyo, 2015.
[11] E. L. Lawler: Combinatorial Optimization: Networks and Matroids, Holt, Rinehart andWinston, 1976.
[12] L. Lovász: Matroid matching and some applications. Journal of Combinatorial Theory,
Ser. B, 28 (1980), pp. 208–236.
[13] L. Lovász: The matroid matching problem. Colloquia Mathematica Societatis János Bolyai,
25 (1981), pp. 495–517.
[14] W. Mader: Über die Maximalzahl krezungsfreier H-Wege. Archiv der Mathematik, 31(1978), pp. 387–402.
[15] J. B. Orlin: A fast, simpler algorithm for the matroid parity problem. Proceedings of the
13th Conference on Integer Programming and Combinatorial Optimization (IPCO 2008),
pp. 240–258, 2008.
[16] G. Pap: Weighted linear matroid matching. Proceedings of the 8th Japanese-Hungarian
Symposium on Discrete Mathematics and Its Applications, pp. 411–413, 2013.
[17] A. Schrijver: Combinatorial Optimization — Polyhedral and Eﬃciency, Springer-Verlag,
2003.
[18] S. Tanigawa, Y. Yamaguchi: Packing non-zero A-paths via matroid matching. Mathematical Engineering Technical Reports, METR 2013-08, University of Tokyo, 2013.
[19] Y. Yamaguchi: Packing A-paths in group-labelled graphs via linear matroid parity.
Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA 2014),
pp. 562–569, 2014.
7