# Matroid Intersection under Restricted Oracles

Kristóf Bérczi MTA-ELTE Egerváry Research Group and MTA-ELTE Momentum Matroid
Optimization Research Group, Department of Operations Research, Eötvös Loránd
University, Budapest, Hungary. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>Tamás Király11footnotemark: 1 Yutaro Yamaguchi
Department of Information and Physical Sciences, Graduate School of
Information Science and Technology, Osaka University, Osaka, Japan. Email:
<EMAIL_ADDRESS>Yu Yokoi Principles of Informatics
Research Division, National Institute of Informatics, Tokyo, Japan. Email:
<EMAIL_ADDRESS>
###### Abstract

Matroid intersection is one of the most powerful frameworks of matroid theory
that generalizes various problems in combinatorial optimization. Edmonds’
fundamental theorem provides a min-max characterization for the unweighted
setting, while Frank’s weight-splitting theorem provides one for the weighted
case. Several efficient algorithms were developed for these problems, all
relying on the usage of one of the conventional oracles for both matroids.

In the present paper, we consider the tractability of the matroid intersection
problem under restricted oracles. In particular, we focus on the rank sum,
common independence, and maximum rank oracles. We give a strongly polynomial-
time algorithm for weighted matroid intersection under the rank sum oracle. In
the common independence oracle model, we prove that the unweighted matroid
intersection problem is tractable when one of the matroids is a partition
matroid, and that even the weighted case is solvable when one of the matroids
is an elementary split matroid. Finally, we show that the common independence
and maximum rank oracles together are strong enough to realize the steps of
our algorithm under the rank sum oracle.

Keywords: Matroid intersection, Tractability, Rank sum oracle, Common
independence oracle, Maximum rank oracle

##  1 Introduction

A cornerstone of matroid theory is the efficient solvability of the matroid
intersection problem introduced by Edmonds [9]. Efficient algorithms for
weighted matroid intersection were developed subsequently by Edmonds [10], by
Lawler [21, 23], and by Iri and Tomizawa [15]. The min-max duality theorem of
Edmonds [9] for the unweighted matroid intersection problem was generalized by
Frank [11] to the weighted case. These results do not only provide a well-
established framework that includes various tractable combinatorial
optimization problems such as bipartite matching and arborescence packing, but
in certain cases they are unavoidable in solving natural optimization problems
that seem to be unrelated to matroids. A beautiful example is the problem of
computing a cheapest rooted $k$-connected spanning subgraph of a digraph [12].
This is a pure graph optimization problem and yet the only known polynomial
algorithm is based on the recognition that minimal rooted $k$-connected
subgraphs of a digraph form the common bases of two matroids, and therefore a
weighted matroid intersection algorithm can be applied.

In order to design matroid algorithms and to analyze their complexity, it
should be clarified how matroids are given. As the number of bases can be
exponential in the size of the ground set, defining a matroid in an explicit
form is inefficient. Rather than giving a matroid as an explicit input, it is
usually assumed that one of the standard oracles is available, and the
complexity of the algorithm is measured by the number of oracle calls and
other elementary steps. Another way to define a matroid is to give an explicit
linear representation, but this restricts the scope of the algorithm to linear
matroids for which such an explicit representation is known.

For both the unweighted and weighted problems, a variety of efficient
algorithms have been developed; see e.g. [9, 10, 21, 1, 22, 15, 8, 11, 5, 14].
A common feature of these algorithms, and also all previous studies on matroid
intersection, is that they assume the availability of one of the standard
oracles for both matroids; e.g., we can ask for the rank of a subset in each
of them. Our main contribution is showing that this assumption is not
necessary for the tractability of matroid intersection, not even in the
weighted setting.

One motivation for studying restricted oracles comes from polymatroid
matching, a framework introduced by Lawler [23] as a common generalization of
matroid intersection and non-bipartite matching. In [26], Edmonds’ theorem was
deduced from polymatroid matching using a sophisticated argument. The main
point is that when the matroid intersection problem is formulated as a
polymatroid matching problem, only the _rank sum function_ of the two matroids
is used rather than the two rank functions. Although the polymatroid matching
problem cannot be solved in polynomial time in general [25, 16], the hardness
was shown through special instances that seem to be far from matroid
intersection. This suggests that matroid intersection might still be tractable
when only the sum of the rank functions is available.

We mention that another natural oracle to consider is the _minimum rank
function_ , which answers the smaller value among the two ranks of a subset.
It follows from the polyhedral results of Edmonds [9] that this oracle
suffices to describe the convex hull of common independent sets. In an
unpublished manuscript, Bárász [2] gave a polynomial time algorithm for
unweighted matroid intersection under the minimum rank oracle. We will present
additional results about this oracle in a separate paper [3].

#### Our results

Our goal is to settle the tractability of the weighted matroid intersection
problem under restricted oracles. In particular, we will focus on three
different oracles: rank sum, common independence, and maximum rank oracles.

The study of the rank sum oracle is motivated by the above discussed
connection to polymatroid matching results. The difficulty of giving an
efficient algorithm is that the usual augmenting path approach cannot be
applied directly, since the exchangeability graphs are not determined by the
rank sum oracle. Still, we are able to give a strongly polynomial time
algorithm for the weighted matroid intersection problem by emulating the
Bellman–Ford algorithm without explicitly knowing the underlying graph.

######  Theorem 1.1.

There exists a strongly polynomial time algorithm for the weighted matroid
intersection problem in the rank sum oracle model.

It is not difficult to see that a common independence oracle can be
constructed with the help of a rank sum oracle. Therefore, any algorithm that
is based on the usage of a common independence oracle immediately translates
into an algorithm that uses a rank sum oracle. Nevertheless, the reverse
implication does not hold, hence the common independence oracle is strictly
weaker. We show that unweighted matroid intersection remains tractable under
the common independence oracle model when one of the matroids is a partition
matroid.

######  Theorem 1.2.

There exists a strongly polynomial time algorithm for the unweighted matroid
intersection problem in the common independence oracle model when one of the
matroids is a partition matroid with all-one upper bound on the partition
classes.

Although the complexity of the problem in general remains an intriguing open
question even for the unweighted setting, this seemingly simple case already
includes matchings in bipartite graphs and arborescences.

Recently, Joswig and Schröter [17] introduced the notion of split matroids, a
class with distinguished structural properties that generalizes paving
matroids. Bérczi, Király, Schwarcz, Yamaguchi and Yokoi [4] showed that every
split matroid can be obtained as the direct sum of a so-called elementary
split matroid and uniform matroids, and provided a hypergraph characterization
of elementary split matroids. By relying on this characterization, we show
that even weighted matroid intersection is tractable in the common
independence oracle model when one of the matroids is from this class.

######  Theorem 1.3.

There exists a strongly polynomial time algorithm for the weighted matroid
intersection problem in the common independence oracle model when one of the
matroids is an elementary split matroid.

We will see that the maximum rank oracle does not carry too much information
on its own. However, when combined with the common independence oracle, they
are strong enough to mimic our algorithm for the rank sum case.

######  Theorem 1.4.

There exists a strongly polynomial time algorithm for the weighted matroid
intersection problem when both the common independence and the maximum rank
oracles are available.

#### Organization

The rest of the paper is organized as follows. Basic definitions and notation
are introduced in Section 2, together with some fundamental results on matroid
intersection. Section 3 describes the relation between different oracles. We
present our strongly polynomial algorithm under the rank sum oracle in Section
4. The common independence oracle case when one of the matroids is a partition
matroid or an elementary split matroid, as well as the combination of the
common independence and maximum rank oracles, is discussed in Section 5.

##  2 Preliminaries

For the basics on matroids and the matroid intersection problem, we refer the
reader to [27, 29]. Throughout the paper, for $i=1,2$, let
${\mathbf{M}}_{i}=(E,{\mathcal{I}}_{i})$ be loopless111The assumption that the
matroids are loopless is not restrictive as loops can be easily detected by
any of the oracles considered. matroids on the same finite ground set $E$ of
size $n$, whose independent set families, rank functions, and closure
operators are denoted by ${\mathcal{I}}_{i}$, by $r_{i}$, and by
$\mathrm{cl}_{i}$, respectively. For two sets $X,Y\subseteq E$, we denote
their symmetric difference by $X\triangle Y=(X\setminus Y)\cup(Y\setminus X)$.
The $k$-truncation of a matroid ${\mathbf{M}}=(S,{\mathcal{I}})$ is a matroid
$({\mathbf{M}})_{k}=(S,{\mathcal{I}}^{\leq k})$ with ${\mathcal{I}}^{\leq
k}=\\{\,X\in{\mathcal{I}}\mid|X|\leq k\,\\}$. For $I\in{\mathcal{I}}_{i}$ and
$x\in\mathrm{cl}_{i}(I)\setminus I$, the fundamental circuit of $x$ with
respect to $I$ in ${\mathbf{M}}_{i}$ is denoted by $C_{i}(I,x)=\\{\,y\in I\mid
I+x-y\in{\mathcal{I}}_{i}\,\\}$.

We consider four oracles for matroid intersection. Given a set $X\subseteq E$
as an input, a rank sum oracle (Sum) answers the sum
${r_{\mathrm{sum}}}(X)\coloneqq r_{1}(X)+r_{2}(X)$ of the ranks of $X$, a
minimum rank oracle (Min) answers the minimum
${r_{\mathrm{min}}}(X)\coloneqq\min\left\\{r_{1}(X),r_{2}(X)\right\\}$ of the
ranks of $X$, a maximum rank oracle (Max) answers the maximum
${r_{\mathrm{max}}}(X)\coloneqq\max\left\\{r_{1}(X),r_{2}(X)\right\\}$ of the
ranks of $X$, and a common independence oracle (CI) answers _“Yes”_ if
$X\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ and _“No”_ otherwise.

Let us first overview some basic results on unweighted matroid intersection.
In [9], Edmonds gave the following characterization for the maximum
cardinality of a common independent set of two matroids.

######  Theorem 2.1 (Edmonds [9]).

Given two matroids ${\mathbf{M}}_{1}=(E,{\mathcal{I}}_{1})$ and
${\mathbf{M}}_{2}=(E,{\mathcal{I}}_{2})$ on a common ground set $E$, the
maximum cardinality of a common independent set of ${\mathbf{M}}_{1}$ and
${\mathbf{M}}_{2}$ is equal to

$\displaystyle\min\left\\{\,r_{1}(Z)+r_{2}(E\setminus Z)\mid Z\subseteq
E\,\right\\}.$

The notion of exchangeability graphs plays a central role in any matroid
intersection algorithm.

######  Definition 2.2 (Exchangeability Graphs).

Assume that $I\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$. The exchangeability
graph corresponding to $I$ is a bipartite digraph $D[I]=(E\setminus I,I;A[I])$
defined as follows. Set

$\displaystyle S_{I}$ $\displaystyle\coloneqq\\{\,s\in E\setminus I\mid
I+s\in{\mathcal{I}}_{1}\,\\},$ $\displaystyle T_{I}$
$\displaystyle\coloneqq\\{\,t\in E\setminus I\mid
I+t\in{\mathcal{I}}_{2}\,\\},$

where elements in $S_{I}$ and in $T_{I}$ are called sources and sinks,
respectively. We then define the set $A[I]\coloneqq A_{1}[I]\cup A_{2}[I]$ of
exchangeability arcs, where

$\displaystyle A_{1}[I]\coloneqq$ $\displaystyle\ \\{\,(y,x)\mid x\in
E\setminus I,~{}y\in I,~{}I+x-y\in{\mathcal{I}}_{1}\,\\}$ $\displaystyle=$
$\displaystyle\ \\{\,(y,s)\mid s\in S_{I},~{}y\in I\,\\}\cup\\{\,(y,x)\mid
x\in E\setminus(I\cup S_{I}),~{}y\in C_{1}(I,x)\,\\},$ $\displaystyle
A_{2}[I]\coloneqq$ $\displaystyle\ \\{\,(x,y)\mid x\in E\setminus I,~{}y\in
I,~{}I+x-y\in{\mathcal{I}}_{2}\,\\}$ $\displaystyle=$ $\displaystyle\
\\{\,(t,y)\mid t\in T_{I},~{}y\in I\,\\}\cup\\{\,(x,y)\mid x\in
E\setminus(I\cup T_{I}),~{}y\in C_{2}(I,x)\,\\}.$

Note that $S_{I}$ and $A_{1}[I]$ depend only on ${\mathcal{I}}_{1}$, and
$T_{I}$ and $A_{2}[I]$ depend only on ${\mathcal{I}}_{2}$.

Brualdi [6] observed that the set $A_{i}[I]$ satisfies the following property
for $i=1,2$.

######  Lemma 2.3.

Let $I\in{\mathcal{I}}_{i}$ and let $Z\subseteq E$ satisfy $|I\triangle
Z|=|I|$ and $I\triangle Z\in{\mathcal{I}}_{i}$. Then $A_{i}[I]$ contains a
perfect matching on $Z$ (i.e., a set of vertex-disjoint arcs whose tails and
heads constitute $Z$).

Krogdahl [18, 19, 20] proved a partial converse to the above lemma.

######  Lemma 2.4 (Unique Perfect Matching Lemma).

Let $I\in{\mathcal{I}}_{i}$ and let $Z\subseteq E$ satisfy $|I\triangle
Z|=|I|$. If $A_{i}[I]$ contains a unique perfect matching on $Z$, then
$I\triangle Z\in{\mathcal{I}}_{i}$.

Finally, let us recall that a standard algorithm for finding a maximum-
cardinality common independent set is driven by the following subroutine (see
[29, $\S$ 41.2]).

For any digraph $D=(E,A)$, a path in $D$ is a sequence $P=e_{1}e_{2}\cdots
e_{\ell}$ of distinct vertices such that $(e_{i},e_{i+1})\in A$ for each
$i=1,2,\dots,\ell-1$; we call $P$ an $e_{1}$–$e_{\ell}$ path or an $X$–$Y$
path for sets $X\ni e_{1}$ and $Y\ni e_{\ell}$ to emphasize the end vertices,
and define $\ell$ as the length. A cycle in $D$ is a sequence
$e_{1}e_{2}\cdots e_{\ell}e_{1}$ such that $e_{1}e_{2}\cdots e_{\ell}$ is a
path and $(e_{\ell},e_{1})\in A$. We often identify a path or a cycle with its
vertex set $\\{e_{1},e_{2},\dots,e_{\ell}\\}$.

Input : A finite set $E$, oracle access to ${\mathcal{I}}_{1}$ and
${\mathcal{I}}_{2}$, and a common independent set
$I\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$.

Output : A common independent set $J\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$
with $|J|=|I|+1$ if one exists, or a subset $Z\subseteq E$ with
$r_{1}(Z)+r_{2}(E\setminus Z)=|I|$ otherwise.

1

2Construct the exchangeability graph $D[I]$ with source set $S_{I}$ and sink
set $T_{I}$.

If some $t\in T_{I}$ is reachable from some $s\in S_{I}$, then find a shortest
$S_{I}$–$T_{I}$ path $P$ in $D[I]$, and return $J=I\triangle P$. Otherwise,
return $Z=\\{\,e\in E\mid e~{}\text{can reach some}~{}t\in
T_{I}~{}\text{in}~{}D[I]\,\\}$.

Algorithm 1 (Augment$[E,{\mathcal{I}}_{1},{\mathcal{I}}_{2},I]$).

Now we turn to the weighted setting. For a weight function $w\colon
E\to{\mathbb{R}}$ and a subset $X\subseteq E$, define $w(X)\coloneqq\sum_{e\in
X}w(e)$. For a family ${\mathcal{F}}\subseteq 2^{E}$, a subset $X\subseteq E$
is $w$-maximal in ${\mathcal{F}}$ if $X\in\textrm{arg\,max}\left\\{\,w(Y)\mid
Y\in{\mathcal{F}}\,\right\\}$. We define
${\mathcal{I}}_{i}^{k}\coloneqq\\{\,X\in{\mathcal{I}}_{i}\mid|X|=k\,\\}$ for
$i=1,2$ and $k=0,1,\dots,n$.

One approach to solve the weighted matroid intersection problem is via
augmentation along cheapest paths in the exchangeability graph (see [29, $\S$
41.3]), where the cost function $c\colon E\to{\mathbb{R}}$ is defined on the
vertex set as follows:

$\displaystyle c(e)$ $\displaystyle\coloneqq\begin{cases}w(e)&\text{if $e\in
I$},\\\ -w(e)&\text{if $e\in E\setminus I$}.\end{cases}$ (2.1)

For each path (or cycle) $P$ in $D[I]$, we define the cost of $P$ as
$c(P)\coloneqq\sum_{e\in P}c(e)$.

Input : A finite set $E$, a weight function $w\colon E\to{\mathbb{R}}$, oracle
access to ${\mathcal{I}}_{1}$ and ${\mathcal{I}}_{2}$, and a $w$-maximal set
$I\in{\mathcal{I}}_{1}^{k}\cap{\mathcal{I}}_{2}^{k}$ for some
$k\in\\{0,1,\dots,n-1\\}$.

Output : A $w$-maximal set
$J\in{\mathcal{I}}_{1}^{k+1}\cap{\mathcal{I}}_{2}^{k+1}$ if one exists, or a
subset $Z\subseteq E$ with $r_{1}(Z)+r_{2}(E\setminus Z)=|I|$ otherwise.

1

2Construct the exchangeability graph $D[I]$ with source set $S_{I}$ and sink
set $T_{I}$. In addition, define the cost function $c\colon E\to{\mathbb{R}}$
by (2.1).

If some $t\in T_{I}$ is reachable from some $s\in S_{I}$, then find a shortest
cheapest $S_{I}$–$T_{I}$ path $P$ in $D[I]$ (i.e., the cost $c(P)$ is minimum,
and subject to this, the length of $P$ is minimum), and return $J=I\triangle
P$. Otherwise, return $Z=\\{\,e\in E\mid e~{}\text{can reach some}~{}t\in
T_{I}~{}\text{in}~{}D[I]\,\\}$.

Algorithm 2
(CheapestPathAugment$[E,w,{\mathcal{I}}_{1},{\mathcal{I}}_{2},I]$).

The next lemma characterizes $w$-maximal common independent sets in
${\mathcal{I}}^{k}_{1}\cap{\mathcal{I}}^{k}_{2}$.

######  Lemma 2.5 (cf. [29, Theorem 41.5]).

A common independent set $I\in{\mathcal{I}}_{1}^{k}\cap{\mathcal{I}}_{2}^{k}$
is $w$-maximal if and only if $D[I]$ contains no negative-cost cycle with
respect to the cost function $c$ defined as (2.1).

##  3 Polynomial Reducibility of Oracles

Although there are many different types of oracles that are used in studies on
matroids, many of these conventional oracles have the same computational
power. More precisely, we say that an oracle ${\mathcal{O}}_{1}$ is
polynomially reducible to another oracle ${\mathcal{O}}_{2}$ if
${\mathcal{O}}_{1}$ can be simulated by using a polynomial number of oracle
calls to ${\mathcal{O}}_{2}$ measured in terms of the size of the ground set.
Two oracles are polynomially equivalent if they are mutually polynomially
reducible to each other. In this sense, the rank, independence, strong basis,
circuit-finding, spanning, and port oracles are polynomially equivalent [28,
13, 7].

The aim of this section is to clarify the relation between the restricted
oracles that we consider, that is, Sum, Min, Max, and CI. As it turns out, Max
is not very useful on its own, but it provides a powerful tool when combined
with any of the other three oracles. We denote by a ‘+’ sign when we have
access to two of the oracles, e.g., Min+Max means that for a set $X\subseteq
E$ the oracle tells both ${r_{\mathrm{min}}}(X)$ and ${r_{\mathrm{max}}}(X)$.

In what follows, we discuss the reducibility of the oracles one by one. In
order to keep the presentation clear, some of the ideas appear multiple times.
For an overview of the results, see Figure 1. Observe that, by
${r_{\mathrm{sum}}}(X)={r_{\mathrm{min}}}(X)+{r_{\mathrm{max}}}(X)$, any
combination of at least two of Min, Max, and Sum is clearly equivalent. This
immediately implies that each of Min, Sum, and Max is reducible to each of
Min+Max, Min+Sum, and Sum+Max.

Figure 1: Hierarchy of oracles, directed arcs representing polynomial
reducibility. Grey boxes denote oracles for which strongly polynomial time
algorithms are given in the present paper.

######  Theorem 3.1.

CI is not polynomially reducible to Max, but it is polynomially reducible to
Min and Sum.

###### Proof.

If ${\mathbf{M}}_{1}$ is the free matroid, then Max always answers $|X|$
independently from the choice of ${\mathbf{M}}_{2}$. Thus deciding if
$X\subseteq E$ is a common independent set or not is impossible relying solely
on Max.

To see the second half, observe that for a set $X\subseteq E$, CI answers
_“Yes”_ if and only if $X$ is a common independent set of the two matroids,
that is, $r_{1}(X)=r_{2}(X)=|X|$. By the subcardinality of the rank functions,
this is equivalent to ${r_{\mathrm{min}}}(X)=|X|$ and to
${r_{\mathrm{sum}}}(X)=2|X|$. As these conditions can be checked by Min and
Sum, respectively, the theorem follows. ∎

######  Theorem 3.2.

Min is not polynomially reducible to Sum, CI, Max, and CI+Max.

###### Proof.

We define two instances of the matroid intersection problem on the same ground
set $E=\\{a,b,c,d\\}$ as follows. For $i=1,2$, let ${\mathbf{M}}_{i}$ be the
graphic matroid of the graph $G_{i}$ on Figure 2(a), and let
${\mathbf{M}}^{\prime}_{i}$ be the graphic matroid of the graph
$G^{\prime}_{i}$ on Figure 2(b). Consider the maximum-cardinality common
independent set problem for ${\mathbf{M}}_{1}$ and ${\mathbf{M}}_{2}$, and for
${\mathbf{M}}^{\prime}_{1}$ and ${\mathbf{M}}^{\prime}_{2}$. For any subset
$X$ of $E$, both Sum and CI give the same answer in the two instances, thus it
is not possible to distinguish them from each other using one of these
oracles. However, ${r_{\mathrm{min}}}(E)$ is $2$ in one of them while $3$ in
the other one, showing that Min cannot be reduced to Sum or CI.

Now take the $3$-truncation of these graphic matroids, and define
${\mathbf{N}}_{1}=({\mathbf{M}}_{1})_{3}$,
${\mathbf{N}}_{2}=({\mathbf{M}}_{2})_{3}$,
${\mathbf{N}}^{\prime}_{1}=({\mathbf{M}}^{\prime}_{1})_{3}$, and
${\mathbf{N}}^{\prime}_{2}=({\mathbf{M}}^{\prime}_{2})_{3}$. Consider the
maximum-cardinality common independent set problem for ${\mathbf{N}}_{1}$ and
${\mathbf{N}}_{2}$, and for ${\mathbf{N}}^{\prime}_{1}$ and
${\mathbf{N}}^{\prime}_{2}$. By the slight change in the definitions, both CI
and Max give the same answer in the two instances for any subset $X\subseteq
E$, thus it is not possible to distinguish them from each other using a
combination of these two oracles. However, ${r_{\mathrm{min}}}(E)$ is $2$ in
one of them while $3$ in the other one, showing that Min cannot be reduced to
CI+Max.

The case when ${\mathbf{M}}_{1}$ is the free matroid shows again that
${r_{\mathrm{min}}}(X)$ cannot be determined relying solely on Max. ∎

(a) The graphs $G_{1}$ and $G_{2}$ defining ${\mathbf{M}}_{1}$ and
${\mathbf{M}}_{2}$.

(b) The graphs $G^{\prime}_{1}$ and $G^{\prime}_{2}$ defining
${\mathbf{M}}^{\prime}_{1}$ and ${\mathbf{M}}^{\prime}_{2}$.

Figure 2: Illustration of Theorems 3.2, 3.3, and 3.4.

######  Theorem 3.3.

Sum is not polynomially reducible to Min, CI, Max, and CI+Max.

###### Proof.

If ${\mathbf{M}}_{1}$ is a uniform matroid of rank $1$, then
${r_{\mathrm{min}}}(X)=0$ if $X=\emptyset$ and $1$ otherwise, while CI answers
_“Yes”_ if $|X|\leq 1$ and _“No”_ otherwise. These answers are independent
from the choice of ${\mathbf{M}}_{2}$, therefore we cannot determine
${r_{\mathrm{sum}}}(X)$ with their help.

The case when ${\mathbf{M}}_{1}$ is the free matroid shows again that
${r_{\mathrm{sum}}}(X)$ cannot be determined relying solely on Max.

Consider the same two instances of the matroid intersection problem defined by
the $3$-truncations of the graphic matroids on Figure 2 as in the proof of
Theorem 3.2. Recall that both CI and Max give the same answer in the two
instances for any subset $X\subseteq E$, thus it is not possible to
distinguish them from each other using a combination of these two oracles.
However, ${r_{\mathrm{sum}}}(E)$ is $5$ in one of them while $6$ in the other
one, showing that Sum cannot be reduced to CI+Max. ∎

######  Theorem 3.4.

Max is not polynomially reducible to Min, Sum, and CI.

###### Proof.

The case when ${\mathbf{M}}_{1}$ is a uniform matroid of rank $1$ shows again
that ${r_{\mathrm{max}}}(X)$ cannot be determined relying solely on Min or CI.

Consider the same two instances of the matroid intersection problem defined by
Figure 2 as in the proof of Theorem 3.2. Recall that for any subset $X$ of
$E$, Sum gives the same answer in both instances, thus it is not possible to
distinguish them from each other using Sum. However, ${r_{\mathrm{max}}}(E)$
is $4$ in one of them while $3$ in the other one, showing that Max cannot be
reduced to Sum. ∎

##  4 Matroid Intersection under Rank Sum Oracle

In Algorithm 2, we assume that we are given the independence oracles of
matroids ${\mathbf{M}}_{1}$ and ${\mathbf{M}}_{2}$, which are polynomially
equivalent to the oracles of rank functions $r_{1}$ and $r_{2}$, respectively.
In this section, we consider the solvability of the weighted matroid
intersection problem when only the _rank sum function_
${r_{\mathrm{sum}}}\colon 2^{E}\to{\mathbb{Z}}_{\geq 0}$ is available, that
is, for any set $X\subseteq E$ the oracle answers the value of
${r_{\mathrm{sum}}}(X)\coloneqq r_{1}(X)+r_{2}(X)$. Note that a subset
$I\subseteq E$ belongs to ${\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ if and only
if ${r_{\mathrm{sum}}}(I)=2|I|$. However, when ${r_{\mathrm{sum}}}(I)<2|I|$,
we cannot decide whether $I\in{\mathcal{I}}_{i}$ or not for each $i=1,2$.

The matroid intersection problem under this oracle model is exactly a special
case of the _polymatroid matching problem_ , which is equivalent to the so-
called _matroid matching (or parity) problem_ [26, § 11.1]. While a max-min
duality theorem was given by Lovász [24] for the case when the matroids in
question admit linear representations222For the matroid intersection
considered as a special case, the two matroids are necessarily representable
over the same field., such a good characterization is not known in general
even in the matroid intersection case.

In what follows, we provide an algorithm for the weighted matroid intersection
problem with the rank sum oracle. We consider emulating Algorithm 2, i.e.,
CheapestPathAugment$[E,w,{\mathcal{I}}_{1},{\mathcal{I}}_{2},I]$.

###  4.1 Searching a Shortest Cheapest Path

Take any $k\in\\{0,1,\dots,n-1\\}$ and let $I$ be a $w$-maximal set
${\mathcal{I}}_{1}^{k}\cap{\mathcal{I}}_{2}^{k}$. To emulate Algorithm 2, we
want to find a shortest cheapest $S_{I}$–$T_{I}$ path in $D[I]=(E\setminus
I,I;A_{1}[I]\cup A_{2}[I])$ with respect to vertex cost $c\colon
E\to{\mathbb{R}}$ defined in Algorithm 2. With only the rank sum oracle,
however, we cannot determine the sets $A_{1}[I]$, $A_{2}[I]$, $S_{I}$, and
$T_{I}$, and hence cannot simply emulate Algorithm 2.

We show that, despite this difficulty, we can compute a shortest cheapest
$S_{I}$–$T_{I}$ path in $D[I]$. We first make some observations. Let
$D^{\prime}[I]=(E\setminus I,I;A^{\prime}_{1}[I]\cup A^{\prime}_{2}[I])$ be
the subgraph of $D[I]$ obtained from $D[I]$ by removing arcs entering $S_{I}$
and leaving $T_{I}$, i.e.,

$\displaystyle A^{\prime}_{1}[I]\coloneqq$ $\displaystyle\\{\,(y,x)\mid x\in
E\setminus(I\cup S_{I}),~{}y\in C_{1}(I,x)\,\\},$ $\displaystyle
A^{\prime}_{2}[I]\coloneqq$ $\displaystyle\\{\,(x,y)\mid x\in E\setminus(I\cup
T_{I}),~{}y\in C_{2}(I,x)\,\\}.$

Note that each element in $S_{I}\cap T_{I}$ is an isolated vertex in
$D^{\prime}[I]$. Recall that $D[I]$ has no negative cost cycle with respect to
$c$ by Lemma 2.5. This fact implies that finding a shortest cheapest
$S_{I}$–$T_{I}$ path in $D[I]$ is equivalent to finding one in
$D^{\prime}[I]$.

######  Lemma 4.1.

Any shortest cheapest $S_{I}$–$T_{I}$ path in $D^{\prime}[I]$ is a shortest
cheapest $S_{I}$–$T_{I}$ path in $D[I]$.

###### Proof.

It is sufficient to show that any shortest cheapest $S_{I}$–$T_{I}$ path in
$D[I]$ is contained in $D^{\prime}[I]$. Suppose, to the contrary, that a
shortest cheapest $S_{I}$–$T_{I}$ path $P$ uses some arc $(y,s^{*})\in
A_{1}[I]\setminus A^{\prime}_{1}[I]$ or $(t^{*},y)\in A_{2}[I]\setminus
A^{\prime}_{2}[I]$, and let $s\in S_{I}$ and $t\in T_{I}$ be its end vertices.
If $P$ uses $(y,s^{*})\in A_{1}[I]\setminus A^{\prime}_{1}[I]$, let $P(s,y)$
and $P(s^{*},t)$ be the subpaths of $P$ from $s$ to $y$ and from $s^{*}$ to
$t$, respectively. Since $(y,s)\in A_{1}[I]$, the path $P(s,y)$ is extended to
a cycle with the same vertex set in $D[I]$, and hence $c(P(s,y))$ is
nonnegative by Lemma 2.5. Then $c(P)=c(P(s,y))+c(P(s^{*},t))\geq
c(P(s^{*},t))$ and $|P(s^{*},t)|<|P|$, which contradicts that $P$ is a
shortest cheapest $S_{I}$–$T_{I}$ path in $D[I]$. If $P$ uses $(t^{*},y)\in
A_{2}[I]\setminus A^{\prime}_{2}[I]$, we can similarly show that $P(s,t^{*})$
is an $S_{I}$–$T_{I}$ path that is at least as cheap as $P$ and shorter than
$P$. ∎

While we cannot determine $S_{I}$ and $T_{I}$, we can determine $S_{I}\cup
T_{I}$ as $S_{I}\cup T_{I}=\\{\,s\in E\setminus
I\mid{r_{\mathrm{sum}}}(I+s)\geq 2|I|+1\,\\}$. We now provide a search
algorithm with the rank sum oracle. Its description is given as Algorithm 3.
For any $s\in S_{I}$ (resp., $s\in T_{I}$), it emulates the Bellman–Ford
algorithm in $D^{\prime}[I]$ (resp., in the inverse of $D^{\prime}[I]$) rooted
at $s$ without knowing $D^{\prime}[I]$ explicitly. Since there is no negative
cost cycle in $D^{\prime}[I]$ by Lemma 2.5, the algorithm finds shortest
cheapest paths from $s$ to all reachable vertices, and it returns a shortest
cheapest $s$–$T_{I}$ path (resp., $s$–$S_{I}$ path) if it exists. By applying
this search algorithm for all $s\in S_{I}\cup T_{I}$, we can obtain a shortest
cheapest $S_{I}$–$T_{I}$ path in $D^{\prime}[I]$, which is also a shortest
cheapest path in $D[I]$ by Lemma 4.1.

For each $e\in E$, the algorithm maintains a sequence $P_{e}$ of distinct
elements of $E$. We will show that $P_{e}$ is an $s$–$e$ path in
$D^{\prime}[I]$. For a sequence $P_{e}$ and an element $e^{\prime}\in
E\setminus P_{e}$, we denote by $P_{e}+e^{\prime}$ the sequence obtained by
appending $e^{\prime}$ to $P_{e}$.

Input : A finite set $E$, a weight function $w\colon E\to{\mathbb{R}}$, which
defines $c\colon E\to{\mathbb{R}}$ by (2.1), oracle access to
${r_{\mathrm{sum}}}\colon 2^{E}\to{\mathbb{Z}}_{\geq 0}$, a $w$-maximal set
$I\in{\mathcal{I}}_{1}^{k}\cap{\mathcal{I}}_{2}^{k}$ for some
$k\in\\{0,1,\dots,n-1\\}$, and $s\in S_{I}\cup T_{I}$.

Output : For $s\in S_{I}$ (resp., $s\in T_{I}$), a shortest cheapest
$s$–$T_{I}$ path (resp., $s$–$S_{I}$ path) in $D^{\prime}[I]$ (resp, in the
inverse of $D^{\prime}[I]$) with respect to $c$ if one exists, or a message
_“No”_ otherwise.

1

2Set $P_{s}\leftarrow s$, and $P_{e}\leftarrow{\mathsf{null}}$ for each $e\in
E-s$.

3For $\ell=1,2,\dots,n-1$, do the following.

If $\ell$ is odd:

For each $y\in I$, do the following.

  * •

Let $x\in E\setminus I$ minimize $c(P_{x})$ subject to
$P_{x}\neq{\mathsf{null}}$, $y\not\in P_{x}$, and

$\displaystyle(*)\quad{r_{\mathrm{sum}}}(I\triangle
P_{x})=2|I|+1,\quad{r_{\mathrm{sum}}}(I\triangle(P_{x}+y))=2|I|.$

  * •

If $c(P_{x}+y)<c(P_{y})$, update $P_{y}\leftarrow P_{x}+y$.

If $\ell$ is even:

For each $x\in E\setminus I$, do the following.

  * •

Let $y\in I$ minimize $c(P_{y})$ subject to $P_{y}\neq{\mathsf{null}}$,
$x\not\in P_{y}$, and

$\displaystyle(**)\quad$
$\displaystyle[~{}{r_{\mathrm{sum}}}(I+x)=2|I|,~{}{r_{\mathrm{sum}}}(I\triangle(P_{y}+x))=2|I|+1~{}]~{}\text{or}$
$\displaystyle[~{}{r_{\mathrm{sum}}}(I+x)=2|I|+1,~{}{r_{\mathrm{sum}}}(I\triangle(P_{y}+x))=2|I|+2~{}].$

  * •

If $c(P_{y}+x)<c(P_{x})$, update $P_{x}\leftarrow P_{y}+x$.

Let $t\in E\setminus I$ minimize $c(P_{t})$ subject to
${r_{\mathrm{sum}}}(I\triangle P_{t})=2|I|+2$. Return $P_{t}$ if
$c(P_{t})\neq\infty$, and otherwise return _“No”_.

Algorithm 3 (EmulatingBellmanFord$[E,c,{r_{\mathrm{sum}}},I,s]$).

###  4.2 Correctness of the Search

The following lemma shows an important property of Algorithm 3, where we can
assume that $s$ belongs to $S_{I}=\\{\,s\in E\setminus I\mid
I+s\in{\mathcal{I}}_{1}\,\\}$ by symmetry. (For $s\in T_{I}=\\{\,s\in
E\setminus I\mid I+s\in{\mathcal{I}}_{2}\,\\}$, replace $D^{\prime}[I]$ with
its inverse in the arguments.)

######  Lemma 4.2.

Let $s\in S_{I}$ and take any $\ell=1,2,\dots,n-1$. For any $e\in E$, just
after the $\ell$th updating process of Step 2 of Algorithm 3, the sequence
$P_{e}$ is a shortest cheapest $s$–$e$ path in $D^{\prime}[I]$ subject to
$|P_{e}|\leq\ell+1$, where $P_{e}={\mathsf{null}}$ means that there is no such
path.

###### Proof.

We use induction on $\ell$. Note that the statement holds if $\ell=0$. We show
the statement for any $\ell>0$ assuming that it holds for $\ell-1$. We use the
following two claims.

######  Claim 4.3.

Suppose that, for any $e$, $P_{e}$ is a shortest cheapest $s$–$e$ path in
$D^{\prime}[I]$ subject to $|P_{e}|\leq\ell$. Then, for any $y\in I$ and $x\in
E\setminus I$ such that [$P_{x}\neq{\mathsf{null}}$, $y\not\in P_{x}$, and
$c(P_{x}+y)<c(P_{y})$], condition $(\ast)$ holds if and only if $(x,y)\in
A^{\prime}_{2}[I]$.

######  Claim 4.4.

Suppose that, for any $e$, $P_{e}$ is a shortest cheapest $s$–$e$ path in
$D^{\prime}[I]$ subject to $|P_{e}|\leq\ell$. Then, for any $x\in E\setminus
I$ and $y\in I$ such that [$P_{y}\neq{\mathsf{null}}$, $x\not\in P_{y}$, and
$c(P_{y}+x)<c(P_{x})$], condition $(\ast\ast)$ holds if and only if $(y,x)\in
A^{\prime}_{1}[I]$.

We postpone the proofs of these claims and complete the proof of the lemma
relying on them. For any $e\in E$, let $P^{\ell-1}_{e}$ and $P^{\ell}_{e}$ be
the sequence $P_{e}$ just after the $(\ell-1)$th and $\ell$th process,
respectively. By induction, $P^{\ell-1}_{e}$ is a shortest cheapest $s$–$e$
path in $D^{\prime}[I]$ subject to $|P_{e}|\leq\ell$. Let $P^{*}_{e}$ be any
shortest cheapest $s$–$e$ path in $D^{\prime}[I]$ subject to
$|P^{*}_{e}|\leq\ell+1$.

By the “only if” parts of Claims 4.3 and 4.4, $P^{\ell}_{e}$ is an $s$–$e$
path in $D^{\prime}[I]$ with $|P^{\ell}_{e}|\leq\ell+1$, and hence
$c(P^{*}_{e})\leq c(P^{\ell}_{e})$. Also, $c(P^{\ell}_{e})\leq
c(P^{\ell-1}_{e})$ by the algorithm. If $c(P^{*}_{e})=c(P^{\ell-1}_{e})$, then
$P^{\ell}_{e}=P^{\ell-1}_{e}$ and the statement immediately follows.
Otherwise, $c(P^{*}_{e})<c(P^{\ell-1}_{e})$. This implies
$|P^{*}_{e}|=\ell+1$. Then $e\in I$ if $\ell$ is odd and $e\in E\setminus I$
if $e$ is even (recall that $D^{\prime}[I]$ is a bipartite digraph between
$E\setminus I$ and $I$). Let $e^{\prime}$ be the second last element in
$P^{*}_{e}$ and let $P^{*}_{e^{\prime}}:=P^{*}_{e}-e$ (i.e., delete $e$ from
$P^{*}_{e}$). Then $P^{*}_{e^{\prime}}$ is an $s$–$e^{\prime}$ path with
$|P_{e^{\prime}}|=\ell$, and hence $c(P^{\ell-1}_{e^{\prime}})\leq
c(P^{*}_{e^{\prime}})$. So $c(P^{\ell-1}_{e^{\prime}}+e)\leq
c(P^{*}_{e})<c(P^{\ell-1}_{e})$. If $\ell$ is odd, then $(e^{\prime},e)\in
A^{\prime}_{2}[I]$, and hence ($\ast$) holds with $x:=e^{\prime}$ and $y:=e$
by Claim 4.3. If $\ell$ is even, then $(e^{\prime},e)\in A^{\prime}_{1}[I]$,
and hence ($\ast\ast$) holds with $y:=e^{\prime}$ and $x:=e$ by Claim 4.4. In
either case, we obtain $c(P^{\ell}_{e})\leq
c(P^{*}_{e^{\prime}}+e)=c(P^{*}_{e})$ and
$|P^{\ell}_{e}|\leq\ell+1=|P^{*}_{e}|$. Hence $P^{\ell}_{e}$ is a shortest
cheapest $s$–$e$ path subject to $|P_{e}|\leq\ell+1$. ∎

In what follows, we prove Claims 4.3 and 4.4. First, we need the following
lemma.

######  Lemma 4.5.

Let $s\in S_{I}$. At any moment of the algorithm, the following conditions
hold.

  1. (a)

Any $y\in I$ with $P_{y}\neq{\mathsf{null}}$ satisfies $|I\triangle
P_{y}|=|I|$, $r_{1}(I\triangle P_{y})=|I|$, and $r_{2}(I\triangle P_{y})=|I|$.

  2. (b)

Any $x\in E\setminus I$ with $P_{x}\neq{\mathsf{null}}$ satisfies $|I\triangle
P_{x}|=|I|+1$, $r_{1}(I\triangle P_{x})=|I|+1$, and $r_{2}(I\triangle
P_{x})\geq|I|$. Moreover, it satisfies $r_{2}(I\triangle P_{x})=|I|+1$ if and
only if $x\in T_{I}$.

  3. (c)

For each $e\in E$ with $P_{e}\neq{\mathsf{null}}$, we have $(P_{e}-s)\cap
S_{I}=\emptyset$ and $(P_{e}-e)\cap T_{I}=\emptyset$.

###### Proof.

By the algorithm, for each $e\in E$ with $P_{e}\neq{\mathsf{null}}$, the
sequence $P_{e}$ starts with $s\in E\setminus I$ and uses elements in
$E\setminus I$ and $I$ alternately. Then $|I\triangle P_{y}|=|I|$ for any
$y\in I$ with $P_{y}\neq{\mathsf{null}}$ and $|I\triangle P_{x}|=|I|+1$ for
any $x\in E\setminus I$ with $P_{x}\neq{\mathsf{null}}$. For any $y\in I$,
after $P_{y}$ is updated, it satisfies ${r_{\mathrm{sum}}}(I\triangle
P_{y})=2|I|$ by the condition ($\ast$) for update. Then (a) follows.

For any $e\in E\setminus I$ with $P_{e}\neq{\mathsf{null}}$, any
$x^{\prime}\in(P_{e}\setminus I)-e$ has some succeeding element $y^{\prime}\in
I$ in $P_{e}$ and ($\ast$) holds for $x^{\prime}$ and $y^{\prime}$. Hence
${r_{\mathrm{sum}}}(I\triangle P_{x^{\prime}})=2|I|+1$. If $x^{\prime}=s\in
S_{I}$, it immediately implies $x^{\prime}\not\in T_{I}$. If $x^{\prime}\neq
s$, then $x^{\prime}$ has some preceding element $y^{\prime\prime}$ in
$P_{x}$, and ($\ast\ast$) for $y^{\prime\prime}$ and $x^{\prime}$ implies
${r_{\mathrm{sum}}}(I+x^{\prime})=2|I|$, and hence $x^{\prime}\not\in
S_{I}\cup T_{I}$. Thus, $s\in S_{I}\setminus T_{I}$ and any
$x^{\prime}\in(P_{e}\setminus I)-s-e$ satisfies $x^{\prime}\not\in S_{I}\cup
T_{I}$.

For any $x\in(E\setminus I)-s$ with $P_{x}\neq{\mathsf{null}}$, by
($\ast\ast$) for $x$ and its preceding element $y$, we have
$[{r_{\mathrm{sum}}}(I+x)=2|I|,{r_{\mathrm{sum}}}(I\triangle P_{x})=2|I|+1]$
or $[{r_{\mathrm{sum}}}(I+x)=2|I|+1,{r_{\mathrm{sum}}}(I\triangle
P_{x})=2|I|+2]$. In the former case, ${r_{\mathrm{sum}}}(I+x)=2|I|$ implies
$x\not\in S_{I}\cup T_{I}$, and hence $P_{x}\cap T_{I}=\emptyset$. This
implies $r_{2}(I\triangle P_{x})\leq r_{2}(I\cup P_{x})=|I|$, and then
${r_{\mathrm{sum}}}(I\triangle P_{x})=2|I|+1$ implies $r_{1}(I\triangle
P_{x})=|I|+1$ and $r_{2}(I\triangle P_{x})=|I|$. In the latter case,
${r_{\mathrm{sum}}}(I\triangle P_{x})=2|I|+2$ implies $r_{1}(I\triangle
P_{x})=r_{2}(I\triangle P_{x})=|I|+1$. Since any $x^{\prime}\in(P_{x}\setminus
I)-x$ satisfies $x^{\prime}\not\in T_{I}$ (as seen in the previous paragraph),
we must have $x\in T_{I}$, and then $x\not\in S_{I}$ follows from
${r_{\mathrm{sum}}}(I+x)=2|I|+1$. Thus, (b) and (c) are shown. ∎

Now we are ready to show Claims 4.3 and 4.4. We sometimes denote by $V(P)$ the
set of elements in a sequence $P$ for emphasizing that we focus on the set
rather than the sequence.

###### Proof of Claim 4.3.

By Lemma 4.5(b), ${r_{\mathrm{sum}}}(I\triangle P_{x})=2|I|+1$ is equivalent
to $x\not\in T_{I}$. Lemma 4.5(b) also implies $r_{1}(I\triangle
P_{x})=|I|+1=|I\triangle P_{x}|$, and hence
$r_{1}(I\triangle(P_{x}+y))=r_{1}((I\triangle P_{x})-y)=|I|$. Therefore,
${r_{\mathrm{sum}}}(I\triangle(P_{x}+y))=2|I|$ is equivalent to
$r_{2}(I\triangle(P_{x}+y))=|I|=|I\triangle(P_{x}+y)|$, i.e.,
$I\triangle(P_{x}+y)\in{\mathcal{I}}_{2}$. Then, the condition $(\ast)$ is
equivalent to

$\displaystyle(*)^{\prime}\quad x\not\in T_{I},\quad
I\triangle(P_{x}+y)\in{\mathcal{I}}_{2}.$

We show that $(\ast)^{\prime}$ holds if and only if $(x,y)\in
A^{\prime}_{2}[I]$. By induction hypothesis, $P_{x}$ is an $s$–$x$ path in
$D^{\prime}[I]$, and hence it uses arcs of $A^{\prime}_{2}[I]$ and
$A^{\prime}_{1}[I]$ alternately. Let $N_{1}$ and $N_{2}$ be the sets of those
arcs of $A^{\prime}_{1}[I]$ and $A^{\prime}_{2}[I]$, respectively. Since $x\in
E\setminus I$, $N_{1}$ forms a matching that covers $V(P_{x})-s$ and $N_{2}$
forms a matching that covers $V(P_{x})-x$.

To show the “if” part, suppose $(x,y)\in A^{\prime}_{2}[I]$. Then $x\not\in
T_{I}$ by the definition of $A^{\prime}_{2}[I]$. Also,
$N^{\prime}_{2}:=N_{2}+(x,y)\subseteq A^{\prime}_{2}[I]$ forms a perfect
matching on $V(P_{x}+y)$. Suppose conversely that
$I\triangle(P_{x}+y)\not\in{\mathcal{I}}_{2}$. Then Lemma 2.4 implies that
$A_{2}[I]$ contains some other perfect matching $N^{\prime\prime}_{2}$ on
$V(P_{x}+y)$. We see that $N^{\prime\prime}_{2}\subseteq A^{\prime}_{2}[I]$
because $(P_{x}+y)\cap T_{I}=\emptyset$ by Lemma 4.5(c) and $x\not\in T_{I}$.
Thus, $N^{\prime}_{2}$, $N^{\prime\prime}_{2}$, and $N_{1}$ are all contained
in $D^{\prime}[I]$. Consider the digraph $D=(V(P_{x}+y),A)$ whose arc set $A$
consists of the arcs in $N^{\prime}_{2}$, $N^{\prime\prime}_{2}$, and two
copies of $N_{1}$, where we consider their multiplicity, i.e., each arc in
$(N^{\prime}_{2}\cap N^{\prime\prime}_{2})\cup N_{1}$ is taken twice
(parallel). Since $N^{\prime\prime}_{2}\neq N^{\prime}_{2}$, there exists an
arc in $N^{\prime\prime}_{2}$ whose head precedes its tail on the path
$P_{x}+y$. Then $D$ contains at least one directed cycle. The indegree and
outdegree of each vertex in $D$ are given as $(d^{\rm in}(s),d^{\rm
out}(s))=(0,2)$, $(d^{\rm in}(y),d^{\rm out}(y))=(2,0)$, and $(d^{\rm
in}(e),d^{\rm out}(e))=(2,2)$ for all the other vertices $e$. Then $A$ can be
decomposed into the arc sets of two $s$–$y$ paths and one or more cycles. Let
$P_{1}$ and $P_{2}$ be those $s$–$y$ paths and $\mathcal{Q}$ be the set of
those cycles (where paths and cycles are sequences of vertices). Then each
vertex in $V(P_{x}+y)$ is used exactly twice in this decomposition, and hence

$\textstyle{c(P_{1})+c(P_{2})+\sum_{Q\in\mathcal{Q}}c(Q)=2c(P_{x}+y).}$

Since $D^{\prime}[I]$ has no negative cycle, this implies
$c(P_{1})+c(P_{2})\leq 2c(P_{x}+y)$. Also, $\mathcal{Q}\neq\emptyset$ implies
$V(P_{1})\subsetneq V(P_{x}+y)$ or $V(P_{2})\subsetneq v(P_{x}+y)$. In case
$V(P_{1})=V(P_{x}+y)$, we have $V(P_{2})\subsetneq V(P_{x}+y)$, which implies
$|P_{2}|<|P_{x}+y|\leq\ell+1$ because $|P_{x}|\leq\ell$ holds by induction.
Also, $V(P_{1})=V(P_{x}+y)$ implies $c(P_{2})\leq c(P_{x}+y)$, where
$c(P_{x}+y)<c(P_{y})$ by assumption. Thus, $P_{2}$ is an $s$–$y$ path in
$D^{\prime}[I]$ with $c(P_{2})<c(P_{y})$ and $|P_{2}|\leq\ell$, which
contradicts the induction hypothesis that $P_{y}$ is a shortest cheapest
$s$–$y$ path subject to $|P_{y}|\leq\ell$. The case $V(P_{2})=V(P_{x}+y)$ is
similar. In case $V(P_{1})\subsetneq V(P_{x}+y)$ and $V(P_{2})\subsetneq
V(P_{x}+y)$, both $P_{1}$ and $P_{2}$ satisfy $|P_{i}|\leq\ell$ and at least
one of them, say $P_{i}$, satisfies $c(P_{i})\leq c(P_{x}+y)<c(P_{y})$, which
again contradicts the induction hypothesis on $P_{y}$.

We next show the “only if” part. Let $(\ast)^{\prime}$ hold. By
$I\triangle(P_{x}+y)\in{\mathcal{I}}_{2}$, Lemma 2.3 implies that $A_{2}[I]$
contains a perfect matching $N^{\prime}_{2}$ on $V(P_{x}+y)$. Also,
$N^{\prime}_{2}\subseteq A^{\prime}_{2}[I]$ because $(P_{x}+y)\cap
T_{I}=\emptyset$ by Lemma 4.5(c) and $x\not\in T_{I}$. Thus, $N_{2}$,
$N^{\prime}_{2}$, and $N_{1}$ are all contained in $D^{\prime}[I]$. Consider
the digraph $D^{*}=(V(P_{x}+y),A^{*})$ whose arc set $A^{*}$ consists of the
arcs in $N_{2}$, $N^{\prime}_{2}$, and two copies of $N_{1}$, where we
consider their multiplicity as before. Conversely, suppose that $(x,y)\not\in
A^{\prime}_{2}[I]$. Then $(x,y)\not\in N^{\prime}_{2}$. Since $N^{\prime}_{2}$
covers $V(P_{x}+y)$, it has an arc whose tail is $x$ and whose head precedes
$x$ in the path $P_{x}+y$. Then $D^{*}$ contains at least one directed cycle.
Note that $(d^{\rm in}(s),d^{\rm out}(s))=(0,2)$, $(d^{\rm in}(x),d^{\rm
out}(x))=(2,1)$, $(d^{\rm in}(y),d^{\rm out}(y))=(1,0)$, and $(d^{\rm
in}(e),d^{\rm out}(e))=(2,2)$ for all the other vertices $e$ in $D^{*}$. Then
$A^{*}$ can be decomposed into the arc sets of one $s$–$x$ path, one $s$–$y$
path, and one or more cycles. Let $R_{x}$, $R_{y}$, and $\mathcal{Q}^{\prime}$
be that $s$–$x$ path, $s$–$y$ path, and the set of cycles, respectively. Then
each vertex in $V(P_{x}+y)-y$ is used twice and $y$ is used once in this
decomposition, and hence

$\textstyle{c(R_{x})+c(R_{y})+\sum_{Q\in\mathcal{Q}^{\prime}}c(Q)=c(P_{x})+c(P_{x}+y).}$

Since $D^{\prime}[I]$ has no negative cost cycle, $c(R_{x})+c(R_{y})\leq
c(P_{x})+c(P_{x}+y)$. Also, $\mathcal{Q}\neq\emptyset$ implies
$V(R_{x})\subsetneq V(P_{x})$ or $V(R_{y})\subsetneq v(P_{x}+y)$. If
$V(R_{x})=V(P_{x})$, then $V(R_{y})\subsetneq V(P_{x}+y)$, which implies
$|R_{y}|<|P_{x}+y|\leq\ell+1$. Also, $V(R_{x})=V(P_{x})$ implies $c(R_{y})\leq
c(P_{x}+y)<c(P_{y})$. Thus, $R_{y}$ is an $s$–$y$ path with
$c(R_{y})<c(P_{y})$ and $|R_{y}|\leq\ell$, which contradicts the induction
hypothesis on $P_{y}$. In case $V(R_{y})=V(P_{x}+y)$, we have
$V(R_{x})\subsetneq V(P_{x})$, which implies $|R_{x}|<|P_{x}|$. Also,
$V(R_{y})=V(P_{x}+y)$ implies $c(R_{x})\leq c(P_{x})$. Thus, $R_{x}$ is an
$s$–$x$ path with $c(R_{x})\leq c(P_{x})$ and $|R_{x}|<|P_{x}|$, which
contradicts the induction hypothesis on $P_{x}$. In case $V(R_{x})\subsetneq
V(P_{x})$ and $V(R_{y})\subsetneq V(P_{x}+y)$, we have $|R_{x}|<|P_{x}|$ and
$|R_{y}|\leq\ell$. Also, we have $c(R_{x})\leq c(P_{x})$ or $c(R_{y})\leq
c(P_{x}+y)<c(P_{y})$, and each of them yields a contradiction. ∎

###### Proof of Claim 4.4.

Since $I\triangle(P_{y}+x)=(I\triangle P_{y})+x$, Lemma 4.5(a) implies
$|I\triangle(P_{y}+x)|=|I|+1$, $r_{1}(I\triangle(P_{y}+x))\geq|I|$, and
$r_{2}(I\triangle(P_{y}+x))\geq|I|$. Also, by Lemma 4.5(c), we have $P_{y}\cap
T_{I}=\emptyset$ (which implies $\mathrm{cl}_{2}(I)=\mathrm{cl}_{2}(I\triangle
P_{y})$), and hence $r_{2}(I\triangle(P_{y}+x))=|I|+1$ holds if and only if
$x\in T_{I}$. If $x\not\in T_{I}$ (resp., $x\in T_{I}$), then
${r_{\mathrm{sum}}}(I\triangle(P_{y}+x))=2|I|+1$ (resp.,
${r_{\mathrm{sum}}}(I\triangle(P_{y}+x))=2|I|+2$) is equivalent to
$r_{1}(I\triangle(P_{y}+x))=|I|+1$, and also ${r_{\mathrm{sum}}}(I+x)=2|I|$
(resp., ${r_{\mathrm{sum}}}(I+x)=2|I|+1$) is equivalent to $x\not\in S_{I}$.
Therefore, $(\ast\ast)$ is equivalent to

$\displaystyle(**)^{\prime}\quad x\not\in S_{I},\quad
I\triangle(P_{y}+x)\in{\mathcal{I}}_{1}.$

We show that $(\ast\ast)^{\prime}$ holds if and only if $(y,x)\in
A^{\prime}_{1}[I]$. By induction hypothesis, $P_{y}$ is an $s$–$y$ path in
$D^{\prime}[I]$, and hence it uses arcs of $A^{\prime}_{2}[I]$ and
$A^{\prime}_{1}[I]$ alternately. Let $N_{1}$ and $N_{2}$ be the sets of those
arcs of $A^{\prime}_{1}[I]$ and $A^{\prime}_{2}[I]$, respectively. Then
$N_{1}$ forms a matching that covers $V(P_{y})-y-s$ and $N_{2}$ forms a
matching that covers $V(P_{y})$.

To show the “if” part, suppose $(y,x)\in A^{\prime}_{1}[I]$. Then $x\not\in
S_{I}$ by the definition of $A^{\prime}_{1}[I]$. Also,
$N^{\prime}_{1}:=N_{1}+(y,x)\subseteq A^{\prime}_{1}[I]$ forms a perfect
matching on $V(P_{y}+x)-s$. Suppose conversely that
$I\triangle(P_{y}+x)\not\in{\mathcal{I}}_{1}$. It implies
$I\triangle(P_{y}+x-s)\not\in{\mathcal{I}}_{1}$ as follows. Lemma 4.5(c)
implies $(P_{y}+x)\cap S_{I}=\\{s\\}$, and hence
$\mathrm{cl}_{1}(I\triangle(P_{y}+x-s))\subseteq\mathrm{cl}_{1}(I)$. If
$\mathrm{cl}_{1}(I\triangle(P_{y}+x-s))=\mathrm{cl}_{1}(I)$, then
$\mathrm{cl}_{1}(I\triangle(P_{y}+x))=\mathrm{cl}_{1}(I+s)$, and
$I\triangle(P_{y}+x)\in{\mathcal{I}}_{1}$ as $I+s\in{\mathcal{I}}_{1}$, a
contradiction. Thus, we have
$\mathrm{cl}_{1}(I\triangle(P_{y}+x-s))\subsetneq\mathrm{cl}_{1}(I)$, which
implies $I\triangle(P_{y}+x-s)\not\in{\mathcal{I}}_{1}$. Then Lemma 2.4
implies that $A_{1}[I]$ contains some other perfect matching
$N^{\prime\prime}_{1}$ on $V(P_{y}+x)-s$. We see that
$N^{\prime\prime}_{1}\subseteq A^{\prime}_{1}[I]$ because $(P_{y}+x-s)\cap
S_{I}=\emptyset$ by Lemma 4.5(b) and $x\not\in S_{I}$. Thus, $N^{\prime}_{1}$,
$N^{\prime\prime}_{1}$, and $N_{2}$ are all contained in $D^{\prime}[I]$.
Consider the digraph $D=(V(P_{x}+y),A)$ whose arc set $A$ consists of the arcs
in $N^{\prime}_{1}$, $N^{\prime\prime}_{1}$, and two copies of $N_{2}$, where
we consider their multiplicity as before. Similarly to the proof of Claim 4.3,
we see that there exists an $s$–$y$ path $P$ in $D^{\prime}[I]$ with
$c(P)<c(P_{x})$ and $|P|\leq\ell$, which contradicts the induction hypothesis
on $P_{x}$.

We next show the “only if” part. Let $(\ast\ast)^{\prime}$ hold. By
$I\triangle(P_{y}+x-s)\subseteq I\triangle(P_{y}+x)\in{\mathcal{I}}_{1}$,
Lemma 2.3 implies that $A_{1}[I]$ contains a perfect matching $N^{\prime}_{1}$
on $V(P_{y}+x)-s$. Also, $N^{\prime}_{1}\subseteq A^{\prime}_{1}[I]$ because
$(P_{y}+x-s)\cap S_{I}=\emptyset$ by Lemma 4.5(c) and $x\not\in S_{I}$. Thus,
$N_{1}$, $N^{\prime}_{1}$, and $N_{2}$ are all contained in $D^{\prime}[I]$.
Consider the digraph $D^{*}=(V(P_{x}+y),A^{*})$ whose arc set $A^{*}$ consists
of the arcs in $N_{1}$, $N^{\prime}_{1}$, and two copies of $N_{2}$, where we
consider their multiplicity as before. Then, similarly to the proof of Claim
4.3, we see that there exists an $s$–$y$ or $s$–$x$ path whose property
contradicts the induction hypothesis on $P_{y}$ or $P_{x}$. ∎

######  Lemma 4.6.

The output of EmulatingBellmanFord$[E,c,{r_{\mathrm{sum}}},I,s]$ is always
correct.

###### Proof.

For any $e\in E$, a shortest cheapest $s$–$e$ path $P$ satisfies $|P|\leq n$.
Then, after the $(n-1)$th updating process, $P_{e}$ is indeed a shortest
cheapest $s$–$e$ path by Lemma 4.2. Also, when some path is returned, it is a
shortest cheapest $s$–$T_{I}$ path by Lemma 4.5(b). ∎

###  4.3 Matroid Intersection Algorithm under Rank Sum Oracle

Using Algorithm 3 as a subroutine, we can emulate
CheapestPathAugment$[E,w,{\mathcal{I}}_{1},{\mathcal{I}}_{2},I]$ as Algorithm
4.

Input : A finite set $E$, a weight function $w\colon E\to{\mathbb{R}}$, oracle
access to ${r_{\mathrm{sum}}}\colon 2^{E}\to{\mathbb{Z}}_{\geq 0}$, and a
$w$-maximal set $I\in{\mathcal{I}}_{1}^{k}\cap{\mathcal{I}}_{2}^{k}$ for some
$k=0,1,\dots,n-1$.

Output : A $w$-maximal set
$J\in{\mathcal{I}}_{1}^{k+1}\cap{\mathcal{I}}_{2}^{k+1}$ if one exists, or a
message _“No”_.

1

2Determine the set $S_{I}\cup T_{I}=\\{\,s\in E\setminus
I\mid{r_{\mathrm{sum}}}(I+s)\geq 2|I|+1\,\\}$. Define a cost function $c\colon
E\to{\mathbb{R}}$ by (2.1).

3For each $s\in S_{I}\cup T_{I}$, apply
EmulatingBellmanFord$[E,c,{r_{\mathrm{sum}}},I,s]$.

If some path is returned in Step 2, then let $P$ be a shortest cheapest one
among all returned paths, and return $J=I\triangle P$. Otherwise, return a
message _“No”_.

Algorithm 4
(CheapestPathAugmentRankSum$[E,w,{\mathcal{I}}_{1},{\mathcal{I}}_{2},I]$).

The following theorem concludes the section.

######  Lemma 4.7.

The output of
CheapestPathAugmentRankSum$[E,w,{\mathcal{I}}_{1},{\mathcal{I}}_{2},I]$ is
always correct.

###### Proof.

The correctness of Algorithm 4 immediately follows from Lemmas 4.1 and 4.6. ∎

Lemma 4.7 completes the proof of Theorem 1.1.

###### Proof of Theorem 1.1.

Starting from $I=\emptyset$, the size of the common independent set can be
gradually increased using
CheapestPathAugmentRankSum$[E,w,{\mathcal{I}}_{1},{\mathcal{I}}_{2},I]$ until
$I$ becomes a common independent set of maximum cardinality. The correctness
of the algorithm follows from Lemma 4.7. Note that, if we are asked to find a
maximum-weight common independent set, then it suffices to output one with
maximum weight among the obtained $w$-maximal common independent sets. ∎

##  5 Matroid Intersection under Common Independence Oracle

As discussed in Section 3, the common independence oracle is strictly weaker
than the minimum rank and the rank sum oracles. As weighted matroid
intersection turned out to be tractable for the rank sum oracle, the
complexity of the problem under the common independence oracle is especially
interesting.

In what follows, we present an algorithm for the unweighted matroid
intersection problem when one of the matroids is a partition matroid, and an
algorithm for the weighted matroid intersection problem when one of the
matroids is an elementary split matroid. We also show that the common
independence oracle, when complemented with the rank oracle, is strong enough
to design an algorithm similar to that for the rank sum case.

###  5.1 Intersection with Partition Matroid

The aim of this section is to show that the unweighted matroid intersection
problem is tractable under the common independence oracle when
${\mathbf{M}}_{1}$ is a partition matroid with all-one upper bound on the
partition classes, that is, when ${\mathcal{I}}_{1}$ is represented as
${\mathcal{I}}_{1}=\\{\,I\subseteq E\mid|I\cap E_{i}|\leq 1\ \text{for
$i=1,\dots,q$}\,\\}$ for some partition $E=E_{1}\cup\dots\cup E_{q}$. We will
provide an algorithm that emulates Algorithm 1, i.e.,
Augment$[E,{\mathcal{I}}_{1},{\mathcal{I}}_{2},I]$, using only the common
independence oracle.

Take any $k=0,1,\dots,n-1$ and let
$I\in{\mathcal{I}}_{1}^{k}\cap{\mathcal{I}}_{2}^{k}$. To emulate Algorithm 1,
we want to find a shortest $S_{I}$–$T_{I}$ path in the exchangeability graph
$D[I]=(E\setminus I,I;A_{1}[I]\cup A_{2}[I])$. With only the common
independence oracle, however, we cannot construct $D[I]$, and cannot determine
even $S_{I}$ or $T_{I}$.

Note that a shortest $S_{I}$–$T_{I}$ path in $D[I]$ never uses arcs entering
sources or leaving sinks. Therefore, finding a shortest $S_{I}$–$T_{I}$ path
in $D[I]$ is equivalent to finding it in $D^{\prime}[I]$, where
$D^{\prime}[I]$ is the subgraph of $D[I]$ obtained by removing those arcs from
$D[I]$ (it is used also in Section 4). We now provide a search procedure,
described as Algorithm 5, that will be used as a subroutine for our
augmentating procedure. If a given element $s$ belongs to $S_{I}$, this search
algorithm works like the breadth first search in $D^{\prime}[I]$ rooted at
$s$, and returns a shortest $s$–$T_{I}$ path or certifies the nonexistence of
such a path.

In Algorithm 5, for each $y\in I$, a sequence $P_{y}$ of distinct elements is
defined. In our analysis, $P_{y}$ will turn out to be a shortest $s$–$y$ path
in $D^{\prime}[I]$. We use the notation $P_{y}+x$ to denote the sequence
obtained by appending an element $x$ to $P_{y}$.

Input : Oracle access to ${\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ where
${\mathcal{I}}_{1}$ is the independent set family of a partition matroid, a
common independent set $I\in{\mathcal{I}}^{k}_{1}\cap{\mathcal{I}}^{k}_{2}$,
and an element $s\in E\setminus I$.

Output : A sequence $P$ with $I\triangle
P\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ and $|I\triangle P|=k+1$ if one
exists, or a message _“No”_ otherwise. In particular, if $s\in S_{I}$ and
$D^{\prime}[I]$ has an $s$–$T_{I}$ path, then a shortest $s$–$T_{I}$ path is
returned.

1

2If $I+s\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$, halt with returning $s$.

3For each $y\in I$, set $P_{y}\leftarrow sy$ if
$I+s-y\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$, and
$P_{y}\leftarrow{\mathsf{null}}$ otherwise.

For $\ell=1,2,\dots$, do the following.

  1. (i)

If there is no $y\in I$ with $|P_{y}|=2\ell$, halt with returning _“No”_.

  2. (ii)

If there exist $y^{\prime}\in I$ and $x\in E\setminus I$ such that
$|P_{y^{\prime}}|=2\ell$, $x\not\in P_{y^{\prime}}$,
$\\{y^{\prime},x\\}\not\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$, and
$I\triangle(P_{y^{\prime}}+x)\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$, then
halt with returning $P_{y^{\prime}}+x$.

  3. (iii)

For each $y\in I$ with $P_{y}={\mathsf{null}}$, if there exist $y^{\prime}\in
I$ and $x\in E\setminus I$ such that $|P_{y^{\prime}}|=2\ell$, $x\not\in
P_{y^{\prime}}$,
$\\{y^{\prime},x\\}\not\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$, and
$I\triangle(P_{y^{\prime}}+x+y)\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$,
then $P_{y}\leftarrow P_{y^{\prime}}+x+y$.

Algorithm 5 (EmulatingBFS$[E,{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2},I,s]$).

By the algorithm, it is clear that the output is either a sequence $P$ with
$I\triangle P\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ and $|I\triangle
P|=k+1$ or a message _“No”_. Also, if $s\in S_{I}\cap T_{I}$, we see that $s$
itself is a shortest $s$–$T_{I}$ path and is returned at Step 1. Therefore, we
assume $s\in S_{I}\setminus T_{I}$ and show that a shortest $s$–$T_{I}$ path
is returned if such a path exists. We denote by $\operatorname{dist}(s,T_{I})$
the length (i.e., the number of vertices) of a shortest $s$–$T_{I}$ path in
$D^{\prime}[I]$ and by $\operatorname{dist}(s,y)$ the length of a shortest
$s$–$y$ path in $D^{\prime}[I]$ for each $y\in I$. Note that
$\operatorname{dist}(s,T_{I})$ is odd and $\operatorname{dist}(s,y)$ is even
for any $y\in I$.

######  Lemma 5.1.

Let $s\in S_{I}\setminus T_{I}$. The following hold for any $y\in I$ and any
$\ell=1,2,\dots$.

  1. (a)

$P_{y}$ is defined in Step 2 if and only if $\operatorname{dist}(s,y)=2$. If
defined, it is a shortest $s$–$y$ path in $D^{\prime}[I]$.

  2. (b)

A sequence is returned in the $\ell$th process of Step 3(ii) if and only if
$\operatorname{dist}(s,T_{I})=2\ell+1$. The returned sequence is a shortest
$s$–$T_{I}$ path in $D^{\prime}[I]$.

  3. (c)

$P_{y}$ is defined in the $\ell$th process of Step 3(iii) if and only if
$\operatorname{dist}(s,y)=2\ell+2<\operatorname{dist}(s,T_{I})$. If defined,
it is a shortest $s$–$y$ path in $D^{\prime}[I]$.

###### Proof.

For any $y\in I$, $\operatorname{dist}(s,y)=2$ means $(s,y)\in
A^{\prime}_{2}[I]$, which is equivalent to $I+s-y\in{\mathcal{I}}_{2}$ as
$s\not\in T_{I}$. Since $s\in S_{I}$ implies $I+s-y\in{\mathcal{I}}_{1}$, then
$I+s-y\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ holds if and only if
$(s,y)\in A^{\prime}_{2}[I]$. When $(s,y)\in A^{\prime}_{2}[I]$, clearly $sy$
is a shortest $s$–$y$ path. Thus, (a) is shown.

We show (b) and (c) by induction on $\ell$. Suppose that they hold for
$1,2,\dots,\ell-1$ and we are at the beginning of the $\ell$th process of Step
3. Then $\operatorname{dist}(s,T_{I})\geq 2\ell+1$ because otherwise the
algorithm has halted before. Take any $y^{\prime}\in I$ with
$|P_{y^{\prime}}|=2\ell$. Then

  * •

$P_{y^{\prime}}$ is a shortest $s$–$y^{\prime}$ path in $D^{\prime}[I]$ by (a)
and induction for (c),

  * •

$\mathrm{cl}_{2}(I)=\mathrm{cl}_{2}(I\triangle P_{y^{\prime}})$ because
$|I|=|I\triangle P_{y^{\prime}}|$ and $I\triangle
P_{y^{\prime}}\in{\mathcal{I}}_{2}$ hold by the algorithm (Steps 2 and 3(iii))
and $P_{y^{\prime}}\cap T_{I}=\emptyset$ follows from
$\operatorname{dist}(s,T_{I})\geq 2\ell+1$.

As $P_{y^{\prime}}$ is a path in $D^{\prime}[I]$, it uses arcs in
$A^{\prime}_{2}[I]$ and $A^{\prime}_{1}[I]$ alternately. Let $N_{1}$ and
$N_{2}$ be the sets of those arcs of $A^{\prime}_{1}[I]$ and
$A^{\prime}_{2}[I]$, respectively. By $s\in E\setminus I$ and $y^{\prime}\in
I$, then $N_{1}$ and $N_{2}$ form matchings that cover
$V(P_{y^{\prime}})-s-y^{\prime}$ and $V(P_{y^{\prime}})$, respectively (recall
that we denote by $V(P)$ the set of elements in a sequence $P$ for emphasizing
that we focus on the set rather than the sequence).

Take any $x\in E\setminus I$ with $x\not\in P_{y^{\prime}}$. The following
claim completes the proof of (b).

######  Claim 5.2.

$(y^{\prime},x)\in A^{\prime}_{1}[I]$ and $x\in T_{I}$ if and only if
$\\{y^{\prime},x\\}\not\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ and
$I\triangle(P_{y^{\prime}}+x)\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$.

###### Proof.

For the “only if” part, suppose $(y^{\prime},x)\in A^{\prime}_{1}[I]$ and
$x\in T_{I}$. As $\bf{M}_{1}$ is a partition matroid with all-one upper
bounds, $(y^{\prime},x)\in A^{\prime}_{1}[I]$ means that $\\{y^{\prime},x\\}$
is a circuit in $\bf{M}_{1}$, and hence
$\\{y^{\prime},x\\}\not\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$. Since $s\in
S_{I}$ and $N_{1}+(y^{\prime},x)$ forms a matching that covers
$V(P_{y^{\prime}}+x)-s$, we have
$I\triangle(P_{y^{\prime}}+x)\in{\mathcal{I}}_{1}$. (In
$I\triangle(P_{y^{\prime}}+x)$, each element in $I\cap(P_{y^{\prime}}+x-s)$ is
replaced by another element in the same partition class and $s$ comes from a
partition class whose element is not used in $I$.) Also,
$\mathrm{cl}_{2}(I)=\mathrm{cl}_{2}(I\triangle P_{y^{\prime}})$ and $x\in
T_{I}$ imply $I\triangle(P_{y^{\prime}}+x)=(I\triangle
P_{y^{\prime}})+x\in{\mathcal{I}}_{2}$. Thus, the “only if” part is shown.

For the “if” part, suppose
$\\{y^{\prime},x\\}\not\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ and
$I\triangle(P_{y^{\prime}}+x)\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$. As
$\mathrm{cl}_{2}(I)=\mathrm{cl}_{2}(I\triangle P_{y^{\prime}})$ holds,
$I\triangle(P_{y^{\prime}}+x)\in{\mathcal{I}}_{2}$ implies $x\in T_{I}$. Then
$\\{y^{\prime},x\\}\in{\mathcal{I}}_{2}$, and hence
$\\{y^{\prime},x\\}\not\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ implies that
$\\{y^{\prime},x\\}$ is a circuit in $\bf{M}_{1}$. Thus $(y^{\prime},x)\in
A^{\prime}_{1}[I]$. ∎

Suppose that we are at the beginning of $\ell$th process of Step 3(iii). Take
$y^{\prime}$ and $x$ as before and take any $y\in I$ such that $P_{y}$ is
undefined. Then $\operatorname{dist}(s,y)>2\ell$ by (a) and induction for (c).
Also $(y^{\prime},x)\in A^{\prime}_{1}[I]$ implies $x\not\in T_{I}$ since
otherwise the algorithm has halted at Step 3 (ii). The following claim
completes the proof of (c).

######  Claim 5.3.

Assume that $(y^{\prime},x)\in A^{\prime}_{1}[I]$ implies $x\not\in T_{I}$.
Then $(y^{\prime},x)\in A^{\prime}_{1}[I]$ and $(x,y)\in A^{\prime}_{2}[I]$ if
and only if $\\{y^{\prime},x\\}\not\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$
and $I\triangle(P_{y^{\prime}}+x+y)\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$.

###### Proof.

For the “only if” part, suppose $(y^{\prime},x)\in A^{\prime}_{1}[I]$ and
$(x,y)\in A^{\prime}_{2}[I]$. Similarly to the proof of Claim 5.2,
$(y^{\prime},x)\in A^{\prime}_{1}[I]$ implies
$\\{y^{\prime},x\\}\not\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ and
$I\triangle(P_{y^{\prime}}+x)\in{\mathcal{I}}_{1}$, and hence
$I\triangle(P_{y^{\prime}}+x+y)=(I\triangle(P_{y^{\prime}}+x))-y\in{\mathcal{I}}_{1}$.
Suppose, to the contrary,
$I\triangle(P_{y^{\prime}}+x+y)\not\in{\mathcal{I}}_{2}$. Since
$N_{2}+(x,y)\subseteq A^{\prime}_{2}[I]$ forms a perfect matching on
$V(P_{y^{\prime}}+x+y)$, Lemma 2.4 implies that there exists some other
perfect matching $N^{\prime}_{2}\subseteq A_{2}[I]$ on
$V(P_{y^{\prime}}+x+y)$. This $N^{\prime}_{2}$ is included in
$A^{\prime}_{2}[I]$ because $(P_{y^{\prime}}+x+y)\cap T_{I}=\emptyset$ follows
from $P_{y^{\prime}}\cap T_{I}=\emptyset$ and $x\not\in T_{I}$. Then,
$D^{\prime}[I]$ contains an $s$–$y$ path with arcs in $N_{1}\cup
N^{\prime}_{2}$ and length at most $2\ell$, which contradicts
$\operatorname{dist}(s,y)>2\ell$.

For the “if” part, suppose
$\\{y^{\prime},x\\}\not\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ and
$I\triangle(P_{y^{\prime}}+x+y)\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$. By
Lemma 2.3, $I\triangle(P_{y^{\prime}}+x+y)\in{\mathcal{I}}_{2}$ implies that
$A_{2}[I]$ contains a perfect matching $N_{2}^{\prime\prime}$ on
$V(P_{y^{\prime}}+x+y)$. Conversely, suppose $(x,y)\not\in
N^{\prime\prime}_{2}$. Then $(x^{*},y)\in N_{2}^{\prime\prime}$ for some
$x^{*}\in P_{y^{\prime}}$, and $P_{y^{\prime}}\cap T_{I}=\emptyset$ implies
$(x^{*},y)\in A^{\prime}_{2}[I]$. Hence $D^{\prime}[I]$ has an $s$–$y$ path
with length at most $2\ell$, a contradiction. Thus, $(x,y)\in
N^{\prime\prime}_{2}\subseteq A_{2}[I]$, which implies $x\in T_{I}$ or
$(x,y)\in A^{\prime}_{2}[I]$, where the latter implies $y\in
C_{2}(I,x)\not\subseteq\\{y^{\prime},x\\}$. Thus, in both cases,
$\\{y^{\prime},x\\}\in{\mathcal{I}}_{2}$. Therefore,
$\\{y^{\prime},x\\}\not\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ implies
$\\{y^{\prime},x\\}\not\in{\mathcal{I}}_{1}$, and hence $y^{\prime}\in
C_{1}(I,x)$, and $(y^{\prime},x)\in A^{\prime}_{1}[I]$ follows. By assumption,
we then have $x\not\in T_{I}$, and hence $(x,y)\in A^{\prime}_{2}[I]$. ∎

Thus, both (b) and (c) hold for $\ell$. ∎

Lemma 5.1 completes the proof of correctness of Algorithm 5.

######  Lemma 5.4.

The output of EmulatingBFS$[E,{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2},I,s]$ is
always correct.

###### Proof.

If $\operatorname{dist}(s,T_{I})=1$, i.e., if $s\in S_{I}\cap T_{I}$, then the
algorithm correctly returns $s$ at Step 1. If
$\operatorname{dist}(s,T_{I})=2\ell+1>1$, then $s\in S_{I}\setminus T_{I}$,
and hence Lemma 5.1(b) implies that a shortest $s$–$T_{I}$ path is returned in
the $\ell$th process of Step 3(ii). ∎

Using EmulatingBFS (Algorithm 5) as a subroutine, we design a procedure that
emulates Augment$[E,{\mathcal{I}}_{1},{\mathcal{I}}_{2},I]$ with the common
independence oracle.

Input : Oracle access to ${\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ where
${\mathcal{I}}_{1}$ is the independent set family of a partition matroid, and
a common independent set $I\in{\mathcal{I}}^{k}_{1}\cap{\mathcal{I}}^{k}_{2}$.

Output : A common independent set
$J\in{\mathcal{I}}^{k+1}_{1}\cap{\mathcal{I}}^{k+1}_{2}$ if one exists, or a
message _“No”_ otherwise.

1

2If $I+x\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ for some $x\in E\setminus
I$, then halt with returning $J=I+x$.

For each $s\in E\setminus I$, perform
EmulatingBFS$[E,{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2},I,s]$. If some sequence
$P$ is returned, then return $J=I\triangle P$. Otherwise return with the
message _“No”_.

Algorithm 6
(AugmentCommonIndependencePartition$[E,{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2},I]$).

######  Lemma 5.5.

The output of
AugmentCommonIndependencePartition$[E,{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2},I]$
(Algorithm 6) is always correct.

###### Proof.

The output in Step 6 is clearly correct. As Step 6 returns some sequence $P$
only if $I\triangle P$ is indeed a common independent set of size $k+1$, it
suffices to show that if there exists a common independent set $J$ of size
$k+1$, then EmulatingBFS$[E,{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2},I,s]$
returns a sequence for some $s\in E\setminus I$. By the correctness of
Augment$[E,{\mathcal{I}}_{1},{\mathcal{I}}_{2},I]$, the existence of such $J$
implies that $D[I]$ has some $S_{I}$–$T_{I}$ path, and so does
$D^{\prime}[I]$. Then $D^{\prime}[I]$ contains an $s$–$T_{I}$ path for some
$s\in S_{I}$. For such $s$,
EmulatingBFS$[E,{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2},I,s]$ returns a
shortest $s$–$T_{I}$ path in $D^{\prime}[I]$. ∎

Lemma 5.5 completes the proof of Theorem 1.2.

###### Proof of Theorem 1.2.

Starting from $I\coloneqq\emptyset$, the size of the common independent set
can be gradually increased using
AugmentCommonIndependencePartition$[E,{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2},I]$
until $I$ becomes a common independent set of maximum cardinality. The
correctness of the algorithm follows by Lemma 5.5. ∎

###  5.2 Intersection with Elementary Split Matroid

Motivated by the study of matroid polytopes from a tropical geometry point of
view, Joswig and Schröter [17] introduced the notion of split matroids. This
class does not only generalize paving matroids, but it is closed both under
duality and taking minors. Bérczi, Király, Schwarcz, Yamaguchi and Yokoi [4]
later observed that every split matroid can be obtained as the direct sum of a
so-called elementary split matroid and uniform matroids. Elementary split
matroids capture all the nice properties of connected split matroids, and is
closed not only under duality and taking minors but also truncation. Motivated
by representations of paving matroids by hypergraphs, they provided a
hypergraph characterization of elementary split matroids as follows.

Let $E$ be a ground set of size at least $r$,
${\mathcal{H}}=\\{H_{1},\dots,H_{q}\\}$ be a (possibly empty) collection of
subsets of $E$, and $r,r_{1},\dots,r_{q}$ be nonnegative integers satisfying

$\displaystyle|H_{i}\cap H_{j}|$ $\displaystyle\leq r_{i}+r_{j}-r$ for $1\leq
i<j\leq q$, (H1) $\displaystyle|E\setminus H_{i}|+r_{i}$ $\displaystyle\geq r$
for $i=1,\dots,q$. (H2)

Then ${\mathcal{I}}=\\{\,X\subseteq E\mid|X|\leq r,\ |X\cap H_{i}|\leq r_{i}\
\text{for $1\leq i\leq q$}\,\\}$ forms the family of independent sets of a
rank-$r$ matroid $M$ with rank function
$r_{M}(Z)=\min\big{\\{}r,|Z|,\min_{1\leq i\leq q}\\{|Z\setminus
H_{i}|+r_{i}\\}\big{\\}}$. Matroids that can be obtained in this form are
called elementary split matroids.

We call a set $F\subseteq E$ $H_{i}$-tight or tight with respect to $H_{i}$ if
$|F\cap H_{i}|=r_{i}$. The following lemma shows that an independent set of
size less than $r$ cannot be tight with respect to two different hyperedges.

######  Lemma 5.6.

Let $M$ be an elementary split matroid with representation
${\mathcal{H}}=\\{H_{1},\dots,H_{q}\\}$ and $r,r_{1},\dots,r_{q}$, and let $F$
be a set of size less than $r$. Then $F$ is tight with respect to at most one
of the hyperedges.

###### Proof.

Suppose to the contrary that $F$ is both $H_{i}$\- and $H_{j}$-tight. Then we
get

$\displaystyle|H_{i}\cap H_{j}|{}$ $\displaystyle{}\geq|F\cap H_{i}\cap
H_{j}|=|F\cap H_{i}|+|F\cap H_{j}|-|F\cap(H_{i}\cup H_{j})|$
$\displaystyle{}\geq r_{i}+r_{j}-|F|>r_{i}+r_{j}-r,$

contradicting (H1). ∎

Now we show that the weighted matroid intersection problem is tractable under
the common independence oracle when ${\mathbf{M}}_{1}$ is an elementary split
matroid, that is, when ${\mathcal{I}}_{1}$ can be represented as
${\mathcal{I}}_{1}=\\{\,X\subseteq E\mid|X|\leq r,\ |X\cap H_{i}|\leq r_{i}\
\text{for $1\leq i\leq q$}\,\\}$ for some (possibly empty) hypergraph
${\mathcal{H}}=\\{H_{1},\dots,H_{q}\\}$ and nonnegative integers
$r,r_{1},\dots,r_{q}$ satisfying (H1) and (H2). The proof is based on
observing that the exchangeability graph has a special structure.

###### Proof of Theorem 1.3.

Suppose that we have oracle access to the common independent set family
${\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ of two matroids on $E$, where
${\mathcal{I}}_{1}$ belongs to an elementary split matroid. Consider a
$w$-maximal set $I\in{\mathcal{I}}_{1}^{k}\cap{\mathcal{I}}_{2}^{k}$ for some
$k\in\\{0,1,\dots,n-1\\}$. According to Algorithm 2 and Lemma 4.1, a
$w$-maximal set $J\in{\mathcal{I}}_{1}^{k+1}\cap{\mathcal{I}}_{2}^{k+1}$, if
exists, can be obtained in the form $J=I\triangle P$ where $P$ is a shortest
cheapest $S_{I}$–$T_{I}$ path in $D^{\prime}[I]$.

######  Claim 5.7.

If ${\mathcal{I}}_{1}^{k+1}\cap{\mathcal{I}}_{2}^{k+1}\neq\emptyset$, then
there exists a shortest cheapest $S_{I}$–$T_{I}$ path in $D^{\prime}[I]$ of
length at most $3$.

###### Proof.

As ${\mathcal{I}}_{1}^{k+1}\cap{\mathcal{I}}_{2}^{k+1}\neq\emptyset$, there
necessarily exists an $S_{I}$–$T_{I}$ path in $D^{\prime}[I]$; let
$P=e_{1}e_{2}\cdots e_{\ell}$ be a shortest cheapest one. As $I$ is not a
basis of ${\mathbf{M}}_{1}$, observe that $I+x\notin{\mathcal{I}}_{1}$ for
some $x\in E\setminus I$ if and only if there exists a hyperedge $H_{i}$ such
that $I$ is $H_{i}$-tight and $x\in H_{i}$. By Lemma 5.6, $I$ is tight with
respect to at most one of the hyperedges, hence we get that
$E\setminus(S_{I}\cup I)\subseteq H_{i}$. This also implies that
$A^{\prime}_{1}[I]=\\{\,(y,x)\mid x\in H_{i}\setminus I,~{}y\in H_{i}\cap
I\,\\}$.

Assume that the length of the path is more than $3$. Then, by the above
observation, both $(e_{2},e_{\ell})$ and $(e_{\ell-1},e_{3})$ exist in
$D^{\prime}[I]$. Therefore $C\coloneqq e_{3}e_{4}\cdots e_{\ell-1}e_{3}$ is a
cycle in $D^{\prime}[I]$, and $P^{\prime}\coloneqq e_{1}e_{2}e_{\ell}$ is an
$S_{i}$–$T_{i}$ path in $D^{\prime}[I]$. By Lemma 2.5, the cost of $C$ is
nonnegative, and hence the cost of $P^{\prime}$ is at most the cost of $P$,
contradicting the choice of $P$. ∎

By Claim 5.7, a $w$-maximal member of
${\mathcal{I}}_{1}^{k+1}\cap{\mathcal{I}}_{2}^{k+1}$, if exists, can be found
by checking every set $I^{\prime}$ of size $k+1$ with $|I\triangle
I^{\prime}|\leq 2$. This concludes the proof of the theorem. ∎

###  5.3 Complemented with Maximum Rank Oracle

When access is given to both a common independence and a maximum rank oracle,
every step of Algorithms 3 and 4, i.e., EmulatingBellmanFord and
CheapestPathAugmentRankSum, can be emulated and hence the weighted matroid
intersection problem is solved as with Section 4.

###### Proof of Theorem 1.4.

Suppose that we have oracle access to the common independent set family
${\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ and the maximum rank function
${r_{\mathrm{max}}}$ of two matroids on $E$ instead of that to
${r_{\mathrm{sum}}}$. In EmulatingBellmanFord and CheapestPathAugmentRankSum,
we ask the rank sum oracle the following types of questions:

  1. (a)

whether ${r_{\mathrm{sum}}}(I^{\prime}+x)=2|I^{\prime}|$ or not for
$I^{\prime}\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ and $x\in E\setminus
I^{\prime}$,

  2. (b)

whether ${r_{\mathrm{sum}}}(I^{\prime}+x)=2|I^{\prime}|+1$ or not for
$I^{\prime}\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ and $x\in E\setminus
I^{\prime}$,

  3. (c)

whether ${r_{\mathrm{sum}}}(I^{\prime}+x)=2|I^{\prime}|+2$ or not for
$I^{\prime}\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ and $x\in E\setminus
I^{\prime}$, and

  4. (d)

whether ${r_{\mathrm{sum}}}(I^{\prime})=2|I^{\prime}|$ or not for
$I^{\prime}\subseteq E$.

These questions can be tested using the common independence and the maximum
rank oracles together as follows. The answer to (a) is _“Yes”_ if and only if
$I^{\prime}+x\notin{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ and
${r_{\mathrm{max}}}(I^{\prime}+x)=|I^{\prime}|$, the answer to (b) is _“Yes”_
if and only if $I^{\prime}+x\not\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$ and
${r_{\mathrm{max}}}(I^{\prime}+x)=|I^{\prime}|+1$, the answer to (c) is
_“Yes”_ if and only if
$I^{\prime}+x\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$, and the answer to (d)
is _“Yes”_ if and only if
$I^{\prime}\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$. ∎

## Acknowledgments

We are grateful to Yuni Iwamasa and Taihei Oki for initial discussions on the
problem.

The work was supported by the Lendület Programme of the Hungarian Academy of
Sciences – grant number LP2021-1/2021 and by the Hungarian National Research,
Development and Innovation Office – NKFIH, grant numbers FK128673 and
TKP2020-NKA-06. Yutaro Yamaguchi was supported by JSPS KAKENHI Grant Numbers
20K19743 and 20H00605, and by Overseas Research Program in Graduate School of
Information Science and Technology, Osaka University. Yu Yokoi was supported
by JST PRESTO Grant Number JPMJPR212B.

## References

  * [1] M. Aigner and T. A. Dowling.  Matching theory for combinatorial geometries.  Transactions of the American Mathematical Society, 158(1):231–245, 1971.
  * [2] M. Bárász.  Matroid intersection for the min-rank oracle.  Technical Report QP-2006-03, Egerváry Research Group, Budapest, 2006\.  http://www.cs.elte.hu/egres/.
  * [3] M. Bárász, K. Bérczi, T. Király, Y. Yamaguchi, and Y. Yokoi.  Matroid intersection under minimum rank oracle.  In preparation.
  * [4] K. Bérczi, T. Király, T. Schwarcz, Y. Yamaguchi, and Y. Yokoi.  Hypergraph characterization of split matroids.  arXiv preprint arXiv:2202.04371, 2022.
  * [5] C. Brezovec, G. Cornuéjols, and F. Glover.  Two algorithms for weighted matroid intersection.  Mathematical Programming, 36(1):39–53, 1986.
  * [6] R. A. Brualdi.  Comments on bases in dependence structures.  Bulletin of the Australian Mathematical Society, 1(2):161–167, 1969\.
  * [7] C. R. Coullard and L. Hellerstein.  Independence and port oracles for matroids, with an application to computational learning theory.  Combinatorica, 16(2):189–208, 1996.
  * [8] W. H. Cunningham.  Improved bounds for matroid partition and intersection algorithms.  SIAM Journal on Computing, 15(4):948–957, 1986.
  * [9] J. Edmonds.  Submodular functions, matroids, and certain polyhedra.  In Combinatorial Structures and Their Applications, pages 69–87. Gorden and Breach, 1970.  (Also in _Combinatorial Optimization — Eureka, You Shrink!_ , pages 11–26, Springer, 2003.).
  * [10] J. Edmonds.  Matroid intersection.  Annals of Discrete Mathematics, 4:39–49, 1979.
  * [11] A. Frank.  A weighted matroid intersection algorithm.  Journal of Algorithms, 2(4):328–336, 1981.
  * [12] A. Frank.  Rooted $k$-connections in digraphs.  Discrete Applied Mathematics, 157(6):1242–1254, 2009.
  * [13] D. Hausmann and B. Korte.  Algorithmic versus axiomatic definitions of matroids.  In Mathematical Programming at Oberwolfach, pages 98–111. Springer, 1981.
  * [14] C.-C. Huang, N. Kakimura, and N. Kamiyama.  Exact and approximation algorithms for weighted matroid intersection.  Mathematical Programming, 177(1-2):85–112, 2019.
  * [15] M. Iri and N. Tomizawa.  An algorithm for finding an optimal “independent assignment”.  Journal of the Operations Research Society of Japan, 19(1):32–57, 1976.
  * [16] P. M. Jensen and B. Korte.  Complexity of matroid property algorithms.  SIAM Journal on Computing, 11(1):184–190, 1982.
  * [17] M. Joswig and B. Schröter.  Matroids from hypersimplex splits.  Journal of Combinatorial Theory, Series A, 151:254–284, 2017.
  * [18] S. Krogdahl.  A combinatorial base for some optimal matroid intersection algorithms.  Technical Report STAN-CS-74-468, Computer Science Department, Stanford University, Stanford, CA, U.S., 1974.
  * [19] S. Krogdahl.  A combinatorial proof for a weighted matroid intersection algorithm.  Technical Report Computer Science Report 17, Institute of Mathematical and Physical Sciences, University of Tromso, Tromso, Norway, 1976\.
  * [20] S. Krogdahl.  The dependence graph for bases in matroids.  Discrete Mathematics, 19(1):47–59, 1977.
  * [21] E. L. Lawler.  Optimal matroid intersections.  In Combinatorial Structures and Their Applications, pages 233–234. Gorden and Breach, 1970.
  * [22] E. L. Lawler.  Matroid intersection algorithms.  Mathematical Programming, 9(1):31–56, 1975.
  * [23] E. L. Lawler.  Combinatorial Optimization: Networks and Matroids.  Holt, Rinehart and Winston, 1976.
  * [24] L. Lovász.  Matroid matching and some applications.  Journal of Combinatorial Theory, Series B, 28(2):208–236, 1980\.
  * [25] L. Lovász.  The matroid matching problem.  In Algebraic Methods in Graph Theory II, pages 495–517. North-Holland, 1981.
  * [26] L. Lovász and M. D. Plummer.  Matching Theory.  American Mathematical Society, 2009.
  * [27] J. Oxley.  Matroid Theory.  Oxford University Press, 2011.
  * [28] G. Robinson and D. Welsh.  The computational complexity of matroid properties.  In Mathematical Proceedings of the Cambridge Philosophical Society, volume 87, pages 29–45. Cambridge University Press, 1980.
  * [29] A. Schrijver.  Combinatorial Optimization: Polyhedra and Efficiency.  Springer, 2003.


the latter result following by differentiating (A.35). In summary, we have
established the existence of an exact solution
$S^{(n)}_{p}(\tau)=W^{(n)}_{p}(\tau)\cdot R_{p}(\tau)$ of (A.1), i.e., an
adiabatic vacuum state of order $n\in{\mathbb{N}}_{0}$, whose large $|p|$
asymptotic behavior (A.2) follows immediately from (A.38). Finally, the
initial condition (A.36) entails that
$(\partial_{\tau}S^{(n)}_{p}\,S^{(n)\,\ast}_{p})(\tau_{0})-(\partial_{\tau}S^{(n)\,\ast}_{p}\,S^{(n)}_{p})(\tau_{0})=-i$,
and since $S^{(n)}_{p}$ solves
$[{\partial}_{\tau}^{2}+\omega_{p}(\tau)^{2}]S^{(n)}_{p}(\tau)=0$, it is
Wronskian normalized for all times. ∎

## References

  * [1] I. Khavkine and V. Moretti, Algebraic QFT in Curved Spacetime and quasifree Hadamard states: an introduction, In Advances in algebraic quantum field theory, editors R. Brunetti, C. Dappiaggi, K. Fredenhagen, and J. Yngvason, Springer, 2015.
  * [2] S. Hollands and R. Wald, Quantum fields in curved spacetimes, Phys. Rept. 574 (2015) 1.
  * [3] C. Gerard, Microlocal Analysis of Quantum Fields on Curved Spacetimes, Europ. Math. Soc., 2019.
  * [4] S. Fulling, F. Narcovich, R. Wald, Singularity structure of the two-point function in curved spacetime II, Ann. Phys. 136 (1981) 243.
  * [5] C. Dappiaggi , V. Moretti , and N. Pinamonti, Hadamard States From Light-like Hypersurfaces, Springer, 2017.
  * [6] W. Junker and E. Schrohe, Adiabatic vacuum states on general space-time manifolds: definition, construction, and physical properties, Ann. H. Poincaré 3 (2002) 1113–1182.
  * [7] H. Olbermann, States of low energy on Robertson-Walker spacetimes, Class. Quant. Grav. 24 (2007) .
  * [8] N. Ashordi, S. Aslanbeigi, and R. Sorkin, A distingished vacuum state for a quantum field in a curved spacetimes: formalism, features, and cosmology, JHEP 8 (2012) 137.
  * [9] M. Brum and K. Fredenhagen, ‘Vacuum-like’ Hadamard states for quantum fields on curved spacetimes, Class. Quant. Grav. 31 (2014) 025024.
  * [10] K. Them and M. Brum, States of Low Energy in homogeneous and inhomogeneous, expanding spacetimes, Class. Quant. Grav. 30 (2013) 235035.
  * [11] R. Banerjee and M. Niedermaier, Bonus properties of states of low energy, J. Math. Phys. 61 10 (2020) 103511.
  * [12] R. Banerjee and M. Niedermaier, The spatial Functional Renormalization Group and Hadamard states on cosmological spacetimes, Nucl. Phys. B980 (2022) 11514.
  * [13] C. J. Fewster, A general worldline quantum inequality, Class. Quant. Grav. 17 (2000) 1897–1911.
  * [14] B. S. Kay and R. M. Wald, Theorems on the uniqueness and thermal properties of stationary, nonsingular, quasifree states on space-times with a bifurcate killing horizon, Phys. Rept. 207 2 (1991) 49–136.
  * [15] S. A. Fulling, Remarks on positive frequency and Hamiltonians in expanding universes, Gen. Rel. Grav. 10 (1979) 807–824.
  * [16] M. Martín-Benito, R. B. Neves, and J. Olmedo, Non-oscillatory power spectrum from States of Low Energy in kinetically dominated early universes, Front. Astron. Space Sci. 8 (2021) 702543.
  * [17] M. Martín-Benito, R. B. Neves, and J. Olmedo, States of Low Energy in bouncing inflationary scenarios in Loop Quantum Cosmology, Phys. Rev. D103 (2021) 123524.
  * [18] Á. Álvarez-Domínguez, L.J Garay, M. Martín-Benito, and R. B Neves, States of Low Energy in the Schwinger effect, JHEP 06 (2023) 93.
  * [19] S. Nadal-Gisbert, J. Navarro-Salas, and S. Pla, Low Energy States and CPT invariance at the big bang, Phys. Rev. D107 8 (2023) 085018.
  * [20] C. A. Mantica and L. G. Molinari, Generalized Robertson-Walker spacetimes – A survey, Int. J. Geom. Meth. Mod. Phys. 14 03 (2017) 1730001.
  * [21] M. Niedermaier, Nonstandard action of Diffeomorphisms and Gravity’s Anti-Newtonian limit, Symmetry 12 (2020) 752.
  * [22] G. Montani, M. Battisti, R. Benini, and G. Imponente, Primordial Cosmology, World Scientific, 2011.
  * [23] G. Maniccia, M. De Angelis, and G. Montani, WKB Approaches to Restore Time in Quantum Cosmology: Predictions and Shortcomings, Universe 8 (2022) 556.
  * [24] B. Cropp and M. Visser, Any spacetime has a Bianchi I type limit, Class. Quant. Grav. 28 (2011) 055007.
  * [25] J. Ritchie, Bianchi I “asymptotically Kasner” solutions of the Einstein scalar field equations, Class. Quant. Grav. 39 13 (2022) 135007.
  * [26] E. Nungesser, Isotropization of non-diagonal Bianchi I spacetimes with collisionless matter at late times assuming small initial data, Class. Quant. Grav. 27 (2010) 235025.
  * [27] D. Bernard, Hadamard singularity and quantum states in Bianchi type I space-time, Phys. Rev. D33 (1986) 3581–3589.
  * [28] J. Matyjasek, Quantum fields in Bianchi type I spacetimes: the Kasner metric, Phys. Rev. D98 (2018) 104054.
  * [29] F. D. Mazzitelli , J. P. Paz, and M. A. Castagnino, Cauchy data and Hadamard singularities in time dependent backgrounds, Phys. Rev. D36 (1987) 2994-3001.
  * [30] L. Hörmander, The Analysis of Linear Partial Differential Operators I: Distribution theory and Fourier Analysis, Springer, 1983.
  * [31] R. Haag, H. Narnhofer, and U. Stein, On quantum field theory in gravitational background, Commun. Math. Phys. 94 (1984) 219.
  * [32] C. Lüders and J. E. Roberts, Local quasiequivalence and adiabatic vacuum states, Commun. Math. Phys. 134 (1990) 29–63.
  * [33] K. Pirk, Hadamard states and adiabatic vacua, Phys. Rev. D48 (1993) 3779–3783.
  * [34] L. E. Parker, Quantized Fields and Particle Creation in Expanding Universes. I, Phys. Rev. 183 (1969) 1057–1068.
  * [35] L. E. Parker and D. Toms, Quantum Field Theory in Curved Spacetime: Quantized Field and Gravity, Cambridge University Press, 2009.
  * [36] M. J. Radzikowski, Micro-local approach to the Hadamard condition in quantum field theory on curved space-time, Commun. Math. Phys. 179 (1996) 529–553.
  * [37] A. Strohmaier, Microlocal analysis, in Lect. Notes Phys. 786 85; editors C. Bär and K. Fredenhagen, Springer 2009.
  * [38] C. Bär, N. Ginoux, and F. Pfäffle, Wave equations on Lorentzian manifolds and Quantization, Europ. Math. Soc. 2007.
  * [39] C. Fewster, Modified Green-hyperbolic operators, SIGMA 19 (2023) 057.
  * [40] J. Swieca, Goldstone’s theorem and related topics, in: Cargese lectures Vol 4, 1969.
  * [41] J. Lopuszanski, An Introduction to Symmetry and Supersymmetry in Quantum Field Theory, World Scientific, 1991.
  * [42] I. Avramidi, Heat kernel method and its applications, Birkhäuser, 2015.
  * [43] S. Rida, Explicit formulae for the powers of a Schrödinger-like ordinary differential operator, J. Phys. A: Math. Gen. 31 (1998) 5577.
  * [44] I. Polterovich, Heat invariants of Riemannian manifolds, Israel J. Math. 119 (2000) 239.
  * [45] I. Avramidi and R. Schimming, A new explicit expression for the Korteweg-de Vries hierarchy, Math. Nachr. 219 (2000) 45; arXiv:solv-int/9710009.
  * [46] Y. Decanini and A. Folacci, Off-diagonal coefficients of the DeWitt-Schwinger and Hadamard representations of the Feynman propagator, Phys. Rev. D73 (2006) 044027.
  * [47] Z. Avetisyan and R. Verch, Explicit harmonic and spectral analysis in Bianchi I-VII type cosmologies, Class. Quant. Grav. 30 (2020) 155006.
  * [48] D. Saadeh, S. M. Feeney, A. Pontzen, H. V. Peiris, and J. D. McEwen, How isotropic is the Universe?, Phys. Rev. Lett. 117 (2016) 131302.