TY - JOUR
T1 - Packing non-zero A-paths via matroid matching
AU - Tanigawa, Shin ichi
AU - Yamaguchi, Yutaro
N1 - Funding Information:
The first author is supported by JSPS KAKENHI Grant Number 15K15942 . The second author was supported by JSPS Grant-in-Aid for JSPS Fellows (Grant Number 13J02522 ) during this work.
Publisher Copyright:
© 2016 Elsevier B.V.
PY - 2016
Y1 - 2016
N2 - A Γ-labeled graph is a directed graph G in which each edge is associated with an element of a group Γ by a label function ψ:E(G)→Γ. For a vertex subset A⊆V(G), a path (in the underlying undirected graph) is called an A-path if its start and end vertices belong to A and does not intersect A in between, and an A-path is called non-zero if the ordered product of the labels along the path is not equal to the identity of Γ. Chudnovsky et al. (2006) introduced the problem of packing non-zero A-paths and gave a min–max formula for characterizing the maximum number of vertex-disjoint non-zero A-paths. In this paper, we show that the problem of packing non-zero A-paths can be reduced to the matroid matching problem on a certain combinatorial matroid, and discuss how to derive the min–max formula based on Lovász’ idea of reducing Mader's S-paths problem to matroid matching.
AB - A Γ-labeled graph is a directed graph G in which each edge is associated with an element of a group Γ by a label function ψ:E(G)→Γ. For a vertex subset A⊆V(G), a path (in the underlying undirected graph) is called an A-path if its start and end vertices belong to A and does not intersect A in between, and an A-path is called non-zero if the ordered product of the labels along the path is not equal to the identity of Γ. Chudnovsky et al. (2006) introduced the problem of packing non-zero A-paths and gave a min–max formula for characterizing the maximum number of vertex-disjoint non-zero A-paths. In this paper, we show that the problem of packing non-zero A-paths can be reduced to the matroid matching problem on a certain combinatorial matroid, and discuss how to derive the min–max formula based on Lovász’ idea of reducing Mader's S-paths problem to matroid matching.
UR - http://www.scopus.com/inward/record.url?scp=84977675563&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84977675563&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2016.06.001
DO - 10.1016/j.dam.2016.06.001
M3 - Article
AN - SCOPUS:84977675563
SN - 0166-218X
VL - 214
SP - 169
EP - 178
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -