Matching Problems with Delta-Matroid Constraints

Kakimura, N. and Takamatsu, M.

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

Cite as: Kakimura, N. and Takamatsu, M. (2012). Matching Problems with Delta-Matroid Constraints . In Proc. Computing: The Australasian Theory Symposium (CATS 2012) Melbourne, Australia. CRPIT, 128. Mestre, J. Eds., ACS. 83-92

(from crpit.com) (local if available)