MATHEMATICAL ENGINEERINGTECHNICAL REPORTS

Matching Problems with
Delta-Matroid Constraints

Naonori KAKIMURA and Mizuyo TAKAMATSU

METR 2011–41

December 2011

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.

Matching Problems with Delta-Matroid Constraints∗
Naonori Kakimura†Mizuyo Takamatsu‡

December 2011

Abstract
Given an undirected graph G = (V, E) and a delta-matroid (V, F), the delta-matroid
matching problem is to ﬁnd a maximum cardinality matching M such that the set of theend vertices of M belongs to F. This problem is a natural generalization of the matroid
matching problem to delta-matroids, and thus it cannot be solved in polynomial time ingeneral.
This paper introduces a class of the delta-matroid matching problem, where the given
delta-matroid is a projection of a linear delta-matroid. We ﬁrst show that it can be solvedin polynomial time if the given linear delta-matroid is generic. This result enlarges apolynomially solvable class of matching problems with precedence constraints on vertices
such as the 2-master/slave matching. In addition, we design a polynomial-time algorithm
when the graph is bipartite and the delta-matroid is deﬁned on one vertex side. This resultis extended to the case where a linear matroid constraint is additionally imposed on theother vertex side.

Keywords: constrained matching, delta-matroid, polynomial-time algorithm, mixed matrix
theory1

Introduction

For an undirected graph G = (V, E), a subset M of E is called a matching if no two edges in
M share a common vertex incident to them. The matching problem is a fundamental topic
in combinatorial optimization, and many polynomial-time algorithms have been developed (seee.g., [25, 34]). When we apply the matching problem to practical problems such as scheduling,
it is often natural to have some additional constraints. In the literature, there are matchingproblems with a variety of constraints such as matroids [22], trees [9], precedence constraints [1,∗A preliminary version appears in Proceedings of the 18th CATS symposium (Computing: the Australasian
Theory Symposium) [24].
†Department of Mathematical Informatics, University of Tokyo, Tokyo 113-8656, Japan. Supported in partby Grant-in-Aid for Scientific Research and by Global COE Program “The research and training center for
new development in mathematics” from the Ministry of Education, Culture, Sports, Science and Technology ofJapan. E-mail: kakimura@mist.i.u-tokyo.ac.jp‡
Department of Information and System Engineering, Chuo University, Tokyo 112-8551, Japan. Supported by a Grant-in-Aid for Scientific Research from the Japan Society for Promotion of Science. E-mail:takamatsu@ise.chuo-u.ac.jp120], and knapsack constraints [2]. These constrained matching problems are known to be NPhard except for some cases with matroid constraints.
For an undirected graph G = (V, E) and a matroid M on V , the matroid matching problem
is a problem of ﬁnding a maximum cardinality matching M such that ∂M is independent in M,
where ∂M denotes the set of vertices incident to edges in M . This problem, which is equivalent
to the matroid parity problem [26], has been investigated in combinatorial optimization as acommon generalization of two well-known polynomially solvable problems: the matroid intersection problem and the matching problem. Although it is shown to be intractable in the oracle
model [23, 30] and NP-hard for matroids with compact representations [28], Lovász provided a
min-max formula [28] for the linear matroid matching problem, and a number of polynomialtime algorithms for the linear matroid matching have been developed [11, 15, 27, 29, 33]. On
the other hand, when the graph is bipartite and the matroid is deﬁned on each class of thevertex bipartition, the matroid matching problem can be solved in polynomial time for generalmatroids [22], because this is equivalent to the matroid intersection problem. This problem isalso known as the independent matching problem.
A delta-matroid was introduced by Bouchet [5] as a generalization of matroids, where essentially equivalent combinatorial structures are given independently by [10, 12]. We say thata pair (V, F) of a ﬁnite set V and a nonempty family F of subsets of V is a delta-matroid if itsatisﬁes the symmetric exchange axiom:(DM) For F, F ′ ∈ F and u ∈ F △F ′ , there exists v ∈ F △F ′ such that F △{u, v} ∈ F,
where I△J denotes the symmetric diﬀerence, i.e., I△J = (I \ J) ∪ (J \ I). A set F ∈ F is calledfeasible. A delta-matroid maintains matroidal properties in the sense that a greedy algorithm
is applicable to maximizing linear functions over a delta-matroid [5].
In this paper, we generalize the matroid matching problem in terms of delta-matroids. Thatis, for an undirected graph G = (V, E) and a delta-matroid (V, F), the delta-matroid matchingproblem is to ﬁnd a maximum cardinality matching M with ∂M ∈ F. Since this problem
includes the matroid matching problem, the delta-matroid matching problem cannot be solvedin polynomial time in general.
It should be noted that the feasibility problem for the delta-matroid matching, i.e., ﬁnding
a matching M such that ∂M is feasible, already generalizes the matroid matching problem.
The feasibility problem is reduced to the delta-covering problem, posed by Bouchet [7] as a
generalization of the matroid parity problem. For this problem, Geelen et al. [18] provided
a polynomial-time algorithm and a min-max theorem if a given delta-matroid is linear, i.e.,
represented by a skew-symmetric matrix. Thus, for linear delta-matroids, we can ﬁnd a feasibledelta-matroid matching in polynomial time. However, the complexity of the problem to ﬁnd a
maximum delta-matroid matching is still unknown for the linear case.
The main purpose of this paper is to investigate polynomial solvability of the delta-matroid
matching problem. We introduce a new class of the delta-matroid matching problem, where
the delta-matroid is given by a projection of a linear delta-matroid with a skew-symmetricmatrix. We call such problem the matching problem with a projected linear delta-matroid .
For this problem, we ﬁrst show that it can be solved in polynomial time if the given skewsymmetric matrix K is generic, that is, each entry in K is an independent parameter. This2

can be done by reducing it to the maximum weight matching problem. Let us remark that,
although we restrict a delta-matroid to a generic case, our class still includes a variety of
constrained matching problems, as presented in Section 3.2. In particular, our class includes
polynomially solvable classes of the master/slave matching [20] and its variant [1], arising in a
manpower scheduling problem.
In addition, we deal with a bipartite case of our problem. That is, we assume that a graph
G is bipartite and that the ground set of a delta-matroid is contained in one class of the vertex
bipartition. This problem generalizes the bipartite 2-master/slave matching [19], which is a
special case of the master/slave matching. In this setting we prove that the matching problem
with a projected linear delta-matroid can be solved in polynomial time. The proof makes
use of mixed matrix theory developed by Murota [32]. We further show that our result can beextended to the problem where a linear matroid constraint is additionally imposed on the othervertex side. Note that this problem can be viewed as an intersection problem, i.e., the problem
of ﬁnding a maximum cardinality set that is both feasible for a delta-matroid and independent
for a matroid.
The organization of this paper is as follows. In Section 2, we explain delta-matroid theory
and mixed matrix theory. In Section 3 we examine a projection of a linear delta-matroid
and provide a variety of examples representable by such delta-matroids. Section 4 presentsa polynomial-time algorithm for the generic delta-matroid matching problem. In Section 5,
we deal with the bipartite case and its generalization to the problem with additional linear
matroid constraint. Finally, Section 6 discusses related intersection problems on matroids anddelta-matroids.

2

Matrices and delta-matroids

2.1

Graphs and matrices

Let G = (V, E) be a graph with vertex set V and edge set E. For a subset F of E, we denoteby ∂F the set of vertices incident to edges in F . For a subset X of V , the induced subgraphon X is a graph G[X] = (X, E ′ ), where E ′ ⊆ E is the set of edges whose both end vertices
are included in X. For a bipartite graph G = (V + , V − ; E) with E ⊆ V + × V − , the induced
subgraph on I ⊆ V + and J ⊆ V − is denoted by G[I, J]. We also deﬁne ∂ + F = ∂F ∩ V + and∂ − F = ∂F ∩ V − for a subset F of E.
Throughout this paper, we consider a matrix over the real ﬁeld R1 unless otherwise speciﬁed.
For a matrix K = (Kij ) with row set R and column set C, K[I, J] denotes the submatrix withrow set I ⊆ R and column set J ⊆ C. For a square matrix K, we denote a principal submatrix
with row/column set I by K[I]. A matrix K is called skew-symmetric if Kij = −Kji for all(i, j) and all diagonal entries of K are zero. For a skew-symmetric matrix K = (Kij ) withrow/column set V such that |V | = 2n, the Pfaﬃan of K is deﬁned by∑
pf K =kP ,P
1

In fact, the results of this paper can be applied to a matrix over any ordered field F. That is, the real field
R and the rational field Q which appear in this paper may be replaced by an ordered field F and its subfield K.

3

where the summation is taken over all partitions P = {{i1 , j1 }, . . . , {in , jn }} of V into unorderedpairs and() n
1 2 · · · 2n − 1 2n ∏kP = sgn
Kil jl .
i1 j1 · · ·
in
jn
l=1

Then it holds that det K = (pf K)2 .
A generic matrix is a matrix in which each nonzero entry is an independent parameter.
More precisely, a matrix is generic if the set of nonzero entries is algebraically independent
over the rational ﬁeld Q. A skew-symmetric matrix K is called generic if {Kij | Kij ̸= 0, i < j}is algebraically independent over Q.
Let K be a generic skew-symmetric matrix with row/column set V . The support graphof K is the undirected graph H = (V, EH ) with EH = {(i, j) | Kij ̸= 0, i < j}. Note that anonzero term kP in the Pfaﬃan corresponds to a perfect matching in the support graph. Hencethe rank of a generic skew-symmetric matrix K is twice the size of a maximum matching in its
support graph H (see e.g., [31]). By applying this fact to each principal submatrix of K, we
obtain the following lemma.
Lemma 2.1. Let K be a generic skew-symmetric matrix with row/column set V , and H =(V, EH ) be its support graph. For a subset X ⊆ V , K[X] is nonsingular if and only if H[X]has a perfect matching.

2.2

Delta-matroids and greedy algorithms

We say that a pair (V, I) of a ﬁnite set V and a family I of subsets of V is a matroid if itsatisﬁes the following:(I-1) ∅ ∈ I,
(I-2) I ⊆ J ∈ I ⇒ I ∈ I,
(I-3) I, J ∈ I, |I| < |J| ⇒ I ∪ {v} ∈ I for some v ∈ J \ I.
A set I ∈ I is said to be independent, and a maximal independent set is a base.
Recall that a delta-matroid is a pair M = (V, F) of a ﬁnite set V and a nonempty family Fof subsets of V that satisﬁes the symmetric exchange axiom (DM). A delta-matroid generalizes
a matroid, since the family of independent sets of a matroid forms a delta-matroid. A deltamatroid (V, F) is said to be even if |F △ F ′ | is even for all F, F ′ ∈ F. A simple example of evendelta-matroids is the family of the subsets of even size. The base family of a matroid also forms
an even delta-matroid. Another example is the family of vertex sets X with X = ∂M for somematching M in a graph G, called the matching delta-matroid [6]. Let K be a skew-symmetricmatrix with row/column set V . We denote the family of column indices corresponding tononsingular principal submatrices by
F(K) = {X ⊆ V | rank K[X] = |X|}.
Then M(K) = (V, F(K)) forms an even delta-matroid, where the empty set is feasible [4].

4The twisting of a delta-matroid M = (V, F) by X ⊆ V is a delta-matroid deﬁned by
M△X = (V, F△X), whereF△X = {F △X | F ∈ F}.
A delta-matroid M′ is equivalent to M if M′ is a twisting of M by some X ⊆ V . A deltamatroid M is said to be linear if M is equivalent to M(K) for some skew-symmetric matrix
K. Since M(K) is an even delta-matroid, a linear delta-matroid is even. We call a linear
delta-matroid M generic if M is equivalent to M(K) for some generic skew-symmetric matrix
K. For X ⊆ V , the projection of a delta-matroid M on X is deﬁned by M|X = (V \ X, F|X),
where
F|X = {F \ X | F ∈ F}.
The projection M|X is also a delta-matroid. Note that projection does not necessarily preserve
evenness. The deletion of X from M is a delta-matroid M \ X = (V \ X, F \ X) with
F \ X = {F ∈ F | F ⊆ V \ X},where F \ X is assumed to be nonempty. The contraction of M by X is deﬁned as M/X =(M△X) \ X.
Given a delta-matroid M = (V, F) and a weight function c : V → R, consider the problem∑
to ﬁnd F ∈ F which maximizes c(F ) = v∈F c(v). For this problem, Bouchet [5] designed agreedy-type algorithm, and Shioura and Tanaka [35] extended the algorithm to one for jumpsystems [8], which is a generalization of delta-matroids to integral lattice. Their results imply
that the greedy algorithm ﬁnds an optimal solution in polynomial time under the assumptionthat a membership oracle for M, which checks whether or not a given set F is in F, is available.

2.3

Mixed skew-symmetric matrices and delta-covering

Mixed matrix theory, developed by Murota [32], is one of the most signiﬁcant applications ofdelta-matroid theory. In this section, we explain the concept of mixed skew-symmetric matrices,which will be used to analyze the bipartite delta-matroid matching problem in Section 5.
Let F be a ﬁeld and K be a subﬁeld of F. A typical example is K = Q and F = R. A
skew-symmetric matrix A is called a mixed skew-symmetric matrix if A is given by A = Q + T ,where(MS-Q) Q = (Qij ) is a skew-symmetric matrix over K (i.e., Qij ∈ K), and(MS-T) T = (Tij ) is a skew-symmetric matrix over F (i.e., Tij ∈ F) such that the set {Tij |Tij ̸= 0, i < j} of its nonzero entries in the upper-triangle part is algebraically independent
over K.
The problem of computing the rank of a mixed skew-symmetric matrix is discussed in[17, 18]. The rank is expressed by using delta-matroids.
Theorem 2.2 ([32, Theorem 7.3.22]). For a mixed skew-symmetric matrix A = Q + T withrow/column set V , it holds thatrank A = max{rank Q[I] + rank T [V \ I] | I ⊆ V }= max{|FQ △FT | | FQ ∈ F(Q), FT ∈ F (T )},5where M(Q) = (V, F(Q)) and M(T ) = (V, F(T )).
For a pair of delta-matroids (V, F1 ) and (V, F2 ), the delta-covering problem is the problem to
ﬁnd F1 ∈ F1 and F2 ∈ F2 maximizing |F1 △F2 |. This problem is a generalization of the matroid
parity problem, and contains the delta-matroid intersection problem and the delta-matroid
partition problem as special cases (see [32]). Since Geelen et al. [18] gave a polynomial-timealgorithm for the delta-covering problem for linear delta-matroids, it follows from Theorem 2.2
that the rank of a mixed skew-symmetric matrix A = Q + T can be computed in polynomial
time. This is rewritten as follows.
Corollary 2.3. Let A = Q + T be a mixed skew-symmetric matrix with row/column set V .
Then we can ﬁnd in polynomial time a maximum cardinality set X ⊆ V such that A[X] is
nonsingular. Moreover, we can obtain in polynomial time a set I ⊆ X such that both Q[I] andT [X \ I] are nonsingular.
We can also compute in polynomial time the weighted version of ﬁnding a nonsingularprincipal submatrix of A. More generally, we have the following.
Lemma 2.4. Let A = Q + T be a mixed skew-symmetric matrix with row/column set V .
For a weight function c : V → R and U ⊆ V , we can ﬁnd a set X ⊆ V which maximizes∑c(X) = v∈X c(v) subject to U ⊆ X and rank A[X] = |X| in polynomial time, if exists.
Proof. Since A is skew-symmetric, (V, F(A)) is a delta-matroid. We deﬁne a weight functionc̃ : V → R by{N(v ∈ U )c̃(v) =,
c(v) (v ∈ V \ U )where N is an integer larger than cmax |V | with cmax = maxv∈V c(v). Let X be a maximum
weight feasible set with respect to the delta-matroid (V, F(A)) with weight c̃, which can beobtained by the greedy algorithm. Then if c̃(X) < N |U | there exists no set Y ∈ F(A) withU ⊆ Y . If c̃(X) ≥ N |U | then X maximizes c(X) subject to U ⊆ X and rank A[X] = |X|.
In the greedy algorithm, it is necessary to determine whether a given set Y ⊆ V is in F(A)or not. This is equivalent to computing the rank of A[Y ], which can be done in polynomial
time by solving the linear delta-covering problem. Thus a membership oracle for (V, F(A))
is available, which implies that we can ﬁnd a maximum weight feasible set X in polynomial
time.

3

Matching problem with projected linear delta-matroids

Let K be a skew-symmetric matrix with row/column set VK , and V be a subset of VK . For asubset S of V , the pair (VK , F(K)△S) is a linear delta-matroid. We deﬁne
FK := (F(K)△S)|R,(1)

where R = VK \ V . Then (V, FK ) is a delta-matroid, which we call a projected linear deltamatroid .
6

V

V
+. .
Ld =

Ls =
V \X

.
+
+

X
0. .

.

W

0

Figure 1: A skew-symmetric matrix Ls and a diagonal matrix Ld .

We then discuss weighted non-bipartite matching problem with (V, FK ). That is, given agraph G = (V, E) with edge weight w : E → R+ , we aim at ﬁnding a matching M ⊆ E in G∑
which maximizes w(M ) = e∈M w(e) subject to ∂M ∈ FK .
We ﬁrst show in Section 3.1 that the family of nonsingular principal submatrices of askew-symmetric matrix with nonnegative diagonals can be represented as a projected linear
delta-matroid (1). This representation brings a variety of constrained matching problems into
our framework, which are provided in Section 3.2.

3.1

Skew-symmetric matrices with nonnegative diagonals

Let L be a skew-symmetric matrix with nonnegative diagonals, that is, L = Ls +Ld with a skewsymmetric matrix Ls and a nonnegative diagonal matrix Ld . We denote the row/column set of
L by V , and the row/column set of Ld corresponding to positive diagonals by W . A matrix L
over R is called generic if {Lij | Lij ̸= 0, i ≤ j} is algebraically independent over Q. For a skewsymmetric matrix L with nonnegative diagonals, deﬁne F(L) = {X ⊆ V | rank L[X] = |X|}.
The main purpose of this section is to prove that (V, F(L)△S) for S ⊆ V forms a projectionof a linear delta-matroid. We ﬁrst show the following lemma.
Lemma 3.1. Let L = Ls + Ld be a skew-symmetric matrix with nonnegative diagonals, andV be the row/column set of L. Then L is nonsingular if and only if there exists X ⊆ W suchthat Ls [V \ X] is nonsingular.
Proof. Since Ld is a diagonal matrix, we have∑det L =
det Ls [V \ X] · det Ld [X]
X⊆V

=

∑

det Ls [V \ X] · det Ld [X]

(2)

X⊆W

by the deﬁnition of W . Figure 1 shows submatrices Ls [V \ X] and Ld [X]. Since Ls [V \ X] isskew-symmetric, det Ls [V \ X] ≥ 0 holds. Moreover, we have det Ld [X] > 0 for X ⊆ W . Henceeach term of (2) is nonnegative. Thus, L is nonsingular if and only if there exists X ⊆ W suchthat Ls [V \ X] is nonsingular.
The copy of W is denoted by Wc . For X ⊆ W , Xc denotes a copy of X included in Wc .

7

We deﬁne a skew-symmetric matrix K in the form of
V \W
O
Ld [W ] O
K =  −Ld [W ]
.
Ls
O


Wc

W

(3)

The matrices L and K are related as follows.
Lemma 3.2. The following (i) and (ii) hold.
(i) For any X ⊆ Wc ∪ V such that K[X] is nonsingular, L[X \ Wc ] is nonsingular.
(ii) For any Y ⊆ V such that L[Y ] is nonsingular, there exists a subset Z ⊆ Wc such thatK[Z ∪ Y ] is nonsingular.
Proof. We ﬁrst prove (i). Let us denote X ∩Wc by Zc and its copy by Z ⊆ W . By the deﬁnitionof K, it holds thatdet K[X] = det K[Zc , Z] · det K[Z, Zc ] · det K[X \ (Z ∪ Zc )].

(4)

Since Ld [W ] is a diagonal matrix with positive entries, both det K[Zc , Z] and det K[Z, Zc ] arenonzero. By det K[X] ̸= 0, it holds that det K[X \ (Z ∪ Zc )] = det Ls [(X \ Wc ) \ Z] ̸= 0. Since
Z ⊆ X ∩ W , this implies by Lemma 3.1 that L[X \ Wc ] is nonsingular.
We next prove (ii). Since L[Y ] is nonsingular, Lemma 3.1 implies that there exists a subset
Z ⊆ W ∩ Y such that Ls [Y \ Z] is nonsingular. Letting X = Zc ∪ Y , we know that K[X] is
nonsingular from (4), which proves (ii).
Let us deﬁne FS (K) = F(K)△(S ∪ Wc ). Since K is a skew-symmetric matrix, (Wc ∪V, FS (K)) is a linear delta-matroid. Lemma 3.2 leads to the following theorem.
Theorem 3.3. Let L be a skew-symmetric matrix with nonnegative diagonals, V be therow/column set of L, and K be a skew-symmetric matrix deﬁned by (3). For a subset S of
V , the pair (V, F(L)△S) is a projection of the linear delta-matroid (Wc ∪ V, FS (K)) on Wc .
Moreover, if L is generic, then (Wc ∪ V, FS (K)) is a generic linear delta-matroid.
Proof. The projection of FS (K) on Wc is equal to
FS (K)|Wc = {F \ Wc | F ∈ FS (K)}
= {(X△(S ∪ Wc )) \ Wc | rank K[X] = |X|, X ⊆ Wc ∪ V }= {(X \ Wc )△S | rank K[X] = |X|, X ⊆ Wc ∪ V }.
If X ⊆ Wc ∪ V satisﬁes rank K[X] = |X|, then L[X \ Wc ] is nonsingular by (i) in Lemma 3.2.
This implies FS (K)|Wc ⊆ F(L)△S. Conversely, if Y ⊆ V satisﬁes rank L[Y ] = |Y |, it follows
from (ii) in Lemma 3.2 that there exists a subset Z ⊆ Wc such that K[Z ∪ Y ] is nonsingular.
Hence Y △S = ((Z ∪ Y ) \ Wc )△S ∈ FS (K)|Wc . Thus we obtain F(L)△S ⊆ FS (K)|Wc .
If L is generic, K deﬁned by (3) is a generic skew-symmetric matrix, which implies that
(Wc ∪ V, FS (K)) is a generic linear delta-matroid.
8

The following corollary immediately follows from Theorem 3.3, because a projection of adelta-matroid is also a delta-matroid. Note that the resulting delta-matroid is not necessarily
linear.
Corollary 3.4. Let L be a skew-symmetric matrix with nonnegative diagonals, and V be therow/column set of L. For a subset S ⊆ V , the pair (V, F(L)△S) is a delta-matroid.

3.2

Constrained matching problems with delta-matroids

In this section, we provide a variety of constrained matching problems that are included in thematching problem with a projected linear delta-matroid. We ﬁrst remark that the identity matrix is a skew-symmetric matrix with nonnegative diagonals, which represents free constraints,
and hence the standard matching problem is contained in our problem by Theorem 3.3.
Example 3.1. (2-master/slave-constraint) The master/slave matching problem, introduced by Hefner and Kleinschmidt [20], arises in manpower scheduling problem in printing
plants. Let G = (V, E) be an undirected graph and D = (V, A) be a directed graph with thesame vertex set as G. For (us , um ) ∈ A, we say that us is a slave of um and um is a master of
us . A master/slave matching (MS-matching for short) is a matching M in G which satisﬁes
the following master/slave constraint (MS-constraint):(us , um ) ∈ A, us ∈ ∂M ⇒ um ∈ ∂M.

(5)

The MS-matching problem (MSMP ) is to ﬁnd an MS-matching of maximum cardinality. Givena weight function w : E → R+ , the weighted MSMP is deﬁned similarly. Hefner and Kleinschmidt [20] proved that it is NP-hard in general, while it can be solved in O(|V |3 ) time
under the assumption that k(D) ≤ 2, where k(D) denotes the maximum size of a connectedcomponent of D. Such MSMP is called the 2-MSMP .
Let D = (V, A) be a directed graph with k(D) ≤ 2. Then D consists of the following threekinds of components:(a) ◦(b) ◦ ←− ◦(c) ◦ ←→ ◦MS-constraints (5) arising from (a), (b), and (c) correspond to F(La ), F(Lb ), and F(Lc ),respectively, where
(
)
(
)
( )
d
k
0
k
La = d , Lb =, and Lc =
−k 0
−k 0
with constants d > 0 and k ̸= 0. Here, La , Lb , and Lc are generic skew-symmetric matrices
with nonnegative diagonals. Thus the 2-MSMP is included in the matching problem withprojected linear delta-matroids. It should be noted that MS-constraints with k(D) ≥ 3 are notnecessarily contained in our framework.
Example 3.2. (multi-master/single-slave constraint) Amanuma and Shigeno [1] introduced the following variant of the MSMP, motivated by the observation of staﬀ schedulingwith new staﬀs. Given an undirected graph G = (V, E) and a directed graph D = (V, A),9we say that a multi-master single-slave matching (MMSS-matching) is a matching M in G
satisfyingu ∈ ∂M, N + (u) ̸= ∅ ⇒ N + (u) ∩ ∂M ̸= ∅,where N + (u) = {v ∈ V | (u, v) ∈ A}. Note that if k(D) ≤ 2, then the family of MMSSmatchings coincides with that of MS-matchings. Amanuma and Shigeno showed that thisproblem can be solved in polynomial time if each connected component of D has (i) exactly
one slave vertex us , or (ii) exactly two slave vertices u1s , u2s with (u1s , u2s ), (u2s , u1s ) ∈ A. MMSSconstraints arising from (i) and (ii) correspond to F(Li ) and F(Lii ) determined by


us

0
 −k
1

Li =  ..
 .
−kn

u1m

···

k1

···
D

u1s

u2s

1
Um

2
Um

0
kn
 −k
1




 and Lii =  −k1


 0
−k2

k1
0
0
−k3
−k4

k1⊤
0⊤

0⊤
k3⊤

unm





D

12
Um


k2⊤
k4⊤ 


,



where D is a diagonal matrix with positive entries and kj = (k1j , . . . , knj j )⊤ is a vector of size
nj with constants k1j , . . . , knj j for j = 1, . . . , 4. Indeed, if a feasible set F of F(Li ) contains us ,F contains at least one uim . Next, consider the case of F(Lii ). If a feasible set F of F(Lii )1 ∪ U 2 ∪ U 12 . This is because u1
contains both u1s and u2s , then F can contain any subset of Ummms
is a master of u2s and vice versa. If F contains u1s and not u2s , then F has to contain at least
1 ∪ U 12 , which is a master of u1 . Here, Li and Lii are generic skew-symmetric
one element of Ummsmatrices with nonnegative diagonals.
Example 3.3. (matching constraint) Let G = (V, EG ) be an undirected graph and (V, FH )be the matching delta-matroid of an undirected graph H = (V, EH ), i.e., F ∈ FH if H has amatching M with ∂M = F . Since (V, FH ) is represented by a generic skew-symmetric matrix
whose support graph coincides with H, the matching problem with (V, FH ) is contained in ourframework with no projection.
This constraint arises in the maximum cycle subgraph problem in a 2-edge-colored multigraph [3]. A 2-edge-colored multigraph is a graph which has red edges and blue edges. A
cycle subgraph is a union of disjoint cycles whose successive edges diﬀer in color. It is known
that a maximum cycle subgraph can be found in polynomial time by the maximum matching problem. Let Gr and Gb be the subgraphs consisting of all the red edges and all theblue edges, respectively. We know that the maximum cycle subgraph problem is equivalent toﬁnding a maximum cardinality matching M in Gr subject to ∂M is feasible for the matchingdelta-matroid of Gb .
Example 3.4. (upper/lower size constraint) Let G = (V, E) be an undirected graph.
Deﬁne V1 , . . . , Vm to be a partition of V and r1 , . . . , rm to be positive integers. In this setting
we aim at ﬁnding a maximum cardinality matching M with |∂M ∩ Vi | ≤ ri for any i.
This problem can be viewed as the matching problem with a projection of a generic even10

delta-matroid. Indeed, deﬁne a bipartite graph H = (V, W ; EH ) as follows:
W =
EH =

m
∪
i=1
m
∪

Wi , where Wi = {w1i , . . . , wri i }(i = 1, . . . , m),Ei , where Ei = {(v, w) | v ∈ Vi , w ∈ Wi }(i = 1, . . . , m).

i=1

Thus H is the disjoint union of complete bipartite graphs with vertex sets Vi and Wi for all i.
Consider the matching matroid of H, denoted by FH . Then the size constraint is represented
by using (V, FH |W ).
Note that X ∈ FH △V |W if and only if |X ∩ Vi | ≥ |Vi | − ri for any i. Hence by using thedelta-matroid (V, FH △V |W ), we can also deal with ﬁnding a maximum cardinality matching
M with |∂M ∩ Vi | ≥ ri′ for any i, where ri′ = |Vi | − ri .
Example 3.5. (linear matroid constraint) Let G = (V, E) be an undirected graph and(V, I) be a linear matroid. Then we discuss ﬁnding a maximum cardinality matching M with∂M ∈ I.
We denote a representation of (V, I) by a matrix A with row set W and column set V .
Deﬁne a skew-symmetric matrix K to be
)
(
O
A
.
K=
−A⊤ O
The column set of K is denoted by W ∪ V . Then it is not diﬃcult to see that F(K)|W = I.
Thus the matching problem with linear matroid constraint can be reduced to one with projected
linear delta-matroids.
We conclude this section with a relation between our delta-matroid and a simultaneousdelta-matroid. A pair (V, F) is called a simultaneous delta-matroid if it satisﬁes the following
simultaneous exchange property:(SDM) For F, F ′ ∈ F and u ∈ F △F ′ , there exists v ∈ F △F ′ such that F △{u, v} ∈ F andF ′ △{u, v} ∈ F.
It is shown in [13, 37] that an even delta-matroid satisﬁes (SDM). In fact, a delta-matroid issimultaneous if and only if it is a projection of some even delta-matroid on a singleton [13].
Simultaneous delta-matroids are also discussed in Takazawa [36], where he showed that deltamatroids arising from branchings and matching forests both satisfy (SDM). We prove that ourdelta-matroid is a simultaneous delta-matroid as follows.
Theorem 3.5. A delta-matroid (V, FK ) given by (1) is a simultaneous delta-matroid.
Proof. We denote F(K)△S by F̃. Then (VK , F̃) is an even delta-matroid. We prove thatFK = F̃|R satisﬁes the simultaneous exchange axiom (SDM). Let F, F ′ ∈ FK and u ∈ F △F ′ .
Then there exist Y, Y ′ ⊆ R such that F ∪ Y, F ′ ∪ Y ′ ∈ F̃. Since F̃ satisﬁes the simultaneous
exchange axiom (SDM), there exists ṽ ∈ (F ∪ Y )△(F ′ ∪ Y ′ ) = (F △F ′ ) ∪ (Y △Y ′ ) such that(F ∪ Y )△{u, ṽ} ∈ F̃and11(F ′ ∪ Y ′ )△{u, ṽ} ∈ F̃.

(6)

If ṽ ∈ F △F ′ , (6) is rewritten as (F △{u, ṽ}) ∪ Y ∈ F̃ and (F ′ △{u, ṽ}) ∪ Y ′ ∈ F̃. Hence wehave F △{u, ṽ} ∈ FK and F ′ △{u, ṽ} ∈ FK . Thus (SDM) with v = ṽ holds. If ṽ ∈ Y △Y ′ , itfollows from (6) that F △{u} ∈ FK and F ′ △{u} ∈ FK . This implies that (SDM) with v = uholds.

4

Generic delta-matroid matching

In this section, we discuss weighted non-bipartite matching problem with a projected linear
delta-matroid, and show that it can be solved in polynomial time if a given skew-symmetricmatrix K is generic. Note that all the delta-matroids given in Examples 3.1–3.4 are generic.
Thus weighted matching problems with these constraints can be solved in polynomial time.
Let G = (V, EG ) be a graph, w : EG → R+ be an edge weight, and K be a skew-symmetricmatrix with row/column set VK ⊇ V . We denote VK \ V by R. For a subset S of V , let FK be
given by (1). The main theorem of this section is the following.
Theorem 4.1. If a skew-symmetric matrix K is generic, the weighted delta-matroid matchingproblem with (V, FK ) can be solved in O(|V |3 ) time.
By the deﬁnition, we have
FK = {(X \ R)△S | rank K[X] = |X|, X ⊆ R ∪ V },because S and R are disjoint. Let H = (R ∪ V, EH ) be the support graph of K. Since K isgeneric, we obtain
FK = {(∂MH \ R)△S | MH : matching in H}
by Lemma 2.1. Then, the given problem is rewritten as a problem to ﬁnd a matching MG in
G which maximizes w(MG ) such that there exists a matching MH in H with (∂MH \ R)△S =∂MG .
The above problem is reduced to the maximum weight matching problem as follows. Let
VG and VH be copies of V , and VS be a copy of S ⊆ V . The copies of i ∈ V are denoted byiG ∈ VG , iH ∈ VH , and iS ∈ VS , respectively. We set U = VG ∪ VH ∪ VS for convenience. For
G = (VG , EG ) and H = (R ∪ VH , EH ), we construct a graph Γ = (U ∪ R, EG ∪ EH ∪ Ẽ) withẼ = {(iG , iH ) | i ∈ V \ S} ∪ {(iG , iS ), (iS , iH ) | i ∈ S}.
The weight γ(e) of an edge e ∈ EG ∪ EH ∪ Ẽ is deﬁned to beγ(e) ={
w(e) (e ∈ EG )0(e ∈ EH ∪ Ẽ).

Then the following lemma holds.
Lemma 4.2. The following (i) and (ii) hold.
(i) For a matching M in Γ with U ⊆ ∂M , the set MG = M ∩ EG is a matching in G with∂MG ∈ FK and w(MG ) = γ(M ).
12(ii) For a matching MG in G with ∂MG ∈ FK , there exists a matching M in Γ with U ⊆ ∂M
and γ(M ) = w(MG ).
Proof. Deﬁne MH = M ∩ EH . Since U ⊆ ∂M , it holds that iG ∈ ∂MG if and only if iH ∈ ∂MH
for any i ∈ V \ S, and iG ∈ ∂MG if and only if iH ̸∈ ∂MH for any i ∈ S. Hence (∂MH \ R)△S
corresponds to ∂MG . This means that MG is a matching satisfying ∂MG ∈ FK and w(MG ) =γ(M ).
We next prove (ii). By the deﬁnition of FK where K is generic, there exists a matching
MH in H with (∂MH \ R)△S = ∂MG . We deﬁne
M = MG ∪ MH ∪ {(iS , iH ) | i ∈ S ∩ ∂MG }∪ {(iG , iS ) | i ∈ S ∩ ∂MH } ∪ {(iG , iH ) | i ̸∈ ∂MG ∪ ∂MH )}.
Then M is a matching in Γ satisfying U ⊆ ∂M and γ(M ) = w(MG ).
By Lemma 4.2, a matching M in Γ has a corresponding matching MG in G, and viceversa. Thus, we reduce our problem to maximum weight matching problem in Γ, and solve thisproblem in O(|V |3 ) time [16, 26]. This completes the proof of Theorem 4.1.

5

Bipartite delta-matroid matching

Let G = (V + , V − ; E) be a bipartite graph, and (V − , F − ) be a delta-matroid on V − . The
bipartite delta-matroid matching is to ﬁnd a maximum cardinality matching M in G satisfying∂ − M ∈ F − . Although Section 4 assumes that a matrix K is generic, this section deals with K
over the rational ﬁeld Q. This problem is a special case of the delta-matroid matching problem,
where G is restricted to be bipartite and the delta-matroid is deﬁned on V − . The general caseis discussed in Section 6.
Let K be an n × n skew-symmetric matrix with row/column set VK with V − ⊆ VK . Deﬁne−a delta-matroid (V − , FK
) to be−FK= F(K)|R(7)
with R = VK \ V − . In this section, we mainly focus on the bipartite delta-matroid matching−with (V − , FK). We remark that K is not assumed to be generic, which is diﬀerent from
Section 4, and instead, we assume that FK is not twisted in this section.
In Section 5.1, we describe a polynomial-time algorithm for this problem, which is basedon mixed matrix theory described in Section 2.3. For that purpose, we ﬁrst deﬁne operations
induced by a bipartite graph for a delta-matroid, and show that this operation preserves linear
delta-matroidness. We further impose linear matroid constraints on V + in Section 5.2.

5.1

Algorithm via mixed skew-symmetric matrices

Let G = (V + , V − ; E) be a bipartite graph. For a delta-matroid (V − , F − ) on the one vertex
side of G, we deﬁne
F + = {J + ⊆ V + | G[J + , J − ] has a perfect matching for some J − ∈ F − }.
13

Then it is known that (V + , F + ) forms a delta-matroid [5], called the delta-matroid induced by−
G. We will further show that for a delta-matroid (V − , FK
) given by (7), the delta-matroid++(V , FK ) induced by G is also represented by a skew-symmetric matrix.
Deﬁne T (G) = (Tij ) to be a generic matrix with row set V + and column set V − provided
that Tij ̸= 0 if (i, j) ∈ E and Tij = 0 otherwise. Note that for vertex sets J + ⊆ V + andJ − ⊆ V − , G[J + , J − ] has a perfect matching if and only if T (G)[J + , J − ] is nonsingular. We
denote by K ′ a mixed skew-symmetric matrix in the form of

Vc− V − RV+O
T (G) O O
 −T (G)⊤
O
D O


K′ = 
,


O
−D
K
O
O

(8)

where D = (dii ) denotes a generic diagonal matrix all of whose diagonal entries are nonzero.
We identify each element of V − with that of Vc− in correspondence with D. Let V ′ be thewhole column set of K ′ and U ′ = Vc− ∪ V − .
−Lemma 5.1. Let G = (V + , V − ; E) be a bipartite graph and (V − , FK
) be a delta-matroid+
given by (7). Then the delta-matroid (V + , FK
) induced by G is equal to F(K ′ )/U ′ |R, where+K ′ is deﬁned by (8). In particular, if R = ∅ then (V + , FK
) is a linear delta-matroid.

Proof. Let J + ⊆ V + be a feasible set in F(K ′ )/U ′ |R. Then there exists Y ⊆ R such thatK ′ [J + ∪ U ′ ∪ Y ] is nonsingular. This submatrix is skew-symmetric, and its Pfaﬃan is equal to∑∏dii · pf K[X ∪ Y ].
(9)
pf K ′ [J + ∪ U ′ ∪ Y ] =± det T (G)[J + , Xc ] ·X⊆V −i∈V − \XSince the left-hand side is nonzero, there exists X ⊆ V − such that both of T (G)[J + , Xc ] and−+K[X ∪ Y ] are nonsingular. This implies that X ∈ FK
and hence J + ∈ FK.
+++
Conversely, let J ⊆ V be a feasible set in FK . Then there exists J − ⊆ V − such that−−
T (G)[J + , J − ] is nonsingular and J − ∈ FK
. It follows from J − ∈ FK
that there exists Y ⊆ R−such that K[J ∪ Y ] is nonsingular. Consider the principal submatrix K ′ [J + ∪ U ′ ∪ Y ] of K ′ .
Its Pfaﬃan is equal to (9). The right-hand side has at least one nonzero term when X = J − .
Since each nonzero term has distinct dii ’s, we conclude that pf K ′ [J + ∪U ′ ∪Y ] ̸= 0 by genericity
of dii ’s. Thus J + ∪ U ′ ∪ Y is feasible for F(K ′ ), and hence J + ∈ F(K ′ )/U ′ |R.
Therefore, the ﬁrst part of the statement holds. Note that, since K ′ [U ′ ] is nonsingular,F(K ′ )/U ′ can be represented by some skew-symmetric matrix by pivoting operation. Hence if+
R = ∅ then (V + , FK
) is a linear delta-matroid.
We prove the following theorem using Lemma 5.1.
−
) given by (7) can be solved
Theorem 5.2. The bipartite delta-matroid matching with (V − , FK
in polynomial time.

Proof. We show that this problem can be solved by a greedy algorithm for a delta-matroid.
+
By the deﬁnition of FK, for a set X ⊆ V + , there exists a matching M in G with X = ∂ + M
14−+and ∂ − M ∈ FK
if and only if X ∈ FK
. Hence the maximum size of delta-matroid matchings++
is equal to the maximum size of feasible sets in FK. Since (V + , FK
) is a delta-matroid, we can+ﬁnd a maximum feasible set in FK by a greedy algorithm. In fact, for a delta-matroid F(K ′ ),deﬁne a weight function c : V ′ → R+ as follows:{c(v) =

1 (v ∈ V + )0 (v ̸∈ V + ).

+Then, by Lemma 5.1, ﬁnding a maximum feasible set in FK
is equivalent to ﬁnding a feasible′′
set X in F(K ) with U ⊆ X that maximizes c(X). Such X can be found in polynomial timeby Lemma 2.4. Note that a maximum matching corresponding to X can also be computed by
Corollary 2.3.

5.2

Bipartite delta-matroid matching with linear matroid constraints

In this section, we deal with the bipartite delta-matroid matching with linear matroid constraints on the other vertex side. That is, for the bipartite delta-matroid matching with−
(V − , FK) given by (7), we are additionally given a linear matroid (V + , I), and our task is−
to ﬁnd a maximum cardinality matching M in G subject to ∂ + M ∈ I and ∂ − M ∈ FK.
+
Let A be an m × n matrix representing (V , I). The column set corresponds to V + andthe row set is denoted by W . We now construct a mixed skew-symmetric matrix
W

Vc+ V + Vc− V − ROAO O O O
 −A⊤
O D′ O O O 


 O

−D′

,
Ǩ = 

O
O


K′


O
 O

O
O
where K ′ is deﬁned in (8) and D′ = (d′ii ) is a generic diagonal matrix all of whose diagonal
entries are nonzero. Let V̌ be the whole column set of Ǩ and Ǔ = Vc+ ∪ V + ∪ Vc− ∪ V − . We
consider a delta-matroid (W, F(Ǩ)/Ǔ |R). Then we can prove the following lemma in a similar
way to Section 5.1.
Lemma 5.3. Let X ⊆ W . Then there exists a matching M in G such that A[X, ∂ + M ] is−nonsingular and ∂ − M ∈ FK
if and only if X ∈ F(Ǩ)/Ǔ |R.
Proof. Assume that X is a feasible set in F(Ǩ)/Ǔ |R. Then there exists Y ⊆ R such thatǨ[X ∪ Ǔ ∪ Y ] is nonsingular. The Pfaﬃan of this submatrix is equal to∑∏pf Ǩ[X ∪ Ǔ ∪ Y ] =± det A[X, Jc ] ·d′ii · pf K ′ [J ∪ Vc− ∪ V − ∪ Y ].
(10)i∈V + \JJ⊆V +Since the left-hand side is nonzero, there exists J ⊆ V + such that both of A[X, Jc ] and K ′ [J ∪Vc− ∪ V − ∪ Y ] are nonsingular. Moreover, the nonsingularity of the latter matrix implies that15+J ∈ FK
by Lemma 5.1, which means that there exists a matching M in G with ∂ + M = J and−∂ − M ∈ FK
. Thus the suﬃciency of the statement holds.
−
Conversely, let M be a matching in G such that A[X, ∂ + M ] is nonsingular and ∂ − M ∈ FK
.
+
+
+
+
−
−
+
We set J = ∂ M and J = ∂ M . Then J ∈ FK follows from the deﬁnition of FK . By
Lemma 5.1, there exists Y ⊆ R such that K ′ [J + ∪ Vc− ∪ V − ∪ Y ] is nonsingular. Consider the
principal submatrix Ǩ[X ∪ Ǔ ∪ Y ] of Ǩ. Its Pfaﬃan is equal to (10), whose right-hand side
has at least one nonzero term when J = J + . Since each nonzero term has distinct d′ii ’s, weconclude that pf Ǩ[X ∪ Ǔ ∪ Y ] ̸= 0 by genericity of d′ii ’s. Thus X ∈ F(Ǩ)/Ǔ |R holds, andhence we obtain the necessity of the statement.

Therefore, in order to ﬁnd a maximum matching M satisfying given delta-matroid constraints, it suﬃces to ﬁnd a maximum feasible set X ⊆ W in F(Ǩ)/Ǔ |R. Such X can befound in polynomial time by applying Lemma 2.4 to a linear delta-matroid (V̌ , F(Ǩ ′ )), a set
Ǔ required to be contained, and a weight function c : V̌ → R+ deﬁned by{
1 (v ∈ W )c(v) =.
0 (v ̸∈ W )We can construct from X a desired matching M by Corollary 2.3.
Thus we obtain the following theorem.
−
Theorem 5.4. For a delta-matroid (V − , FK
) given by (7), the bipartite delta-matroid match+ing with linear matroid constraints on V can be solved in polynomial time.

Remark 5.5. Hefner and Kleinschmidt [21] extended the 2-MSMP to one with capacity constraints. That is, given a bipartite graph G = (V + , V − ; E), a directed graph D = (V + ∪V − , A)with k(D) ≤ 2, a partition (V1+ , . . . , Vm+ ) of V + , and positive integers r1 , . . . , rm , we aim at
ﬁnding a maximum cardinality MS-matching M in G subject to |∂M ∩ Vi+ | ≤ ri for 1 ≤ i ≤ m.
They showed that this problem is NP-hard in general.
Theorem 5.4 indicates that if 2-MS-constraints are imposed only on V − , the 2-MSMP withcapacity constraints can be solved in polynomial time, because the capacity constraints on V +can be represented by a linear matroid.

6

Related intersection-type problem

Let S1 and S2 be two families of subsets in a ﬁnite set V . The intersection problem with respect
to S1 and S2 is the problem of ﬁnding a maximum cardinality set in S1 ∩ S2 . A well-known
example of this kind of problem is the case where both S1 and S2 are matroids, called thematroid intersection problem, which can be solved in polynomial time (see e.g., [34]). In thissection, we summarize our results from the viewpoint of the intersection problem with respect
to a matroid and a delta-matroid. For a matroid (V, I) and a delta-matroid (V, F), we classify
related intersection problems with respect to I and F as Table 1. Note that an untwisted linear
delta-matroid in Table 1 means a delta-matroid F(K) for some skew-symmetric matrix K.
Let us ﬁrst discuss the case where (V, I) is a transversal matroid, that is, given a bipartite
graph G = (U, V ; E), I ∈ I holds if and only if G has a matching covering I. Hence the intersection problem with a transversal matroid (V, I) coincides with the bipartite delta-matroid
16

Table 1: Intersection problems with a matroid and a delta-matroid
delta-matroid (V, F)
matching
generaluntwisted linear
delta-matroid
delta-matroid
delta-matroidtransversal
poly. timepoly. time
exp. time
matroid(Theorem 4.1)
(Theorem 5.2) (Theorem 6.1)
matroidlinearpoly. time [28]poly. time
exp. time
matroid(linear matroid matching) (Theorem 5.4)
(V, I)
generalexp. time [23]exp. time
exp. time
matroid(matroid matching)matching. Therefore, it follows from Theorems 4.1 and 5.2 that we can solve the intersection
problems in polynomial time if (V, F) is a matching delta-matroid and an untwisted linear
delta-matroid, respectively. However, it turns out to be intractable if (V, F) is not linear.
Theorem 6.1. The bipartite delta-matroid matching problem, i.e., the intersection problem
with respect to a transversal matroid and a delta-matroid, cannot be solved in polynomial timein the oracle model.
Proof. Let G = (V, E) be a graph with |V | = n and (V, I) be a matroid with rank r. We
consider to ﬁnd a matching MG of size r with ∂MG ∈ I, which is known to require exponential
time in the oracle model [34, §43.9].
We deﬁne two delta-matroids (V, Fb ) and (V, FG ) to be the base family of the given matroid
and the matching delta-matroid of G, respectively. We denote by V1 and V2 the copies of V , andby vi ∈ Vi (i = 1, 2) the copies of v ∈ V . Construct a bipartite graph H = (V, V1 ∪ V2 ; E) with
E = {(v, vi ) | v ∈ V, i = 1, 2}. Let (V1 ∪ V2 , F) be a delta-matroid deﬁned by the direct sum of(V1 , Fb ) and (V2 , FG △V2 ). Then H has a matching MH of size n with ∂MH ∩ (V1 ∩ V2 ) ∈ F if
and only if G has a matching MG of size r with ∂MG ∈ I. Indeed, if such MG exists, by letting
Ji be the copies of ∂MG in Vi (i = 1, 2), we know that J1 ∈ Fb and J2 △V2 = V2 \ J2 ∈ FG △V2 ,and hence H has the matching MH covering J1 ∪ (V2 \ J2 ), which satisﬁes the constraints.
The converse also holds by the same argument. Therefore, we can reduce ﬁnding a matching
MG of size r with ∂MG ∈ I to the bipartite delta-matroid matching, and thus the statement
holds.
Let us remark that the master/slave matching problem in Example 3.1 is shown to be NP-hardeven if the graph G is bipartite and k(D) = 3 [1, 20]. Since the MS-constraint with k(D) = 3
can be represented by a (non-linear) delta-matroid, except for the case where the directed graphis complete, this fact implies that the bipartite delta-matroid matching is NP-hard even whenan explicit representation of the delta-matroid is given.
Next assume that (V, F) is a matching delta-matroid of a graph H. Then (V, F) is represented by a generic slew-symmetric matrix whose support graph coincides with H. Thismeans that the intersection problem with a matching delta-matroid (V, F) is equivalent to thematroid matching. Therefore, if (V, I) is linear then it can be solved in polynomial time, while17deltamatroid(V, F1 )Table 2: Intersection problems with two delta-matroids
delta-matroid (V, F2 )matching
lineargeneralmatching poly. time
open
exp. time(matching) (linear delta-matroid matching) (matroid matching)linearopen
exp. time(linear delta-matroid matching)

it requires exponential time if (V, I) is general. Hence, for general (V, I), the intersection problem requires exponential time, because a matching delta-matroid is a special case of (linear)delta-matroids.
The remaining case is that for a linear matroid and an untwisted delta-matroid. This
problem can be solved in polynomial time by Theorem 5.4. Indeed, for a linear matroid (V, I)
and an untwisted linear delta-matroid (V, F), construct a bipartite graph G = (V, V ′ ; E), whereV ′ is a copy of V and E consists only of edges connecting a vertex in V and its copy. Then theintersection problem with respect to I and F is equivalent to ﬁnding a maximum matching M
in G with ∂ + M ∈ I and ∂ − M ∈ F.
It should be noted that Fleiner et al. [14] deal with the intersection problem with respect
to a matroid and the 2-MS-constraint in Example 3.1, which is a special case of a matchingdelta-matroid. They showed that this problem can be solved in polynomial time with the aidof the matroid intersection.
We conclude this section with remarks on the intersection problems with respect to twodelta-matroids Mi = (V, Fi ) (i = 1, 2), which is summarized in Table 2. If M1 is a matchingdelta-matroid of a graph H, the problem is equivalent to the delta-matroid matching. Thisimplies that if M2 is also a matching delta-matroid then we can solve it in polynomial timeby Theorem 4.1, and if M2 is general then it requires exponential time. Assume that M2 islinear in addition. This case, which is equivalent to the matching problem with linear deltamatroids, is an important broader class of the delta-matroid matching, because it includes thelinear matroid matching and the linear delta-covering as a special case. Let us remark that
this problem is equivalent to that with two linear delta-matroids.
Theorem 6.2. The intersection problem with respect to two linear delta-matroids is reduced
to the linear delta-matroid matching, i.e., the intersection problem with respect to a matchingdelta-matroid and a linear delta-matroid.
Proof. Let (V, Fi ) (i = 1, 2) be two linear delta-matroids. Then construct a bipartite graph
G = (V, V ′ ; E), where V ′ is a copy of V and E consists only of parallel edges connecting avertex in V and its copy. Then the intersection problem with respect to F1 , F2 is reduced
to the bipartite delta-matroid matching with (V ∪ V ′ , F), where F is a direct sum of F1 and
F2 .

18

Acknowledgement
The authors are grateful to Satoru Iwata for fruitful comments on this topic, and Maiko Shigeno
for informing us of the recent paper [1]. They are also thankful to Kazuo Murota and Kazuhisa
Makino for helpful suggestions.

References[1] T. Amanuma and M. Shigeno.
manuscript, 2011.

Matching problems with dependence constraints.

[2] V. Aggarwal. A Lagrangian relaxation method for the constrained assignment problem.
Computers and Operations Research, 12:97–106, 1985.
[3] J. Bang-Jensen and G. Gutin. Alternating cycles and paths in edge-coloured multigraphs:
A survey. Discrete Mathematics, 165/166:39–60, 1997.
[4] A. Bouchet. Representability of ∆-matroids. Combinatorics, Colloquia Mathematica Societatis János Bolyai, 52:167-182, 1988.
[5] A. Bouchet. Greedy algorithm and symmetric matroids. Mathematical Programming,
38:147–159, 1987.
[6] A. Bouchet. Matchings and ∆-matroids. Discrete Applied Mathematics, 24:55–62, 1989.
[7] A. Bouchet. Coverings and delta-coverings. Lecture Notes in Computer Science 920 (IPCO1995), 228–243, 1995.
[8] A. Bouchet and W. H. Cunningham. Delta-matroids, jump systems and bisubmodular
polyhedra. SIAM Journal on Discrete Mathematics, 8:17–32, 1995.
[9] S. Canzar, K. Elbassioni, G. Klau, and J. Mestre. On tree-constrained matchings andgeneralizations. Lecture Notes in Computer Science 6755 (ICALP 2011), 98–109, 2011.
[10] R. Chandrasekaran and S. N. Kabadi. Pseudomatroids. Discrete Mathematics, 71:205–217,
1988.
[11] H. Y. Cheung, L. C. Lau, and K. M. Leung. Algebraic algorithms for linear matroid
parity problems. Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms(SODA), 2011.
[12] A. Dress and T. F. Havel. Some combinatorial properties of discriminants in metric vector
spaces. Advances in Mathematics, 62:285–312, 1986.
[13] A. Duchamp. Strong symmetric exchange axiom for delta-matroids. preprint, 1995.
[14] T. Fleiner, A. Frank, and S. Iwata. A constrained independent set problem for matroids.
Operations Research Letters, 32:23–26, 2004.

19

[15] H. N. Gabow and M. Stallmann. An augmenting path algorithm for linear matroid parity.
Combinatorica, 6:123–150, 1986.
[16] H.N. Gabow. Implementation of Algorithms for Maximum Matching on Nonbipartite
Graphs. PhD thesis, Department of Computer Science, Stanford University, 1973.
[17] J. F. Geelen and S. Iwata. Matroid matching via mixed skew-symmetric matrices. Combinatorica, 25:187–215, 2005.
[18] J. F. Geelen, S. Iwata, and K. Murota. The linear delta-matroid parity problem. Journalof Combinatorial Theory, Series B, 88:377–398, 2003.
[19] A. Hefner. A min-max theorem for a constrained matching problem. SIAM Journal on
Discrete Mathematics, 10:180–189, 1997.
[20] A. Hefner and P. Kleinschmidt. A constrained matching problem. Annals of Operations
Research, 57:135–145, 1995.
[21] A. Hefner and P. Kleinschmidt. A polyhedral approach for a constrained matching problem. Discrete & Computational Geometry, 17:429–437, 1997.
[22] M. Iri and N. Tomizawa. An algorithms for solving the ‘independent assignment problem’
with application to the problem of determining the order of complexity of a network (inJapanese). Transactions of the Institute of Electronics and Communication Engineers ofJapan, 57A:627–629, 1974.
[23] P. M. Jensen and B. Korte. Complexity of matroid property algorithms. SIAM Journal
on Computing, 11:184–190, 1982.
[24] N. Kakimura and M. Takamatsu. Matching problem with delta-matroid constraints. Proceedings of the 18th CATS symposium (Computing: the Australasian Theory Symposium),
to appear, 2012.
[25] B. Korte and J. Vygen. Combinatorial Optimization: Theory and Algorithms. SpringerVerlag, 2006.
[26] E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart andWinston, New York, 1976.
[27] J. Lee, M. Sviridenko, and J. Vondrak. Matroid matching: the power of local search.
Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), 2010.
[28] L. Lovász. Matroid matching and some applications. Journal of Combinatorial Theory
Series B, 28:208–236, 1980.
[29] L. Lovász. Selecting independent lines from a family of lines in a space. Acta Scientiarum
Mathematicarum, 42:121–131, 1980.
[30] L. Lovász. The matroid matching problem. In L. Lovász and V. T. Sös, editors, Algebraic
Methods in Graph Theory, Vol. II, 495–517. North-Holland, 1981.
20

[31] L. Lovász and M. D. Plummer. Matching Theory. North-Holland, Amsterdam, 1986.
[32] K. Murota. Matrices and Matroids for Systems Analysis. Springer-Verlag, Berlin, 2000.
[33] J. B. Orlin and J. H. Vande Vate. Solving the linear matroid parity problem as a sequenceof matroid intersection problems. Mathematical Programming, 47:81–106, 1990.
[34] A. Schrijver. Combinatorial Optimization — Polyhedra and Eﬃciency. Springer-Verlag,
2003.
[35] A. Shioura and K. Tanaka. Polynomial-time algorithms for linear and convex optimization
on jump systems. SIAM Journal on Discrete Mathematics, 21:504–522, 2007.
[36] K. Takazawa. Optimal matching forests and valuated delta-matroids. Lecture Notes in
Computer Science 6655 (IPCO 2011), 404–416, 2011. See also RIMS Preprint, RIMS-1718,
Kyoto University, 2011. Available from http://www.kurims.kyoto-u.ac.jp/preprint/
file/RIMS1718.pdf[37] W. Wenzel. ∆-matroids with the strong exchange conditions. Applied Mathematics Letters,
6:67–70, 1993.

21