TY - GEN
T1 - Matching problems with delta-matroid constraints
AU - Kakimura, Naonori
AU - Takamatsu, Mizuyo
PY - 2012
Y1 - 2012
N2 - Given an undirected graph G = (V, E) and a directed graph D = (V, A), the master/slave matching problem is to find a matching of maximum cardinality in G such that for each arc (u; v) ∈ A with u being matched, v is also matched. This problem is known to be NP-hard in general, but polynomially solvable in a special case where the maximum size of a connected component of D is at most two. This paper investigates the master/slave matching problem in terms of delta-matroids, which is a generalization of matroids. We first observe that the above polynomially solvable constraint can be interpreted as delta-matroids. We then introduce a new class of matching problem with delta-matroid constraints, which can be solved in polynomial time. In addition, we discuss our problem with additional constraints such as capacity constraints.
AB - Given an undirected graph G = (V, E) and a directed graph D = (V, A), the master/slave matching problem is to find a matching of maximum cardinality in G such that for each arc (u; v) ∈ A with u being matched, v is also matched. This problem is known to be NP-hard in general, but polynomially solvable in a special case where the maximum size of a connected component of D is at most two. This paper investigates the master/slave matching problem in terms of delta-matroids, which is a generalization of matroids. We first observe that the above polynomially solvable constraint can be interpreted as delta-matroids. We then introduce a new class of matching problem with delta-matroid constraints, which can be solved in polynomial time. In addition, we discuss our problem with additional constraints such as capacity constraints.
KW - Constrained matching
KW - Delta-matroid
KW - Mixed matrix theory
KW - Polynomial-time algorithm
UR - http://www.scopus.com/inward/record.url?scp=84863993737&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84863993737&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84863993737
SN - 9781921770098
T3 - Conferences in Research and Practice in Information Technology Series
SP - 83
EP - 92
BT - Theory of Computing 2012 - Proceedings of the Eighteenth Computing
T2 - Theory of Computing 2012 - 18th Computing: The Australasian Theory Symposium, CATS 2012
Y2 - 31 January 2012 through 3 February 2012
ER -