# Matroid Intersection under Minimum Rank Oracle

Mihály Bárász HUN-REN-ELTE Egerváry Research Group, Department of Operations
Research, Eötvös Loránd University, Budapest, Hungary. Email:
<EMAIL_ADDRESS>Kristóf Bérczi MTA-ELTE Matroid Optimization Research
Group and HUN-REN-ELTE Egerváry Research Group, Department of Operations
Research, Eötvös Loránd University, Budapest, Hungary. Email:
<EMAIL_ADDRESS>Tamás Király HUN-REN-ELTE Egerváry Research Group,
Department of Operations Research, Eötvös Loránd University, Budapest,
Hungary. Email<EMAIL_ADDRESS>Yutaro Yamaguchi Department of
Information and Physical Sciences, Graduate School of Information Science and
Technology, Osaka University, Osaka, Japan. Email:
<EMAIL_ADDRESS>Yu Yokoi Department of Mathematical and
Computing Science, School of Computing, Tokyo Institute of Technology, Tokyo,
Japan. Email<EMAIL_ADDRESS>
###### Abstract

In this paper, we consider the tractability of the matroid intersection
problem under the minimum rank oracle. In this model, we are given an oracle
that takes as its input a set of elements, and returns as its output the
minimum of the ranks of the given set in the two matroids. For the unweighted
matroid intersection problem, we show how to construct a necessary part of the
exchangeability graph, which enables us to emulate the standard augmenting
path algorithm. Furthermore, we reformulate Edmonds’ min-max theorem only
using the minimum rank function, providing a new perspective on this result.
For the weighted problem, the tractability is open in general. Nevertheless,
we describe several special cases where tractability can be achieved, and we
discuss potential approaches and the challenges encountered. In particular, we
present a solution for the case where no circuit of one matroid is contained
within a circuit of the other. Additionally, we propose a fixed-parameter
tractable algorithm, parameterized by the maximum circuit size. We also show
that a lexicographically maximal common independent set can be found by the
same approach, which leads to at least $1/2$-approximation for finding a
maximum-weight common independent set.

Keywords: Algorithm, Matroid intersection, Minimum rank oracle

##  1 Introduction

When designing matroid algorithms, it is essential to clarify how matroids are
represented. Since the number of bases is potentially exponential, listing
them explicitly is impractical. Instead, standard oracles are assumed to be
available to query the rank or the independence of a subset, and the
complexity of the algorithm is measured by the number of oracle calls. In [5],
Bérczi, Király, Yamaguchi, and Yokoi initiated the study of matroid
intersection problems under restricted oracles, with particular emphasis on
the rank sum, common independence, and maximum rank oracles. They showed that
the weighted matroid intersection problem remains tractable even under the
rank sum oracle. Furthermore, they showed that the common independence oracle
model allows for an efficient algorithm for the unweighted matroid
intersection problem 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.

As a continuation of the work [5], we investigate the tractability of the
weighted matroid intersection problem under the minimum rank oracle. In this
model, for a subset of elements, the oracle outputs the minimum of the ranks
of the subset in the two matroids. The motivation of the problem comes from a
polyhedral perspective. In [7], Edmonds showed that the convex hull of the
common independent sets of two matroids coincides with the intersection of the
two independent set polytopes. This implies that the common independent set
polytope itself enjoys a nice feature: it is already determined by the
_minimum rank function_ of the two matroids rather than the two rank
functions. However, while the separation problem for an independent set
polytope defined by a rank function reduces to submodular function
minimization and therefore is tractable [13, 19, 22], this does not hold for a
common independent set polytope defined by the minimum of the two rank
functions, which is no longer submodular.

A set function is called _$1/3$ -submodular_ and _$2/3$ -submodular_ if the
submodular inequality holds for at least one and at least two, respectively,
among the three pairs formed from every distinct three subsets. Mizutani and
Yoshida [20] gave polynomial-time algorithms to minimize 2/3-submodular
functions. However, it was shown by Bérczi and Frank [3] that minimizing a
1/3-submodular function requires an exponential number of oracle calls when
the function is given by an evaluation oracle. This naturally raises the
following question: apart from 2/3-submodular functions, what other classes of
1/3-submodular functions can be minimized in polynomial time? Our research
concerns the class of functions that arise as the sum of a modular function
and the minimum rank of two matroids. On the one hand, these functions are
1/3-submodular, since at least two of every three subsets attain the minimum
rank in the same matroid. On the other hand, the minimization problem over
this class is equivalent to the separation problem over the common independent
set polytope given by minimum rank function of two matroids; with the aid of
the ellipsoid method [10], the latter problem is in turn equivalent to the
weighted matroid intersection problem under the minimum rank oracle, which we
focus on this paper.

##### Our results.

As in the rank sum case of [5], the main obstacle to giving an efficient
algorithm is that the usual augmenting path approach cannot be applied, since
the exchangeability graphs are not determined by the minimum rank oracle.
However, our aim is still to emulate the Bellman–Ford algorithm on the
underlying exchangeability graph, but our strategy is completely different
from the one in [5].

The main difficulty caused by the minimum rank oracle is that we cannot
determine the fundamental circuits of an element with respect to a given set
in the two matroids separately. To overcome this difficulty, we slightly
modify the exchangeability graph by roughly estimating the fundamental
circuits so that extra arcs that in reality are not present in it. Based on
the observation in a manuscript [2], one can do it only using the minimum rank
oracle so that the set of shortest paths remains the same, which in turn
allows us to solve the unweighted problem (Theorem 3.4).

In order to tackle the weighted problem, by further refining the notion of
modified exchangeability graphs, we introduce the notion of consistent
exchangeability graphs that have strong structural properties. Specifically,
we show that even if the true exchangeability graph is not correctly
recognized, a kind of consistency with respect to small local exchanges is
enough for the graph to behave essentially the same (Lemma 4.7), which is
sufficient to emulate the usual weighted matroid intersection algorithm. While
it unfortunately turns out difficult to find such a graph in general (Theorem
6.1), we show that an “almost consistent” exchangeability graph can be found
efficiently relying on a 2-SAT approach. This leads to the tractability under
the minimum rank oracle for several special cases: when no circuit of one
matroid contains a circuit of the other (Theorem 5.4), when the maximum size
of a circuit in the matroids is bounded by a constant (Theorem 5.6), and when
the objective is to find a lexicographically maximal common independent set
(Theorem 5.7), which also implies at least $1/2$-approximation for the usual
weight maximization problem (Corollary 5.11).

##### Organization.

The rest of the paper is organized as follows. Basic definitions and notation
are introduced in Section 2. In Section 3, which is based on a manuscript [2],
we introduce the concept of modified exchangeability graphs, which are crucial
for our proofs. We also review the unweighted problem under the minimum rank
oracle. In Section 4, we refine modified exchangeability graphs further,
leading to the definition of consistent exchangeability graphs. We show that
solving the weighted matroid intersection problem reduces to determining a
consistent exchangeability graph. On the positive side, in Section 5, we show
that an almost consistent exchangeability graph can be constructed in
polynomial time by solving a related 2-SAT problem, which is sufficient for
solving several special cases. On the negative side, we prove in Section 6
that the problem of finding a consistent exchangeability graph is NP-hard in
general.

##  2 Preliminaries

For the basics on matroids and the matroid intersection problem, we refer the
reader to [21, 23, 9]. To make the paper self-contained, we repeat the basic
definitions and results on matroids as summarized in [5, Section 2].

Throughout the paper, for $i=1,2$, let
${\mathbf{M}}_{i}=(E,{\mathcal{I}}_{i})$ be loopless 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 $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 $C_{i}(I,x)=\\{\,y\in I\mid
I+x-y\in{\mathcal{I}}_{i}\,\\}$. For two sets $X,Y\subseteq E$, we denote
their symmetric difference by $X\triangle Y=(X\setminus Y)\cup(Y\setminus X)$.

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

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

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}$ is a common
independent set of ${\mathbf{M}}_{1}$ and ${\mathbf{M}}_{2}$. The
exchangeability graph with respect to $I$ is a directed bipartite graph
$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 $A[I]\coloneqq A_{1}[I]\cup A_{2}[I]$, 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]$ of exchangeability arcs 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 such that $Z$ is
the set of tails and heads of these arcs).

Krogdahl [15, 16, 17] made 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}$.

Let us recall that a standard algorithm for finding a maximum-cardinality
common independent set is driven by the following subroutine, Algorithm 1 (see
[23, Section 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 path that satisfies
$(e_{\ell},e_{1})\in A$. We often identify a path or cycle $e_{1}e_{2}\cdots
e_{\ell}$ with its vertex set $\\{e_{1},e_{2},\dots,e_{\ell}\\}$.

1

Input : A finite set $E$, oracle access to the independence set families
${\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|$.

2

3Construct 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 as shown in
Algorithm 2 (see [23, Section 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)&(e\in I),\\\
-w(e)&(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|$.

1

2Create the exchangeability graph $D[I]$ with $S_{I}$ and $T_{I}$ as with
Augment$[E,{\mathcal{I}}_{1},{\mathcal{I}}_{2},I]$. In addition, define a 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. [23, 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).

We also remark that any even prefix or suffix of any shortest $S_{I}$–$T_{I}$
path in $D[I]$ is also exchangeable (as it has no shortcut, this is an easy
consequence of Lemma 2.4). It is similarly (e.g., by considering the weight-
splitting algorithm [8]) observed that this is also true for any shortest
cheapest $S_{I}$–$T_{I}$ path in $D[I]$ if $I$ is $w$-maximal in
${\mathcal{I}}_{1}^{k}\cap{\mathcal{I}}_{2}^{k}$, where $k=|I|$.

######  Lemma 2.6 (cf. [9, Lemmas 13.1.11 and 13.2.14]).

For any $I\in{\mathcal{I}}_{1}^{k}\cap{\mathcal{I}}_{2}^{k}$, the following
statements hold.

  * •

Let $P$ be a shortest $S_{I}$–$T_{I}$ path in $D[I]$, and $P^{\prime}$ be a
prefix of $P$ ending in $I$ or a suffix starting in $I$, which is of even
length. Then, $I\triangle
P^{\prime}\in{\mathcal{I}}_{1}^{k}\cap{\mathcal{I}}_{2}^{k}$.

  * •

Suppose that $I$ is $w$-maximal in
${\mathcal{I}}_{1}^{k}\cap{\mathcal{I}}_{2}^{k}$. Let $P$ be a shortest
cheapest $S_{I}$–$T_{I}$ path in $D[I]$ with respect to the cost function $c$
defined as (2.1), and $P^{\prime}$ be a prefix of $P$ ending in $I$ or a
suffix starting in $I$, which is of even length. Then, $I\triangle
P^{\prime}\in{\mathcal{I}}_{1}^{k}\cap{\mathcal{I}}_{2}^{k}$.

##  3 Cardinality Matroid Intersection

From now on, we assume access only to the minimum rank function
${r_{\mathrm{min}}}\colon 2^{E}\to{\mathbb{Z}}_{\geq 0}$ defined by

$\displaystyle{r_{\mathrm{min}}}(X)\coloneqq\min\left\\{r_{1}(X),r_{2}(X)\right\\}\quad(X\subseteq
E).$

Note that a subset $I\subseteq E$ is a common independent set if and only if
${r_{\mathrm{min}}}(I)=|I|$. This section is based on a manuscript [2], and
the results are presented in a revised form that is easy to extend to our
approach to the weighted problem.

First, we observe that Theorem 2.1 can be rephrased as follows.

######  Lemma 3.1.

The following equation holds:

$\displaystyle\max\left\\{\,|I|\bigm{|}I\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}\,\right\\}$
$\displaystyle=\min\left\\{\,{r_{\mathrm{min}}}(Z)+{r_{\mathrm{min}}}(E\setminus
Z)\mid Z\subseteq E\,\right\\}.$

###### Proof.

For any common independent set $I\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}$
and any subset $Z\subseteq E$, we have

$\displaystyle|I|$ $\displaystyle=|I\cap Z|+|I\setminus
Z|\leq{r_{\mathrm{min}}}(Z)+{r_{\mathrm{min}}}(E\setminus Z)\leq
r_{1}(Z)+r_{2}(E\setminus Z).$

Since Theorem 2.1 assures the minimum of the most right-hand side is equal to
the maximum of the most left-hand side, the same is true for the intermediate
one with respect to ${r_{\mathrm{min}}}$. ∎

From the algorithmic viewpoint, while Lemma 3.1 gives an optimality
certification in cardinality maximization, it is difficult to construct the
exchangeability graph $D[I]$ (cf. Definition 2.2) used in Algorithm 1.
Specifically, in general, we cannot exactly determine the fundamental circuits
$C_{i}(I,x)$ for all $x\in E\setminus(I\cup S_{I}\cup T_{I})$ and $i=1,2$ only
by the minimum rank function.

We overcome this difficulty by modifying the exchangeability graph as follows.
Intuitively, we estimate the fundamental circuits $C_{1}(I,x)$ and
$C_{2}(I,x)$ as $C_{1}(I,x)\cup C_{1}(I,t^{*})$ and $C_{2}(I,x)\cup
C_{2}(I,s^{*})$, respectively, for some fixed $s^{*}\in S_{I}\setminus T_{I}$
and $t^{*}\in T_{I}\setminus S_{I}$. This yields extra arcs not existing in
the original exchangeability graph $D[I]$, but those extra arcs are not used
in any shortest $S_{I}$–$T_{I}$ path in the new graph (cf. Lemma 3.3). That
is, the shortest $S_{I}$–$T_{I}$ paths are completely preserved, and hence one
can emulate Algorithm 1 using the modified exchangeability graph instead of
$D[I]$.

######  Definition 3.2 (Modified Exchangeability Graph).

For a common independent set $I\subseteq E$ and a pair $(s^{*},t^{*})$ with
${r_{\mathrm{min}}}(I+s^{*})={r_{\mathrm{min}}}(I+t^{*})={r_{\mathrm{min}}}(I)=|I|$
and ${r_{\mathrm{min}}}(I+s^{*}+t^{*})=|I|+1$, the modified exchangeability
graph is a directed bipartite graph
${D^{\mathrm{min}}}[I;s^{*},t^{*}]=(E\setminus
I,I;{A^{\mathrm{min}}}[I;s^{*},t^{*}])$ defined as follows. Define two subsets
$S_{I}^{*},T_{I}^{*}\subseteq E\setminus I$ by

$\displaystyle S_{I}^{*}$ $\displaystyle\coloneqq\\{\,s\in E\setminus
I\mid{r_{\mathrm{min}}}(I+s+t^{*})=|I|+1\,\\},$ $\displaystyle T_{I}^{*}$
$\displaystyle\coloneqq\\{\,t\in E\setminus
I\mid{r_{\mathrm{min}}}(I+s^{*}+t)=|I|+1\,\\}.$

We then define
${A^{\mathrm{min}}}[I;s^{*},t^{*}]\coloneqq{A_{1}^{\mathrm{min}}}[I;s^{*},t^{*}]\cup{A_{2}^{\mathrm{min}}}[I;s^{*},t^{*}]$,
where

$\displaystyle{A_{1}^{\mathrm{min}}}[I;s^{*},t^{*}]$
$\displaystyle\coloneqq\\{\,(y,s)\mid s\in S_{I}^{*},~{}y\in I\,\\}$
$\displaystyle\quad\cup\\{\,(y,t)\mid t\in T_{I}^{*}\setminus
S_{I}^{*},~{}y\in I,~{}{r_{\mathrm{min}}}(I+t-y)=|I|\,\\}$
$\displaystyle\quad\cup\\{\,(y,x)\mid x\in E\setminus(I\cup S_{I}^{*}\cup
T_{I}^{*}),~{}y\in I,~{}{r_{\mathrm{min}}}(I+t^{*}+x-y)=|I|\,\\},$ (3.1)
$\displaystyle{A_{2}^{\mathrm{min}}}[I;s^{*},t^{*}]$
$\displaystyle\coloneqq\\{\,(t,y)\mid t\in T_{I}^{*},~{}y\in I\,\\}$
$\displaystyle\quad\cup\\{\,(s,y)\mid s\in S_{I}^{*}\setminus
T_{I}^{*},~{}y\in I,~{}{r_{\mathrm{min}}}(I+s-y)=|I|\,\\}$
$\displaystyle\quad\cup\\{\,(x,y)\mid x\in E\setminus(I\cup S_{I}^{*}\cup
T_{I}^{*}),~{}y\in I,~{}{r_{\mathrm{min}}}(I+s^{*}+x-y)=|I|\,\\}.$ (3.2)

It is easy to observe that $\\{S_{I}^{*},T_{I}^{*}\\}=\\{S_{I},T_{I}\\}$, and
we can assume that $S_{I}^{*}=S_{I}$ and $T_{I}^{*}=T_{I}$ by symmetry of
$s^{*}$ and $t^{*}$ (i.e., by exchanging them if necessary).

######  Lemma 3.3.

The modified exchangeability graph ${D^{\mathrm{min}}}[I;s^{*},t^{*}]$
satisfies the following properties.

  1. (a)

$A_{i}[I]\subseteq{A_{i}^{\mathrm{min}}}[I;s^{*},t^{*}]$ for $i=1,2$.
Moreover, if $(u,v)\in{A^{\mathrm{min}}}[I;s^{*},t^{*}]\setminus A[I]$, then
$u,v\not\in S_{I}\cup T_{I}$.

  2. (b)

If $(y,x)\in{A_{1}^{\mathrm{min}}}[I;s^{*},t^{*}]\setminus A_{1}[I]$, then
$(y,t^{*})\in A_{1}[I]$. If
$(x,y)\in{A_{2}^{\mathrm{min}}}[I;s^{*},t^{*}]\setminus A_{2}[I]$, then
$(s^{*},y)\in A_{2}[I]$.

###### Proof.

(a) By symmetry, we only prove the statement for $i=2$. We first confirm that
$A_{2}[I]$ and ${A_{2}^{\mathrm{min}}}[I]$ coincide around each vertex in
$S_{I}\cup T_{I}$. This is trivial for each sink in $T_{I}=T_{I}^{*}$ by
definition. Let $s\in S_{I}=S_{I}^{*}$ and $y\in I$. Then, $(s,y)\in A_{2}[I]$
if and only if $I+s-y\in{\mathcal{I}}_{2}$ by definition. As
$I+s\in{\mathcal{I}}_{1}$ by $s\in S_{I}$, we have
$r_{1}(I+s-y)=r_{1}(I+s)-1=|I|$. Hence,
$(s,y)\in{A_{2}^{\mathrm{min}}}[I;s^{*},t^{*}]$ if and only if
$r_{2}(I+s-y)\geq|I|$, which means $I+s-y\in{\mathcal{I}}_{2}$. Thus,
$A_{2}[I]$ and ${A_{2}^{\mathrm{min}}}[I]$ coincide around each source $s\in
S_{I}$, and we are done.

Next, suppose that $(x,y)\in A_{2}[I]$ with $x\in E\setminus(I\cup S_{I}\cup
T_{I})$ and $y\in I$, and we show that
$(x,y)\in{A_{2}^{\mathrm{min}}}[I;s^{*},t^{*}]$, which completes the proof. By
definition, we have $I+x-y\in{\mathcal{I}}_{2}$, and we show
${r_{\mathrm{min}}}(I+s^{*}+x-y)=|I|$, regardless of the choice of $s^{*}\in
S_{I}\setminus T_{I}$. On one hand, as $I+s^{*}\in{\mathcal{I}}_{1}$ (by
$s^{*}\in S_{I}$), we have $r_{1}(I+s^{*}+x-y)\geq r_{1}(I+s^{*})-1=|I|$. On
the other hand, as $\\{s^{*},x\\}\subseteq\mathrm{cl}_{2}(I)$ by
$s^{*},x\not\in T_{I}$, we have $r_{2}(I+s^{*}+x)=|I|$, and hence
$|I|=r_{2}(I+x-y)\leq r_{2}(I+s^{*}+x-y)\leq r_{2}(I+s^{*}+x)=|I|$. This
concludes that ${r_{\mathrm{min}}}(I+s^{*}+x-y)=|I|$, i.e.,
$(x,y)\in{A_{2}^{\mathrm{min}}}[I;s^{*},t^{*}]$. Thus we are done.

(b) By symmetry, fix an arc
$(x,y)\in{A_{2}^{\mathrm{min}}}[I;s^{*},t^{*}]\setminus A_{2}[I]$ with $x\in
E\setminus(I\cup S_{I}\cup T_{I})$ and $y\in I$ (cf. (a)), and we show
$r_{2}(I+s^{*}-y)=|I|$, which implies $(s^{*},y)\in A_{2}[I]$. By definition,
we have ${r_{\mathrm{min}}}(I+s^{*}+x-y)=|I|$ and $r_{2}(I+x-y)\leq|I|-1$. As
$x\neq s^{*}\not\in T_{I}$, we obtain

$\displaystyle|I|=r_{2}(I+s^{*})\geq r_{2}(I+s^{*}-y)\geq
r_{2}(I+s^{*}+x-y)+r_{2}(I-y)-r_{2}(I+x-y)\geq|I|,$

where the middle inequality is by the submodularity of the rank function
$r_{2}$. This concludes that $r_{2}(I+s^{*}-y)=|I|$, and we are done. ∎

By Lemma 3.3, for any pair $(s^{*},t^{*})$ with $s^{*}\in S_{I}\setminus
T_{I}$ and $t^{*}\in T_{I}\setminus S_{I}$,

  * •

the modified exchangeability graph ${D^{\mathrm{min}}}[I;s^{*},t^{*}]$
includes the exchangeability graph $D[I]$ as its subgraph, and

  * •

any shortest $S_{I}$–$T_{I}$ path in ${D^{\mathrm{min}}}[I;s^{*},t^{*}]$
consists of arcs in $A[I]$, since there must be a shortcut arc in $A[I]$ if
some arc in ${A^{\mathrm{min}}}[I;s^{*},t^{*}]\setminus A[I]$ is traversed.

Hence, Algorithm 3 correctly emulates
Augment$[E,{\mathcal{I}}_{1},{\mathcal{I}}_{2},I]$, up to the symmetry of
${\mathbf{M}}_{1}$ and ${\mathbf{M}}_{2}$.

1

Input : A finite set $E$, oracle access to the minimum rank function
${r_{\mathrm{min}}}$ of two matroids on $E$, and a common independent set $I$
(with ${r_{\mathrm{min}}}(I)=|I|$).

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

2

3If ${r_{\mathrm{min}}}(I+s+t)=|I|$ for every $s,t\in E\setminus I$, then halt
with returning $Z=E$.

4If ${r_{\mathrm{min}}}(I+x)=|I|+1$ for some $x\in E\setminus I$, then halt
with returning $J=I+x$.

5Take any pair $(s^{*},t^{*})$ with
${r_{\mathrm{min}}}(I+s^{*})={r_{\mathrm{min}}}(I+t^{*})=|I|$ and
${r_{\mathrm{min}}}(I+s^{*}+t^{*})=|I|+1$, and create the modified
exchangeability graph ${D^{\mathrm{min}}}[I;s^{*},t^{*}]$ with $S_{I}^{*}$ and
$T_{I}^{*}$.

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

Algorithm 3 (AugmentMinRank$[E,{r_{\mathrm{min}}},I]$).

######  Theorem 3.4.

A maximum common independent set in the two matroids can be found in
$\mathrm{O}(rn^{2})$ time only using the minimum rank oracle, where $r$ is the
maximum cardinality of a common independent set.

###### Proof.

If AugmentMinRank halts in Step 1 or 2, then the output is clearly correct.
Moreover, by Lemma 3.3, the output in Step 4 is correct in the sense that the
same one can be returned in Step 2 of
Augment$[E,{\mathcal{I}}_{1},{\mathcal{I}}_{2},I]$. Since the running time
(including the number of oracle accesses) of AugmentMinRank is clearly
$\mathrm{O}(n^{2})$ and the number of calls of AugmentMinRank is $r+1$, the
total computational time is $\mathrm{O}(rn^{2})$. ∎

##  4 Consistent Exchangeability Graphs

For the weighted problem, we try to emulate Algorithm 2 using the modified
exchangeability graph. In contrast to cardinality augmentation, the extra arcs
may do harm in the following two senses (recall that our primary objective is
minimizing the cost of an $S_{I}$–$T_{I}$ path in $D[I]$):

  * •

they yield extra cycles whose cost may be negative, thus making it difficult
just to find a cheapest path in the graph;

  * •

some extra arcs may be traversed by a shortest cheapest
$S_{I}^{*}$–$T_{I}^{*}$ path in ${D^{\mathrm{min}}}[I;s^{*},t^{*}]$, for which
we may not obtain a better path in $D[I]$ by using a shortcut arc $(s^{*},y)$
or $(y,t^{*})$ (cf. Lemma 3.3).

In order to overcome these issues, we refine the modified exchangeability
graph in two steps.

First, we define ${D^{\mathrm{min}}}[I]=(E\setminus
I,I;{A^{\mathrm{min}}}[I])$ as the intersection of all possible candidates for
the modified exchangeability graphs after $S_{I}^{*}$ and $T_{I}^{*}$ are
defined by fixing $s^{*}\in S_{I}^{*}\setminus T_{I}^{*}$ and $t^{*}\in
T_{I}^{*}\setminus S_{I}^{*}$ with
${r_{\mathrm{min}}}(I+s^{*})={r_{\mathrm{min}}}(I+t^{*})=|I|$ and
${r_{\mathrm{min}}}(I+s^{*}+t^{*})=|I|+1$. In other words, we define
${A^{\mathrm{min}}}[I]\coloneqq{A_{1}^{\mathrm{min}}}[I]\cup{A_{2}^{\mathrm{min}}}[I]$,
where

$\displaystyle{A_{1}^{\mathrm{min}}}[I]$ $\displaystyle\coloneqq\bigcap_{t\in
T_{I}^{*}\setminus S_{I}^{*}}{A_{1}^{\mathrm{min}}}[I;s^{*},t],$
$\displaystyle{A_{2}^{\mathrm{min}}}[I]$ $\displaystyle\coloneqq\bigcap_{s\in
S_{I}^{*}\setminus T_{I}^{*}}{A_{2}^{\mathrm{min}}}[I;s,t^{*}].$

We here remark that ${A_{1}^{\mathrm{min}}}[I;s,t]$ and
${A_{2}^{\mathrm{min}}}[I;s,t]$ depend only on $t\in T_{I}^{*}\setminus
S_{I}^{*}$ and $s\in S_{I}^{*}\setminus T_{I}^{*}$, respectively (cf. (3.1)
and (3.2)). As with in the previous section, we assume that $S_{I}^{*}=S_{I}$
and $T_{I}^{*}=T_{I}$, and then Lemma 3.3 is strengthened as follows.

######  Lemma 4.1.

The graph ${D^{\mathrm{min}}}[I]$ satisfies the following properties.

  1. (a)

$A_{i}[I]\subseteq{A_{i}^{\mathrm{min}}}[I]$ for $i=1,2$. Moreover, if
$(u,v)\in{A^{\mathrm{min}}}[I]\setminus A[I]$, then $u,v\not\in S_{I}\cup
T_{I}$.

  2. (b)

If $(y,x)\in{A_{1}^{\mathrm{min}}}[I]\setminus A_{1}[I]$, then $(y,t)\in
A_{1}[I]$ for every $t\in T_{I}$. If
$(x,y)\in{A_{2}^{\mathrm{min}}}[I]\setminus A_{2}[I]$, then $(s,y)\in
A_{2}[I]$ for every $s\in S_{I}$.

In what follows, we call the exchangeability graph $D[I]=(E\setminus
I,I;A[I])$ the true graph. An arc $a\in{A^{\mathrm{min}}}[I]$ is true if $a\in
A[I]$, and fake otherwise. By Lemma 4.1, we can immediately determine that an
arc $a\in{A^{\mathrm{min}}}[I]$ is true if

  * •

$a$ is incident to $S_{I}\cup T_{I}$,

  * •

$a=(y,x)\in{A_{1}^{\mathrm{min}}}[I]$ and
$(y,t)\not\in{A_{1}^{\mathrm{min}}}[I]$ for some $t\in T_{I}$, or

  * •

$a=(x,y)\in{A_{2}^{\mathrm{min}}}[I]$ and
$(s,y)\not\in{A_{2}^{\mathrm{min}}}[I]$ for some $s\in S_{I}$.

These arcs are called sure, and the other arcs in ${A^{\mathrm{min}}}[I]$ are
called suspicious. We denote by
${A^{\mathrm{sure}}}[I]\subseteq{A^{\mathrm{min}}}[I]$ the set of sure arcs,
and define
${A^{\mathrm{susp}}}[I]\coloneqq{A^{\mathrm{min}}}[I]\setminus{A^{\mathrm{sure}}}[I]$.
In other words, we have
${A^{\mathrm{susp}}}[I]={A_{1}^{\mathrm{susp}}}[I]\cup{A_{2}^{\mathrm{susp}}}[I]$,
where

$\displaystyle{A_{1}^{\mathrm{susp}}}[I]$
$\displaystyle\coloneqq\left\\{\,(y,x)\in{A_{1}^{\mathrm{min}}}[I]\bigm{|}x\not\in
T_{I},~{}(y,t)\in{A_{1}^{\mathrm{min}}}[I]~{}(\forall t\in T_{I}\setminus
S_{I})\,\right\\},$ $\displaystyle{A_{2}^{\mathrm{susp}}}[I]$
$\displaystyle\coloneqq\left\\{\,(x,y)\in{A_{2}^{\mathrm{min}}}[I]\bigm{|}x\not\in
S_{I},~{}(s,y)\in{A_{2}^{\mathrm{min}}}[I]~{}(\forall s\in S_{I}\setminus
T_{I})\,\right\\}.$

If ${A^{\mathrm{susp}}}[I]=\emptyset$, then we conclude that
${D^{\mathrm{min}}}[I]$ is indeed the true graph $D[I]$, and we have to do
nothing more. Otherwise, as the second step, we further refine
${D^{\mathrm{min}}}[I]$ by fixing a possible true-fake configuration of the
suspicious arcs. To make a reasonable refinement, we check small local
exchanges. Specifically, we observe the values ${r_{\mathrm{min}}}((I\cup
X)\setminus Y)$ for all pairs $(X,Y)$ of $X\subseteq E\setminus(I\cup
S_{I}\cup T_{I})$ and $Y\subseteq I$ with $1\leq|X|\leq 2$ and $1\leq|Y|\leq
2$. We define the consistency with those observations as follows; roughly
speaking, a local exchange decreases the minimum rank value not so much (by
less than the number of removed elements) if and only if the local exchange
contains an exchangeable pair in each matroid.

######  Definition 4.2.

A pair $(X,Y)$ of $X\subseteq E\setminus(I\cup S_{I}\cup T_{I})$ and
$Y\subseteq I$ with $1\leq|X|\leq 2$ and $1\leq|Y|\leq 2$ is called a local
exchange pair or an LE-pair for short. An LE-pair $(X^{\prime},Y^{\prime})$ is
called a subpair of an LE-pair $(X,Y)$ if $X^{\prime}\subseteq X$ and
$Y^{\prime}\subseteq Y$, and a proper subpair if at least one inclusion is
strict.

######  Definition 4.3.

We say that a directed bipartite graph ${\tilde{D}}[I]=(E\setminus
I,I;{\tilde{A}}[I])$ is consistent with respect to an LE-pair $(X,Y)$ if the
following holds:

  * •

If ${r_{\mathrm{min}}}((I\cup X)\setminus Y)\geq|I|-|Y|+1$, then
${\tilde{A}}_{1}[I]\cap(Y\times X)\neq\emptyset$ and
${\tilde{A}}_{2}[I]\cap(X\times Y)\neq\emptyset$.

  * •

Otherwise (if ${r_{\mathrm{min}}}((I\cup X)\setminus Y)=|I|-|Y|$),
${\tilde{A}}_{1}[I]\cap(Y\times X)=\emptyset$ or
${\tilde{A}}_{2}[I]\cap(X\times Y)=\emptyset$.

We also say that ${\tilde{D}}[I]$ is overestimated or underestimated with
respect to an LE-pair $(X,Y)$ if ${\tilde{D}}[I]$ can be made consistent with
respect to $(X,Y)$ by removing or adding (possibly zero) arcs, respectively.
In particular, ${\tilde{D}}[I]$ is consistent with respect to $(X,Y)$ if and
only if ${\tilde{D}}[I]$ is both overestimated and underestimated with respect
to $(X,Y)$.

We provide some examples of LE-pairs and estimation using those pairs.

######  Example 4.4.

Consider an LE-pair $(X,Y)$ with $X=\\{x_{1},x_{2}\\}\subseteq
E\setminus(I\cup S_{I}\cup T_{I})$ and $Y=\\{y\\}\subseteq I$. Suppose that we
have ${r_{\mathrm{min}}}(I+x_{1}+x_{2}-y)=|I|$,
${r_{\mathrm{min}}}(I+x_{1}-y)=|I|-1$, and
${r_{\mathrm{min}}}(I+x_{2}-y)=|I|-1$. Then, a graph ${\tilde{D}}[I]$ is
consistent with respect to all the subpairs of $(X,Y)$ if and only if the
restriction of ${\tilde{D}}[I]$ to $X\cup Y$ has an arc set
$\\{(x_{1},y),(y,x_{2})\\}$ or $\\{(x_{2},y),(y,x_{1})\\}$. See (A) and (B) in
Figure 1. (C) and (D) in Figure 1 are examples of overestimation and
underestimation, respectively.

Figure 1: An illustration for Example 4.4.

######  Example 4.5.

Consider an LE-pair $(X,Y)$ with $X=\\{x_{1},x_{2}\\}\subseteq
E\setminus(I\cup S_{I}\cup T_{I})$ and $Y=\\{y_{1},y_{2}\\}\subseteq I$.
Suppose that we have ${r_{\mathrm{min}}}(I+x_{1}+x_{2}-y_{1}-y_{2})=|I|-1$,
${r_{\mathrm{min}}}(I+x_{1}+x_{2}-y_{i})=|I|-1~{}(i\in\\{1,2\\})$,
${r_{\mathrm{min}}}(I+x_{i}-y_{1}-y_{2})=|I|-2~{}(i\in\\{1,2\\})$, and
${r_{\mathrm{min}}}(I+x_{i}-y_{j})=|I|-1~{}(i,j\in\\{1,2\\})$. Then, a graph
${\tilde{D}}[I]$ is consistent with respect to all the subpairs of $(X,Y)$ if
and only if the restriction of ${\tilde{D}}[I]$ to $X\cup Y$ has an arc set
either $\\{(x_{1},y_{1}),(y_{2},x_{2})\\}$,
$\\{(x_{2},y_{2}),(y_{1},x_{1})\\}$, $\\{(x_{1},y_{2}),(y_{1},x_{2})\\}$, or
$\\{(x_{2},y_{1}),(y_{2},x_{1})\\}$. Figure 2 shows these four possible arc
sets. We will call this kind of LE-pairs evil (Definition 5.1) as they will be
the main obstacle in our approach described in Section 5.

Figure 2: An illustration for Example 4.5. All the four situations are
consistent.

######  Definition 4.6.

A directed bipartite graph ${\tilde{D}}[I]=(E\setminus I,I;{\tilde{A}}[I])$ is
called a consistent exchangeability graph (or, simply, consistent) if

  * •

${A^{\mathrm{sure}}}[I]\subseteq{\tilde{A}}[I]\subseteq{A^{\mathrm{min}}}[I]$,
and

  * •

${\tilde{D}}[I]$ is consistent with respect to all LE-pairs $(X,Y)$.

We also say that ${\tilde{D}}[I]$ is an overestimation/underestimation (or
overestimated/underestimated) if the above two conditions in which
“consistent” is replaced by “overestimated”/“underestimated” hold.

Note that a subgraph of a consistent exchangeability graph is an
underestimation, but the converse (an underestimation is a subgraph of some
consistent exchangeability graph) is not necessarily true. The condition of
underestimation just requires that it is underestimated with respect to each
LE-pair.

It is easy to observe from the definition that the true graph $D[I]$ is always
consistent. The following lemma guarantees that any consistent exchangeability
graph ${\tilde{D}}[I]$ is suitable for our purpose of finding a shortest
cheapest $S_{I}$–$T_{I}$ path in $D[I]$. Specifically, the property (2)
implies that $D[I]$ and ${\tilde{D}}[I]$ have the same shortest cheapest
$S_{I}$–$T_{I}$ paths in terms of the vertex sets. We define
${\mathcal{I}_{\mathrm{min}}^{k}}\coloneqq\\{\,I\subseteq
E\mid{r_{\mathrm{min}}}(I)=|I|=k\,\\}={\mathcal{I}}_{1}^{k}\cap{\mathcal{I}}_{2}^{k}$
for each $k=0,1,\dots,n$.

######  Lemma 4.7.

Let ${\tilde{D}}[I]$ be a consistent exchangeability graph, and $c$ be the
cost function defined as (2.1). If $I$ is $w$-maximal in
$\mathcal{I}_{\mathrm{min}}^{|I|}$, then the following properties hold.

  1. (1)

${\tilde{D}}[I]$ has no negative-cost cycle.

  2. (2)

For any shortest cheapest $S_{I}$–$T_{I}$ path ${\tilde{P}}$ in
${\tilde{D}}[I]$, there exists an $S_{I}$–$T_{I}$ path $P$ in $D[I]$ with
$P={\tilde{P}}$ as the vertex sets. The same is true if we interchange
${\tilde{D}}[I]$ and $D[I]$.

Before proving this lemma, we prepare two specific lemmas.

######  Lemma 4.8.

Let ${\tilde{D}}[I]$ and ${\tilde{D}}^{\prime}[I]$ be a consistent and
underestimated exchangeability graph, respectively. Then, any cycle
${\tilde{Q}}^{\prime}$ in ${\tilde{D}}^{\prime}[I]$ can be partitioned into
disjoint cycles in $D[I]$.

###### Proof.

Fix a cycle ${\tilde{Q}}^{\prime}$ in ${\tilde{D}}^{\prime}[I]$. It suffices
to show that there exist perfect matchings on ${\tilde{Q}}^{\prime}$ both in
${\tilde{A}}_{1}[I]$ and in ${\tilde{A}}_{2}[I]$, whose union partitions
${\tilde{Q}}^{\prime}$ into cycles in ${\tilde{D}}[I]=(E\setminus
I,I;{\tilde{A}}[I])$. By symmetry, we focus on
${\tilde{A}}_{2}[I]={\tilde{A}}[I]\cap((E\setminus I)\times I)$.

Suppose to the contrary that ${\tilde{A}}_{2}[I]$ has no perfect matching on
${\tilde{Q}}^{\prime}$. Then, by Hall’s theorem [12] (see, e.g., [23, Theorem
22.1]), there exists a subset $Y\subseteq{\tilde{Q}}^{\prime}\cap I$ such that
$|X|<|Y|$, where
$X\coloneqq\Gamma_{{\tilde{A}}_{2}[I]}(Y)\cap({\tilde{Q}}^{\prime}\setminus
I)$ and
$\Gamma_{{\tilde{A}}_{2}[I]}(Y)\coloneqq\\{\,x\mid(x,y)\in{\tilde{A}}_{2}[I],~{}y\in
Y\,\\}$. Since ${\tilde{Q}}^{\prime}$ is a cycle in ${\tilde{D}}^{\prime}[I]$,
it contains two arcs $(z_{1},y_{1}),(y_{2},z_{2})$ such that
$z_{1},z_{2}\in{\tilde{Q}}^{\prime}\setminus(I\cup X)$ and $y_{1},y_{2}\in Y$
(possibly, $z_{1}=z_{2}$ or $y_{1}=y_{2})$. Let $Z^{\prime}=\\{z_{1},z_{2}\\}$
and $Y^{\prime}=\\{y_{1},y_{2}\\}$. Since ${\tilde{D}}^{\prime}[I]$ is
underestimated with respect to $(Z^{\prime},Y^{\prime})$, we have
${r_{\mathrm{min}}}((I\cup Z^{\prime})\setminus
Y^{\prime})\geq|I|-|Y^{\prime}|+1$. Then, the consistency of ${\tilde{D}}[I]$
with respect to $(Z^{\prime},Y^{\prime})$ implies that
$(z_{i},y_{j})\in{\tilde{A}}_{2}[I]$ for some $i,j\in\\{1,2\\}$, which
contradicts the definition of $X$. ∎

######  Lemma 4.9.

Let ${\tilde{D}}[I]$ and ${\tilde{D}}^{\prime}[I]$ be a consistent and
underestimated exchangeability graph, respectively. Then, any $S_{I}$–$T_{I}$
path ${\tilde{P}}^{\prime}$ in ${\tilde{D}}^{\prime}[I]$ can be partitioned
into a disjoint family of an $S_{I}$–$T_{I}$ path and cycles in
${\tilde{D}}[I]$.

###### Proof.

Fix an $S_{I}$–$T_{I}$ path ${\tilde{P}}^{\prime}$ in
${\tilde{D}}^{\prime}[I]$, and let $s\in S_{I}$ and $t\in T_{I}$ denote its
end vertices. It suffices to show that there exist perfect matchings on
${\tilde{P}}^{\prime}-s$ in ${\tilde{A}}_{1}[I]$ and on
${\tilde{P}}^{\prime}-t$ in ${\tilde{A}}_{2}[I]$, whose union forms a desired
family. By symmetry, we focus on
${\tilde{A}}_{2}[I]={\tilde{A}}[I]\cap((E\setminus I)\times I)$.

Suppose to the contrary that ${\tilde{A}}_{2}[I]$ has no perfect matching on
${\tilde{P}}^{\prime}-t$. Then, by Hall’s theorem, again, there exists a
subset $Y\subseteq{\tilde{P}}^{\prime}\cap I$ such that $|X|<|Y|$, where
$X\coloneqq\Gamma_{{\tilde{A}}_{2}[I]}(Y)\cap({\tilde{P}}^{\prime}\setminus(I+t))$.
Since ${\tilde{P}}^{\prime}$ is an $s$–$t$ path in ${\tilde{D}}^{\prime}[I]$,
it contains an arc $a=(z_{1},y_{1})$ such that
$z_{1}\in{\tilde{P}}^{\prime}\setminus(I\cup X+t)$ and $y_{1}\in Y$. By the
definition of $X$, we have $a\not\in{\tilde{A}}_{2}[I]$, and hence
$a\in{A^{\mathrm{susp}}}[I]$ (as ${\tilde{D}}^{\prime}[I]$ is an
underestimation,
${A_{2}^{\mathrm{sure}}}[I]\subseteq{\tilde{A}}_{2}[I]\subseteq{A_{2}^{\mathrm{sure}}}[I]\cup{A_{2}^{\mathrm{susp}}}[I]$).
We then have $z_{1}\neq s\in X$ by Lemma 4.1. Since the $s$–$t$ path
${\tilde{P}}^{\prime}$ does not use any arc entering $s\in X$ and we have
$|X|<|Y|$, it uses at least two arcs from $Y$ to
${\tilde{P}}^{\prime}\setminus(I\cup X)$. Hence, ${\tilde{P}}^{\prime}$
contains an arc $(y_{2},z_{2})$ such that
$z_{2}\in{\tilde{P}}^{\prime}\setminus(I\cup X+t)$ and $y_{2}\in Y$ (possibly,
$z_{1}=z_{2}$ or $y_{1}=y_{2})$. Let $Z^{\prime}=\\{z_{1},z_{2}\\}$ and
$Y^{\prime}=\\{y_{1},y_{2}\\}$. Since ${\tilde{D}}^{\prime}[I]$ is
underestimated with respect to $(Z^{\prime},Y^{\prime})$, we have
${r_{\mathrm{min}}}((I\cup Z^{\prime})\setminus
Y^{\prime})\geq|I|-|Y^{\prime}|+1$. Then, the consistency of ${\tilde{D}}[I]$
implies that $(z_{i},y_{j})\in{\tilde{A}}_{2}[I]$ for some $i,j\in\\{1,2\\}$,
which contradicts the definition of $X$. ∎

Now we are ready to prove Lemma 4.7.

###### Proof of Lemma 4.7.

We obtain the property (1) as follows. By Lemma 4.8, any cycle ${\tilde{Q}}$
in ${\tilde{D}}[I]$ can be partitioned into disjoint cycles in $D[I]$, each of
whose cost is nonnegative by Lemma 2.5.

Similarly, we obtain the property (2) as follows. Fix a shortest cheapest
$S_{I}$–$T_{I}$ path ${\tilde{P}}$ in ${\tilde{D}}[I]$. Then, by Lemma 4.9,
${\tilde{P}}$ can be partitioned into a disjoint family of an $S_{I}$–$T_{I}$
path $P$ and cycles in $D[I]$. By Lemma 4.9 (with interchanging the role of
${\tilde{D}}[I]$ and ${\tilde{D}}^{\prime}[I]$), $P$ can be partitioned into a
disjoint family of an $S_{I}$–$T_{I}$ path $\tilde{P}^{\prime}$ and cycles in
${\tilde{D}}[I]$. We then have $|{\tilde{P}}|\geq|P|\geq|\tilde{P}^{\prime}|$.
Moreover, by Lemma 2.5 and the property (1), we have $c({\tilde{P}})\geq
c(P)\geq c(\tilde{P}^{\prime})$. As ${\tilde{P}}$ is a shortest cheapest
$S_{I}$–$T_{I}$ path in ${\tilde{D}}[I]$, all the inequalities hold with
equality, which implies $P={\tilde{P}}$. The interchanged version of the
property (2) is shown in the same manner, which completes the proof. ∎

By Lemma 4.7, assuming that a consistent exchangeability graph can be found
(in Step 4), Algorithm 4 correctly emulates Algorithm 2 (up to the symmetry of
${\mathbf{M}}_{1}$ and ${\mathbf{M}}_{2}$).

1

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

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

2

3If ${r_{\mathrm{min}}}(I+s+t)=|I|$ for every $s,t\in E\setminus I$, then halt
with returning $Z=E$.

4If no pair $(s,t)$ satisfies
${r_{\mathrm{min}}}(I+s)={r_{\mathrm{min}}}(I+t)=|I|$ and
${r_{\mathrm{min}}}(I+s+t)=|I|+1$, then return $J=I+x^{*}$ for any
$x^{*}\in\arg\,\max\left\\{\,w(x)\mid x\in E\setminus
I,~{}{r_{\mathrm{min}}}(I+x)=|I|+1\,\right\\}$.

5Compute $S_{I}^{*}$ and $T_{I}^{*}$ by fixing a pair $(s^{*},t^{*})$ that
satisfies ${r_{\mathrm{min}}}(I+s^{*})={r_{\mathrm{min}}}(I+t^{*})=|I|$ and
${r_{\mathrm{min}}}(I+s^{*}+t^{*})=|I|+1$, and create the graph
${D^{\mathrm{min}}}[I]$ by taking the intersection of
${D^{\mathrm{min}}}[I;s^{*},t]$ and ${D^{\mathrm{min}}}[I;s,t^{*}]$ for all
$t\in T_{I}^{*}\setminus S_{I}^{*}$ and $s\in S_{I}^{*}\setminus T_{I}^{*}$,
respectively.

6Observe the values ${r_{\mathrm{min}}}((I\cup X)\setminus Y)$ for all LE-
pairs $(X,Y$), and find a consistent exchangeability graph ${\tilde{D}}[I]$.

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

Algorithm 4 (CheapestPathAugmentMinRank$[E,{r_{\mathrm{min}}},I]$).

######  Lemma 4.10.

Algorithm 4 returns a correct output.

The only remaining issue is how to find a consistent exchangeability graph
efficiently in Step 4. Unfortunately, this is NP-hard in general (Section 6),
but we can find an “almost consistent” exchangeability graph, which is enough
to solve several special cases by this approach (Section 5).

######  Remark 4.11.

Lemma 4.8 together with Lemma 2.5 implies that the weighted matroid
intersection problem under the minimum rank oracle enjoys an
$(\mathrm{NP}\cap\mathrm{coNP})$-like feature. On the one hand, if the given
instance has a common independent set $I$ with $|I|=k$ and $w(I)\geq\alpha$,
then such $I$ itself is a certificate. On the other hand, if the given
instance has no such common independent set, then a pair of a $w$-maximal
common independent set $I$ in ${\mathcal{I}_{\mathrm{min}}^{k}}$ (with
$w(I)<\alpha$) and a consistent exchangeability graph ${\tilde{D}}[I]$ having
no negative cycle is a certificate. This may be one positive evidence that
enables us to hope that this problem is tractable in general.

##  5 Almost Consistent Exchangeability Graphs via 2-SAT

In this section, we show that an almost consistent exchangeability graph can
be obtained in polynomial time by solving the 2-SAT problem, which is enough
in several special cases. Specifically, we observe that all but one condition
of the consistency in Definition 4.3 can be formulated by 2-CNF. The following
definition corresponds to the unique difficult case, which is also utilized
for the proof of NP-hardness of finding a consistent exchangeability graph in
general.

######  Definition 5.1 (cf. Example 4.5).

An LE-pair $(X,Y)$ is said to be evil if

  * •

$|X|=|Y|=2$,

  * •

${r_{\mathrm{min}}}((I\cup X)\setminus Y)=|I|-1\ (=|I|-|Y|+1)$, and

  * •

${r_{\mathrm{min}}}((I\cup X^{\prime})\setminus Y^{\prime})=|I|-|Y^{\prime}|$
for every proper subpair $(X^{\prime},Y^{\prime})$ of $(X,Y)$.

######  Definition 5.2.

A directed bipartite graph ${\tilde{D}}[I]=(E\setminus I,I;{\tilde{A}}[I])$ is
called an almost consistent exchangeability graph (or, simply, almost
consistent) if

  * •

${A^{\mathrm{sure}}}[I]\subseteq{\tilde{A}}[I]\subseteq{A^{\mathrm{min}}}[I]$,

  * •

${\tilde{D}}[I]$ is consistent with respect to all non-evil LE-pairs $(X,Y)$,

  * •

${\tilde{D}}[I]$ is underestimated with respect to all evil LE-pairs $(X,Y)$,
and

  * •

if ${\tilde{D}}[I]$ is not consistent with respect to an evil LE-pair $(X,Y)$,
then ${\tilde{A}}[I]$ contains no arc between $X$ and $Y$.

In particular, any consistent exchangeability graph $D[I]$ is almost
consistent.

###  5.1 2-SAT Formulation

To find an almost consistent exchangeability graph ${\tilde{D}}[I]=(E\setminus
I,I;{\tilde{A}}[I])$, for each suspicious arc $a\in{A^{\mathrm{susp}}}[I]$, we
introduce one associated variable $z_{a}$ such that $z_{a}=\text{\sc True}$
means $a\in{\tilde{A}}[I]$. For the sake of simplicity, we introduce a
constant $z_{a}=\text{\sc True}$ for each arc $a\in{A^{\mathrm{sure}}}[I]$,
and $z_{a}=\text{\sc False}$ for each pair
$a=(u,v)\not\in{A^{\mathrm{min}}}[I]$ with either $u\in E\setminus(I\cup
S_{I}\cup T_{I})$ and $v\in I$ or $u\in I$ and $v\in E\setminus(I\cup
S_{I}\cup T_{I})$.

Let $r$ denote the maximum cardinality of a common independent set. Then, the
number of variables is $\mathrm{O}(rn)$, and the following lemma implies that
one can obtain an almost consistent exchangeability graph
${\tilde{D}}[I]=(E\setminus I,I;{\tilde{A}}[I])$ in $\mathrm{O}(r^{2}n^{2})$
time, since 2-SAT can be solved in time linear in the number of variables and
clauses of the input 2-CNF [18, 1].

######  Lemma 5.3.

There exists a 2-CNF $\psi(z)$ on the variables
$z=(z_{a})_{a\in{A^{\mathrm{susp}}}[I]}$ consisting of
$\mathrm{O}(r^{2}n^{2})$ clauses such that $\psi(z)$ is satisfiable and each
satisfying assignment $\tilde{z}\in\\{\text{\sc True},\text{\sc
False}\\}^{{A^{\mathrm{susp}}}[I]}$ corresponds to an almost consistent
exchangeability graph ${\tilde{D}}[I]=(E\setminus I,I;{\tilde{A}}[I])$.

###### Proof.

We define a set ${\mathcal{C}}_{X,Y}$ of at most eight clauses each of which
contains at most two variables for each LE-pair $(X,Y)$. Note that there are
$\mathrm{O}(r^{2}n^{2})$ such pairs.

#### Case 1.1. When $|X|=1$ and $|Y|=1$.

Suppose that $X=\\{x\\}$ and $Y=\\{y\\}$, and let $a=(x,y)$ and $b=(y,x)$. We
then have two possibilities ${r_{\mathrm{min}}}(I+x-y)=|I|$ and
${r_{\mathrm{min}}}(I+x-y)=|I|-1$.

When ${r_{\mathrm{min}}}(I+x-y)=|I|$, both $a$ and $b$ must be included in
${\tilde{D}}[I]$. We then define
${\mathcal{C}}_{X,Y}\coloneqq\\{C_{X,Y}^{1},C_{X,Y}^{2},C_{X,Y}^{3}\\}$ with

$C_{X,Y}^{1}\coloneqq(z_{a}\vee z_{b}),\quad C_{X,Y}^{2}\coloneqq(\neg
z_{a}\vee z_{b}),\quad C_{X,Y}^{3}\coloneqq(z_{a}\vee\neg z_{b}).$

It is easy to see that ${\mathcal{C}}_{X,Y}$ is satisfied if and only if
$z_{a}=z_{b}=\text{\sc True}$, which coincides with the desired consistency
condition.

When ${r_{\mathrm{min}}}(I+x-y)=|I|-1$, at least one of $a$ and $b$ must be
excluded from ${\tilde{D}}[I]$. We then define
${\mathcal{C}}_{X,Y}\coloneqq\\{C_{X,Y}^{1}\\}$ with

$C_{X,Y}^{1}\coloneqq(\neg z_{a}\vee\neg z_{b}).$

It is easy to see that ${\mathcal{C}}_{X,Y}$ is satisfied if and only if
$z_{a}=\text{\sc False}$ or $z_{b}=\text{\sc False}$, which coincides with the
desired consistency condition.

#### Case 1.2. When $|X|=1$ and $|Y|=2$.

Suppose that $X=\\{x\\}$ and $Y=\\{y_{1},y_{2}\\}$, and let $a_{i}=(x,y_{i})$
and $b_{i}=(y_{i},x)$ for $i=1,2$. We then have two possibilities
${r_{\mathrm{min}}}(I+x-y_{1}-y_{2})=|I|-1$ and
${r_{\mathrm{min}}}(I+x-y_{1}-y_{2})=|I|-2$.

When ${r_{\mathrm{min}}}(I+x-y_{1}-y_{2})=|I|-1$, at least one of $a_{1}$ and
$a_{2}$ and at least one of $b_{1}$ and $b_{2}$ must be included in
${\tilde{D}}[I]$. This condition is simply represented by two clauses
${\mathcal{C}}_{X,Y}\coloneqq\\{C_{X,Y}^{1},C_{X,Y}^{2}\\}$ such that

$C_{X,Y}^{1}\coloneqq(z_{a_{1}}\vee z_{a_{2}}),\quad
C_{X,Y}^{2}\coloneqq(z_{b_{1}}\vee z_{b_{2}}).$

When ${r_{\mathrm{min}}}(I+x-y_{1}-y_{2})=|I|-2$, both $a_{1}$ and $a_{2}$ or
both $b_{1}$ and $b_{2}$ must be excluded from ${\tilde{D}}[I]$. This
condition is represented by four clauses

$C_{X,Y}^{1}\coloneqq(\neg z_{a_{1}}\vee\neg z_{b_{2}}),\
C_{X,Y}^{2}\coloneqq(\neg z_{a_{2}}\vee\neg z_{b_{1}}),\
C_{X,Y}^{3}\coloneqq(\neg z_{a_{1}}\vee\neg z_{b_{1}}),\
C_{X,Y}^{4}\coloneqq(\neg z_{a_{2}}\vee\neg z_{b_{2}}).$

Since ${r_{\mathrm{min}}}(I+x-y_{1}-y_{2})=|I|-2$ implies
${r_{\mathrm{min}}}(I+x-y_{i})=|I|-1$ for each $i\in\\{1,2\\}$, the latter two
clauses $C_{X,Y}^{3}$ and $C_{X,Y}^{4}$ have already been introduced as
$C_{x,y_{1}}^{1}$ and $C_{x,y_{2}}^{1}$, respectively, in Case 1.1. Thus, we
define ${\mathcal{C}}_{X,Y}\coloneqq\\{C_{X,Y}^{1},C_{X,Y}^{2}\\}$, and we are
done.

#### Case 2.1. When $|X|=2$ and $|Y|=1$.

Suppose that $X=\\{x_{1},x_{2}\\}$ and $Y=\\{y\\}$, and let $a_{i}=(x_{i},y)$
and $b_{i}=(y,x_{i})$ for $i=1,2$. We then have two possibilities
${r_{\mathrm{min}}}(I+x_{1}+x_{2}-y)=|I|$ and
${r_{\mathrm{min}}}(I+x_{1}+x_{2}-y)=|I|-1$. Each case is analogous to Case
1.2.

When ${r_{\mathrm{min}}}(I+x_{1}+x_{2}-y)=|I|$, at least one of $a_{1}$ and
$a_{2}$ and at least one of $b_{1}$ and $b_{2}$ must be included in
${\tilde{D}}[I]$. This condition is simply represented by two clauses
${\mathcal{C}}_{X,Y}\coloneqq\\{C_{X,Y}^{1},C_{X,Y}^{2}\\}$ such that

$C_{X,Y}^{1}\coloneqq(z_{a_{1}}\vee z_{a_{2}}),\quad
C_{X,Y}^{2}\coloneqq(z_{b_{1}}\vee z_{b_{2}}).$

When ${r_{\mathrm{min}}}(I+x_{1}+x_{2}-y)=|I|-1$, both $a_{1}$ and $a_{2}$ or
both $b_{1}$ and $b_{2}$ must be excluded from ${\tilde{D}}[I]$. This
condition is represented by four clauses

$C_{X,Y}^{1}\coloneqq(\neg z_{a_{1}}\vee\neg z_{b_{2}}),\
C_{X,Y}^{2}\coloneqq(\neg z_{a_{2}}\vee\neg z_{b_{1}}),\
C_{X,Y}^{3}\coloneqq(\neg z_{a_{1}}\vee\neg z_{b_{1}}),\
C_{X,Y}^{4}\coloneqq(\neg z_{a_{2}}\vee\neg z_{b_{2}}).$

Since ${r_{\mathrm{min}}}(I+x_{1}+x_{2}-y)=|I|-1$ implies
${r_{\mathrm{min}}}(I+x_{i}-y)=|I|-1$ for each $i\in\\{1,2\\}$, the latter two
clauses $C_{X,Y}^{3}$ and $C_{X,Y}^{4}$ have already been introduced as
$C_{x_{1},y}^{1}$ and $C_{x_{2},y}^{1}$, respectively, in Case 1.1. Thus, we
define ${\mathcal{C}}_{X,Y}\coloneqq\\{C_{X,Y}^{1},C_{X,Y}^{2}\\}$, and we are
done.

#### Case 2.2. When $|X|=2$ and $|Y|=2$.

Suppose that $X=\\{x_{1},x_{2}\\}$ and $Y=\\{y_{1},y_{2}\\}$, and let
$a_{i,j}=(x_{i},y_{j})$ and $b_{i,j}=(y_{j},x_{i})$ for $i=1,2$ and $j=1,2$.
We then have three possible values $|I|$, $|I|-1$, and $|I|-2$ of
${r_{\mathrm{min}}}(I+x_{1}+x_{2}-y_{1}-y_{2})$.

When ${r_{\mathrm{min}}}(I+x_{1}+x_{2}-y_{1}-y_{2})=|I|$, at least one of
$a_{i,j}$ and at least one of $b_{i,j}$ must be included in ${\tilde{D}}[I]$.
In this case, this is simply satisfied due to the clauses already introduced
in Cases 1.2 and 2.1, since we have
${r_{\mathrm{min}}}(I+x_{1}+x_{2}-y_{i})=|I|$ and
${r_{\mathrm{min}}}(I+x_{i}-y_{1}-y_{2})=|I|-1$ for any $i\in\\{1,2\\}$. Thus,
it suffices to set ${\mathcal{C}}_{X,Y}=\emptyset$.

When ${r_{\mathrm{min}}}(I+x_{1}+x_{2}-y_{1}-y_{2})=|I|-2$, all of $a_{i,j}$
or all of $b_{i,j}$ must be excluded from ${\tilde{D}}[I]$. In this case, we
have ${r_{\mathrm{min}}}((I\cup X^{\prime})\setminus
Y^{\prime})=|I|-|Y^{\prime}|$ for any subpair $(X^{\prime},Y^{\prime})$ of
$(X,Y)$. The consistency with respect to the proper subpairs
$(X^{\prime},Y^{\prime})$ implies (i.e., the clauses already introduced in
Cases 1.1, 1.2, and 2.1 impose) that for each $i,j,k\in\\{1,2\\}$ (possibly,
$i=k$), at least one of $a_{i,j}$ and $b_{k,j}$ is excluded from
${\tilde{A}}[I]$ and at least one of $b_{i,j}$ and $a_{k,j}$ is excluded from
${\tilde{A}}[I]$. Thus, the remaining possibility that we have to reject is
that ${\tilde{D}}[I]$ has two arcs $a_{i,j}$ and $b_{3-i,3-j}$ for some
$i,j\in\\{1,2\\}$. We then define
${\mathcal{C}}_{X,Y}\coloneqq\\{C_{X,Y}^{1},C_{X,Y}^{2},C_{X,Y}^{3},C_{X,Y}^{4}\\}$
with

$C_{X,Y}^{1}\coloneqq(\neg z_{a_{1,1}}\vee\neg z_{b_{2,2}}),\
C_{X,Y}^{2}\coloneqq(\neg z_{a_{1,2}}\vee\neg z_{b_{2,1}}),\
C_{X,Y}^{3}\coloneqq(\neg z_{a_{2,1}}\vee\neg z_{b_{1,2}}),\
C_{X,Y}^{4}\coloneqq(\neg z_{a_{2,2}}\vee\neg z_{b_{1,1}}).$

It is easy to see that ${\mathcal{C}}_{X,Y}$ is satisfied if and only if
$z_{a_{i,j}}=\text{\sc False}$ or $z_{b_{3-i,3-j}}=\text{\sc False}$ for each
$i,j\in\\{1,2\\}$, which coincides with what we have to do.

When ${r_{\mathrm{min}}}(I+x_{1}+x_{2}-y_{1}-y_{2})=|I|-1$, we separately
consider two cases. Suppose that $(X,Y)$ is not evil, i.e.,
${r_{\mathrm{min}}}((I\cup X^{\prime})\setminus
Y^{\prime})\geq|I|-|Y^{\prime}|+1$ for some proper subpair
$(X^{\prime},Y^{\prime})$ of $(X,Y)$. In this case, the consistency with
respect to $(X^{\prime},Y^{\prime})$ implies (i.e., the clauses already
introduced in Cases 1.1, 1.2, or 2.1 impose) the consistency with respect to
$(X,Y)$. Thus, it suffices to set ${\mathcal{C}}_{X,Y}=\emptyset$.

Otherwise, $(X,Y)$ is evil, i.e., ${r_{\mathrm{min}}}((I\cup
X^{\prime})\setminus Y^{\prime})=|I|-|Y^{\prime}|$ for any proper subpair
$(X^{\prime},Y^{\prime})$ of $(X,Y)$. In this case, as seen in the second last
paragraph, the consistency with respect to such LE-pairs
$(X^{\prime},Y^{\prime})$ implies (i.e., the clauses already introduced in
Cases 1.1, 1.2, and 2.1 impose) that for each $i,j,k\in\\{1,2\\}$ (possibly,
$i=k$), at least one of $a_{i,j}$ and $b_{k,j}$ is excluded from
${\tilde{A}}[I]$ and at least one of $b_{i,j}$ and $a_{k,j}$ is excluded from
${\tilde{A}}[I]$. Thus, for the consistency with respect to $(X,Y)$, there
must exist a pair of arcs $a_{i,j}$ and $b_{3-j,3-i}$ for exactly one pair
$(i,j)$ with $i,j\in\\{1,2\\}$ (cf. Example 4.5). We then define
${\mathcal{C}}_{X,Y}\coloneqq\\{C_{X,Y}^{1},C_{X,Y}^{2},\dots,C_{X,Y}^{8}\\}$
with

$\displaystyle C_{X,Y}^{1}\coloneqq(\neg z_{a_{1,1}}\vee z_{b_{2,2}}),\
C_{X,Y}^{2}\coloneqq(\neg z_{a_{1,2}}\vee z_{b_{2,1}}),\
C_{X,Y}^{3}\coloneqq(\neg z_{a_{2,1}}\vee z_{b_{1,2}}),\
C_{X,Y}^{4}\coloneqq(\neg z_{a_{2,2}}\vee z_{b_{1,1}}),$ $\displaystyle
C_{X,Y}^{5}\coloneqq(z_{a_{1,1}}\vee\neg z_{b_{2,2}}),\
C_{X,Y}^{6}\coloneqq(z_{a_{1,2}}\vee\neg z_{b_{2,1}}),\
C_{X,Y}^{7}\coloneqq(z_{a_{2,1}}\vee\neg z_{b_{1,2}}),\
C_{X,Y}^{8}\coloneqq(z_{a_{2,2}}\vee\neg z_{b_{1,1}}).$

We observe that $C_{X,Y}^{1}$ and $C_{X,Y}^{5}$ are both satisfied if and only
if $z_{a_{1,1}}=z_{b_{2,2}}$, and the similar equivalence holds for the other
three pairs of clauses. Hence, ${\mathcal{C}}_{X,Y}$ is satisfied in addition
to the clauses already introduced in Cases 1.1, 1.2, and 2.1 if and only if
$z_{a_{i,j}}=z_{b_{3-i,3-j}}$ for every $i,j\in\\{1,2\\}$ and
$z_{a_{i,j}}=z_{b_{3-i,3-j}}=\text{\sc True}$ for at most one pair $(i,j)$. If
$z_{a_{i,j}}=z_{b_{3-i,3-j}}=\text{\sc True}$ for some pair $(i,j)$, then
${\tilde{D}}[I]$ is consistent with respect to $(X,Y)$; otherwise, all the
eight variables $z_{a_{i,j}},z_{b_{i,j}}$ appearing here take False and
${\tilde{D}}[I]$ is underestimated with respect to $(X,Y)$.

Overall, by at most eight clauses each of which contains at most two
variables, as required in Definition 5.2, we can exactly represent the
consistency with respect to every non-evil LE-pair, and we can impose that
${\tilde{D}}[I]$ is underestimated with respect to every evil LE-pair so that
if ${\tilde{D}}[I]$ is not consistent with respect to an evil LE-pair $(X,Y)$,
then ${\tilde{A}}[I]$ contains no edge between $X$ and $Y$. This completes the
proof. ∎

###  5.2 Tractable Special Cases

We demonstrate several special cases that can be solved by this $2$-SAT
underestimation approach. Recall that $r$ denotes the maximum cardinality of a
common independent set.

First, if no circuit in one matroid is included in any circuit in the other
matroid, then one can solve the weighted matroid intersection problem in
polynomial time only using the minimum rank oracle. This special case already
includes the cases of bipartite matching and arborescence (in simple graphs).

######  Theorem 5.4.

Suppose that for any pair of a circuit $C_{1}$ in $\mathbf{M}_{1}$ and a
circuit $C_{2}$ in $\mathbf{M}_{2}$, we have $C_{2}\setminus
C_{1}\neq\emptyset$. Then, for any weight function $w\colon E\to\mathbb{R}$, a
$w$-maximal common independent set in ${\mathcal{I}_{\mathrm{min}}^{k}}$ for
each cardinality $k=0,1,\dots,r$ can be found in $\mathrm{O}(r^{3}n^{2})$ time
only using the minimum rank oracle.

###### Proof.

We obtain this result by combining Algorithm 4 and Lemma 5.3. Specifically,
under the assumption of this lemma, any almost consistent exchangeability
graph ${\tilde{D}}[I]$ is in fact consistent. Note that the computational time
of finding a shortest cheapest $S_{I}^{*}$–$T_{I}^{*}$ path in
${\tilde{D}}[I]$ in Step 5 is $\mathrm{O}(rn^{2})$ (using the Bellman–Ford
algorithm), which is not a bottleneck.

To see the consistency of ${\tilde{D}}[I]$, it suffices to show that
underestimation with respect to any evil LE-pair cannot occur. Let $(X,Y)$ be
an evil LE-pair. As Case 2.2 in the proof of Lemma 5.3, suppose that
$X=\\{x_{1},x_{2}\\}$ and $Y=\\{y_{1},y_{2}\\}$, and let
$a_{i,j}=(x_{i},y_{j})$ and $b_{i,j}=(y_{j},x_{i})$ for $i=1,2$ and $j=1,2$.
We show that for at least one pair $(i,j)$, we must have
$a_{i,j}\in{\tilde{A}}[I]$ or $b_{i,j}\in{\tilde{A}}[I]$, which implies that
${\tilde{D}}[I]$ is consistent with $(X,Y)$ (recall that the only possible
underestimation is that all of the eight arcs between $X$ and $Y$ are excluded
from ${\tilde{D}}[I]$).

Since ${r_{\mathrm{min}}}((I\cup X)\setminus Y)=|I|-1=|I|-|Y|+1$, there exists
at least one arc $(y_{i},x_{j})\in A[I]$ (in the true graph). By the symmetry,
we assume $(y_{1},x_{1})\in A[I]$. This means that $y_{1}$ is in the
fundamental circuit $C_{1}(I,x_{1})$ of $x_{1}$ with respect to $I$ in
$\mathbf{M}_{1}$. By the assumption of the lemma, the fundamental circuit
$C_{2}(I,x_{1})$ in the other matroid $\mathbf{M}_{2}$ contains some element
$y^{\prime}\not\in C_{1}(I,x_{1})$.

Consider an LE-pair
$(X^{\prime},Y^{\prime})=(\\{x_{1}\\},\\{y_{1},y^{\prime}\\})$. Since
$y^{\prime}\in C_{2}(I,x_{1})\setminus C_{1}(I,x_{1})$, we have
${r_{\mathrm{min}}}(I+x_{1}-y^{\prime})=r_{1}(I+x_{1}-y^{\prime})=|I|-1$.
Also, as $(X,Y)$ is evil, we have ${r_{\mathrm{min}}}(I+x_{1}-y_{1})=|I|-1$.
Finally, since $y_{1}\in C_{1}(I,x_{1})$ and $y^{\prime}\in C_{2}(I,x_{1})$,
we have ${r_{\mathrm{min}}}(I+x_{1}-y_{1}-y^{\prime})=|I|-1$. Thus, the
consistency with respect to the subpairs of $(X^{\prime},Y^{\prime})$ implies
either $a_{1,1}\in{\tilde{A}}[I]$ or $b_{1,1}\in{\tilde{A}}[I]$, which
completes the proof. ∎

######  Remark 5.5.

The condition of Theorem 5.4 raises the following problem: can we decide if
there exists a circuit $C$ in $\mathbf{M}_{1}$ that is dependent in
$\mathbf{M}_{2}$? This problem is hard even if an oracle access (or linear
representation) is available for both matroids. To see this, let $G=(V,E)$ be
an undirected graph, set $\mathbf{M}_{1}$ to be the graphic matroid of $G$ and
$\mathbf{M}_{2}$ be the uniform matroid of rank $|V|-1$. Then, there exists a
circuit $C$ in $\mathbf{M}_{1}$ that is dependent in $\mathbf{M}_{2}$ if and
only if $G$ has a Hamiltonian cycle.

A similar discussion can lead to an FPT algorithm parameterized by the size of
largest circuits. This implies that the case when one matroid is a partition
matroid with constant upper bounds is tractable.

######  Theorem 5.6.

Let $\gamma_{i}$ be the size of largest circuits in $\mathbf{M}_{i}$, and
$\gamma=\min\\{\gamma_{1},\gamma_{2}\\}$. Then, for any weight function
$w\colon E\to\mathbb{R}$, a $w$-maximal common independent set in
${\mathcal{I}_{\mathrm{min}}^{k}}$ for each cardinality $k=0,1,\dots,r$ can be
found in $\mathrm{O}(2^{\gamma}r^{3}n^{2})$ time only using the minimum rank
oracle.

###### Proof.

Without loss of generality, we assume $\gamma=\gamma_{2}$. Then, each $x\in
E\setminus(I\cup T_{I})$ has at most $\gamma$ outgoing arcs in $A_{2}[I]$. In
particular, by Lemma 4.1, there are at most $\gamma$ elements in $I$ that have
arcs in ${A_{2}^{\mathrm{min}}}[I]$ from all the elements in $S_{I}$ (that are
sure), and only those elements can have a suspicious arc in
${A_{2}^{\mathrm{susp}}}[I]$. Let $J\subseteq I$ be the set of such elements
(that have a suspicious arc in ${A_{2}^{\mathrm{susp}}}[I]$). We then guess a
subset $J^{\prime}\subseteq J$ such that

$J^{\prime}=\\{\,y\in J\mid\nexists(x,y)\in
A_{2}[I]\setminus{A_{2}^{\mathrm{sure}}}[I]~{}\text{s.t.}~{}(y,x)\not\in
A_{1}[I]\,\\},$

and show that a consistent exchangeability graph can be obtained by the
$2$-SAT approach under the assumption that $J^{\prime}$ is correctly guessed.
Since the number of the candidates of $J^{\prime}$ is $2^{|J|}\leq
2^{\gamma}$, this concludes the stated computational time.

Fix $J^{\prime}\subseteq J$, and let $(X,Y)$ be an evil LE-pair. As Case 2.2
in the proof of Lemma 5.3, suppose that $X=\\{x_{1},x_{2}\\}$ and
$Y=\\{y_{1},y_{2}\\}$, and let $a_{i,j}=(x_{i},y_{j})$ and
$b_{i,j}=(y_{j},x_{i})$ for $i=1,2$ and $j=1,2$. We show that, by adding some
clauses to ${\mathcal{C}}_{X,Y}$ if necessary, we can impose the consistency
with respect to $(X,Y)$ under the assumption that $J^{\prime}$ is correctly
guessed.

Suppose that $Y\setminus J\neq\emptyset$, say $y_{1}\not\in J$. Then,
regardless of $J^{\prime}$, we do the following. If
${A_{2}^{\mathrm{min}}}[I]$ contains $a_{1,1}$ or $a_{2,1}$, then it is sure.
Thus, $(X,Y)$ cannot be underestimated under the original definition of
${\mathcal{C}}_{X,Y}$, so we need no additional clause. Otherwise, for the
consistency with respect to $(X,Y)$, instead of $a_{1,1}$ and $a_{2,1}$,
either $a_{1,2}$ or $a_{2,2}$ must be included in ${\tilde{A}}[I]$, which can
be simply represented by an additional clause $(z_{a_{1,2}}\vee z_{a_{2,2}})$.

Otherwise, $Y\subseteq J$. If $Y\subseteq J^{\prime}$, then we can conclude
that this $J^{\prime}$ is a wrong guess, since any consistent exchangeability
graph contains exactly one pair of $a_{i,j}$ and $b_{3-i,3-j}$ among the four
candidates (cf. Example 4.5), so we skip this $J^{\prime}$. If $|Y\cap
J^{\prime}|=1$, say $Y\cap J^{\prime}=\\{y_{1}\\}$, then as with the previous
paragraph, instead of $a_{1,1}$ and $a_{2,1}$ (that must be excluded in this
trial), either $a_{1,2}$ or $a_{2,2}$ must be included in ${\tilde{A}}[I]$,
which can be simply represented by an additional clause $(z_{a_{1,2}}\vee
z_{a_{2,2}})$. Otherwise, $Y\cap J^{\prime}=\emptyset$. In this case, we do
not add any clauses, and the consistency with respect to $(X,Y)$ under the
correct guess of $J^{\prime}$ is seen as follows.

Suppose that the true graph $D[I]$ contains $a_{1,1}$ and $b_{2,2}$ (without
loss of generality by the symmetry). As $J^{\prime}$ is correctly guessed,
$D[I]$ contains some arc $(x^{\prime},y_{2})\in
A_{2}[I]\setminus{A_{2}^{\mathrm{sure}}}[I]$ such that
$(y_{2},x^{\prime})\not\in A_{1}[I]$. Consider an LE-pair
$(X^{\prime},Y^{\prime})=(\\{x_{2},x^{\prime}\\},\\{y_{2}\\})$. Then, as with
the proof of Theorem 5.4, we conclude that the consistency with respect to the
subpairs of $(X^{\prime},Y^{\prime})$ implies either
$a_{2,2}\in{\tilde{A}}[I]$ or $b_{2,2}\in{\tilde{A}}[I]$. This completes the
proof. ∎

Finally, a lexicographically maximal common independent set can be found in
polynomial time by this approach, where a common independent set is
lexicographically maximal if it takes as many heaviest elements as possible,
and subject to this, it takes as many second heaviest elements as possible,
and so on.

######  Theorem 5.7.

A lexicographically maximal common independent set can be found in
$\mathrm{O}(r^{3}n^{2})$ time only using the minimum rank oracle.

###### Proof.

Let $(E_{1},E_{2},\dots,E_{\ell})$ be the partition of the ground set $E$ in
the descending order of the weights, i.e., $E_{1}$ is the set of heaviest
elements, $E_{2}$ is the set of second heaviest elements, and so on. We show
that any almost consistent exchangeability graph is sufficient (i.e.,
underestimation with respect to any evil LE-pair does not matter) to update a
lexicographically maximal common independent set
$I\in{\mathcal{I}_{\mathrm{min}}^{k}}$ to a lexicographically maximal common
independent set $I^{\prime}\in\mathcal{I}_{\mathrm{min}}^{k+1}$ such that
$|I^{\prime}\cap E_{i}|\geq|I\cap E_{i}|$ for every $i=1,2,\dots,\ell$.
Indeed, if this is true, one can obtain a lexicographically maximal common
independent set by starting with $I=\emptyset$, doing such updates in $E_{1}$
as long as possible, then doing so in $E_{1}\cup E_{2}$, and so on.

Let us consider an auxiliary weighted matroid intersection instance obtained
by replacing the weight function with $\hat{w}\colon E\to\mathbb{R}$ defined
by $\hat{w}(e)\coloneqq(n+1)^{\ell-i}$ for each $i=1,2,\dots,\ell$ and each
$e\in E_{i}$. It is easy to observe that a common independent set $I$ is
$\hat{w}$-maximal in ${\mathcal{I}_{\mathrm{min}}^{k}}$ if and only if $I$ is
lexicographically maximal in ${\mathcal{I}_{\mathrm{min}}^{k}}$. In what
follows in this proof, we just say that $I$ is maximal to mean that $I$ is
lexicographically maximal and $\hat{w}$-maximal.

Fix $k$, and let $I$ be a maximal common independent set in
${\mathcal{I}_{\mathrm{min}}^{k}}$. Suppose that $I$ can be augmented to a
maximal common independent set $I^{\prime}\in\mathcal{I}_{\mathrm{min}}^{k+1}$
such that $|I^{\prime}\cap E_{i}|\geq|I\cap E_{i}|$ for every
$i=1,2,\dots,\ell$. This occurs if and only if the minimum cost of an
$S_{I}$–$T_{I}$ path in $D[I]$ is negative, where the cost function
$\hat{c}\colon E\to\mathbb{R}$ is defined analogously with respect to
$\hat{w}$ (cf. (2.1)). Let $P$ be a shortest cheapest $S_{I}$–$T_{I}$ path in
$D[I]$. We show that this $P$ indeed exists as it is (including the order of
elements) in any almost consistent exchangeability graph ${\tilde{D}}[I]$.
Since Lemma 4.9 implies that ${\tilde{D}}[I]$ (which is an underestimation)
has no $S_{I}$–$T_{I}$ path ${\tilde{P}}$ such that either
$\hat{c}({\tilde{P}})<\hat{c}(P)$ or $\hat{c}({\tilde{P}})=\hat{c}(P)$ and
$|{\tilde{P}}|<|P|$, this completes the proof.

Suppose to the contrary that an almost consistent exchangeability graph
${\tilde{D}}[I]=(E\setminus I,I;{\tilde{A}}[I])$ does not contain $P$. For the
sake of simplicity, let $I^{\prime}\coloneqq I\triangle P$ and assume $E=I\cup
I^{\prime}$. We then have $I^{\prime}\cap E_{\ell}\neq\emptyset$, and
$|I^{\prime}\cap E_{i}|=|I\cap E_{i}|$ for every $i<\ell$ by the maximality of
$I\in{\mathcal{I}_{\mathrm{min}}^{k}}$. For each $i=1,2,\dots,\ell$, let
$L_{i}\coloneqq\\{\,e\in P\mid e\in E_{j},\ j\leq i\,\\}$. Then,
$\emptyset\neq L_{1}\subsetneq L_{2}\subsetneq\cdots\subsetneq L_{\ell}=P$ and
$|L_{i}|$ is even for every $i<\ell$. The latter can be strengthened as
follows, where a segment of $L_{i}$ is a maximal subset of $L_{i}$ whose
elements appear consecutively on the path $P$, which is also regarded as the
corresponding subpath of $P$.

######  Claim 5.8.

For any $i<\ell$, each segment of $L_{i}$ is of even cardinality.

###### Proof.

Suppose to the contrary that for some $i<\ell$, there exists an odd segment
$Z$. Take such a counterexample so that $i$ is minimum and, among those, $Z$
appears on $P$ as early as possible. We have either $|Z\cap I|=|Z\setminus
I|-1$ or $|Z\cap I|=|Z\setminus I|+1$.

In the former case, let $x\in Z\setminus I$ be the last element of $Z$, and
$y\in I$ be the successor of $x$ on $P$ (since $|L_{i}|$ is even and $Z$ is
the first odd segment of $L_{i}$, $x$ is not the last element of $P$). Let
$P^{\prime}$ be the prefix of $P$ ending at $y$, and
$I^{\prime\prime}\coloneqq I\triangle P^{\prime}$. Then, $I^{\prime\prime}$ is
a common independent set with $|I^{\prime\prime}|=|I|$ by Lemma 2.6. Also, by
the choice of $i$ and $Z$, we have $|I^{\prime\prime}\cap E_{i}|=|I\cap
E_{i}|+1$ and $|I^{\prime\prime}\cap E_{j}|=|I\cap E_{j}|$ for every $j<i$,
which contradicts the maximality of $I$.

In the latter case, let $y\in Z\cap I$ be the last element of $Z$ on $P$, and
$y^{\prime}$ be the next element in $I$ along $P$ (since $|L_{i}|$ is even,
$Z$ is the first odd segment of $L_{i}$, and the successor of $y$ on $P$ is
not in $L_{i}$, such $y^{\prime}$ indeed exists). Let $P^{\prime}$ be the
suffix of $P$ starting at $y^{\prime}$, and $I^{\prime\prime}\coloneqq
I\triangle P^{\prime}$. Then, $I^{\prime\prime}$ is a common independent set
with $|I^{\prime\prime}|=|I|$ by Lemma 2.6. Also, by the choice of $i$ and
$Z$, we have $|I^{\prime\prime}\cap E_{i}|=|I\cap E_{i}|+1$ and
$|I^{\prime\prime}\cap E_{j}|=|I\cap E_{j}|$ for every $j<i$, which
contradicts the maximality of $I$. ∎

Since ${\tilde{D}}[I]$ does not contain the path $P$, there exists an arc
$a=(x,y)\in P\setminus{\tilde{A}}[I]$. Take such an arc $a$ so that the
minimum index $i$ with $\\{x,y\\}\subseteq L_{i}$ is maximized. By symmetry,
we assume that $x\in E\setminus I$ and $y\in I$ (by interchanging
$\mathbf{M}_{1}$ and $\mathbf{M}_{2}$ if necessary). Since $a\in
A[I]\setminus{\tilde{A}}[I]$, we have $a\in{A^{\mathrm{susp}}}[I]$ and hence
$(s,y)\in A[I]$, where $s\in S_{I}$ is the first element of $P$. We then see
that there exists a special arc in the opposite direction on the prefix of
$P$.

######  Claim 5.9.

There exists an arc $b=(y^{\prime},x^{\prime})\in{\tilde{A}}[I]$ on the prefix
of $P$ ending at $x$ such that $y^{\prime}\in I$, $x^{\prime}\in E\setminus
I$, $(x^{\prime},y^{\prime})\not\in{\tilde{A}}[I]$, $x^{\prime}\in L_{j}$ and
$y^{\prime}\not\in L_{j}$ for some $j\geq i$, and the segment of $L_{j}$
starting with $x^{\prime}$ contains $x$ and $y$.

###### Proof.

Since $L_{\ell}=P$, there exists $j\geq i$ such that the segment of $L_{j}$
containing $x$ and $y$ starts with some $x^{\prime}\in E\setminus I$. Take
such an index $j$ as small as possible. We then see that $x^{\prime}\neq s$ as
follows.

Suppose to the contrary that $x^{\prime}=s$. Then, the arc $(s,y)\in A[I]$
gives a shortcut for $P$ as follows. Let $P^{\prime}$ be the $S_{I}$–$T_{I}$
path obtained from $P$ by replacing its prefix ending at $y$ with the arc
$(s,y)$. Since the segment of $L_{h}$ containing $y$ starts in $I$ for any
$i\leq h<j$ by the choice of $j$, we have $\hat{c}(P^{\prime})=\hat{c}(P)$ by
Claim 5.8, which contradicts that $P$ is a shortest cheapest $S_{I}$–$T_{I}$
path in $D[I]$.

Thus, there exists an arc $b=(y^{\prime},x^{\prime})\in A[I]$ on the prefix of
$P$ ending at $x$ such that $y^{\prime}\in I$, $x^{\prime}\in E\setminus I$,
$x^{\prime}\in L_{j}$, $y^{\prime}\not\in L_{j}$, and the segment of $L_{j}$
starting with $x^{\prime}$ contains $x$ and $y$. Since
$\hat{w}(x^{\prime})>\hat{w}(y^{\prime})$ (as $x^{\prime}\in L_{j}$ and
$y^{\prime}\not\in L_{j}$), the reverse arc $(x^{\prime},y^{\prime})$ of $b$
is not contained in $A[I]$ (otherwise, $I+x^{\prime}-y^{\prime}$ is a heavier
common independent set in ${\mathcal{I}_{\mathrm{min}}^{k}}$, which
contradicts the maximality of $I$). By the choice of $a$ (the maximality of
$i$), we have $b\in{\tilde{A}}[I]$, which completes the proof. ∎

Take an arc $b=(y^{\prime},x^{\prime})$ as in Claim 5.9 so that the index $j$
is minimized (see Figure 3). If $x^{\prime}=x$, then the consistency with
respect to the LE-pair $(\\{x\\},\\{y,y^{\prime}\\})$ implies
$a\in{\tilde{A}}[I]$ (like Example 4.4), a contradiction. Otherwise, we can
see that the LE-pair $(X,Y)=(\\{x,x^{\prime}\\},\\{y,y^{\prime}\\})$ is evil
as follows, and hence the almost consistency with respect to $(X,Y)$ implies
$a\in{\tilde{A}}[I]$, a contradiction again, which completes the proof. Since
the reverse arcs of $a=(x,y)$ and $b=(y^{\prime},x^{\prime})$ are simply
excluded from $D[I]$ by the consistency with respect to the LE-pairs
$(\\{x\\},\\{y\\})$ and $(\\{x^{\prime}\\},\\{y^{\prime}\\})$, it suffices to
show the following claim (cf. Example 4.5).

Figure 3: A shortest cheapest $S_{I}$–$T_{I}$ path $P$, an arc $a=(x,y)\in
P\setminus{\tilde{A}}[I]$, and an arc $b=(y^{\prime},x^{\prime})$ taken as in
Claim 5.9 so that the index $j$ is minimized. Here, the segment of $L_{j}$
starting with $x^{\prime}$ is enclosed by the dotted line. Other parts
enclosed by solid lines are examples of segments of $L_{h}$ with $h<j$.

######  Claim 5.10.

$A[I]$ contains none of $(x^{\prime},y)$, $(y,x^{\prime})$, $(x,y^{\prime})$,
and $(y^{\prime},x)$.

###### Proof.

Suppose to the contrary that $(x^{\prime},y)\in A[I]$. Then, let $P^{\prime}$
be the $S_{I}$–$T_{I}$ path obtained from $P$ by replacing its subpath from
$x^{\prime}$ to $y$ with the arc $(x^{\prime},y)$. By the choice of $b$ (the
minimality of $j$) and Claim 5.8, we have $\hat{c}(P^{\prime})=\hat{c}(P)$,
which contradicts that $P$ is shortest among the cheapest $S_{I}$–$T_{I}$
paths in $D[I]$.

Suppose to the contrary that $(y,x^{\prime})\in A[I]$. Since $(x,y)\in A[I]$,
the consistency with respect to the LE-pair $(\\{x,x^{\prime}\\},\\{y\\})$
(together with the fact that $(x,y)\not\in{\tilde{A}}[I]$) implies that
$(x^{\prime},y),(y,x)\in{\tilde{A}}[I]$. This contradicts the consistency with
respect to the LE-pair $(\\{x^{\prime}\\},\\{y,y^{\prime}\\})$, where
${r_{\mathrm{min}}}(I+x^{\prime}-y-y^{\prime})=|I|-2$ since $A[I]$ contains
neither $(x^{\prime},y)$ nor $(x^{\prime},y^{\prime})$.

Suppose to the contrary that $(x,y^{\prime})\in A[I]$. Then, there exists a
cycle $C$ in $D[I]$ whose vertex set coincides with the subpath of $P$ from
$y^{\prime}$ to $x$. By the choice of $b=(y^{\prime},x^{\prime})$, where
$x^{\prime}\in L_{j}$ and $y^{\prime}\not\in L_{j}$, and by Claim 5.8, we have
$\hat{c}(C)<0$, which contradicts that $I$ is maximal (cf. Lemma 2.5).

Suppose to the contrary that $(y^{\prime},x)\in A[I]$. Then, let $P^{\prime}$
be the $S_{I}$–$T_{I}$ path obtained from $P$ by replacing its subpath from
$y^{\prime}$ to $x$ with the arc $(y^{\prime},x)$. By the choice of $b$ (the
minimality of $j$ and the fact that the segment of $L_{j}$ starting with
$x^{\prime}$ contains both $x$ and $y$) and Claim 5.8, we have
$\hat{c}(P^{\prime})\leq\hat{c}(P)$, which contradicts that $P$ is a shortest
cheapest $S_{I}$–$T_{I}$ path in $D[I]$. ∎

To sum up, $(X,Y)=(\\{x,x^{\prime}\\},\\{y,y^{\prime}\\})$ is an evil LE-pair,
$a=(x,y)\not\in{\tilde{A}}[I]$, and
$b=(y^{\prime},x^{\prime})\in{\tilde{A}}[I]$. This contradicts that
${\tilde{D}}[I]$ is almost consistent, which completes the proof. ∎

By [4], a lexicographically maximal solution gives
$\min\\{1,\alpha/2\\}$-approximation of the maximum weight of a common
independent set, where $\alpha>1$ is the minimum ratio of two distinct
positive weight values. Note that when the objective is to find a maximum-
weight common independent set, we can assume the weight function is positive
by excluding any element of weight at most $0$ from the ground set in advance.

######  Corollary 5.11.

There exists an $\mathrm{O}(r^{3}n^{2})$-time
$\min\\{1,\alpha/2\\}$-approximation algorithm for finding a maximum-weight
common independent set only using the minimum rank oracle, where $\alpha>1$ is
the minimum ratio of two distinct positive weight values.

##  6 NP-hardness of Finding a Consistent Exchangeability Graph

In this section, we prove that the problem of finding a consistent
exchangeability graph is NP-hard. Recall that, by Lemma 5.3, an almost
consistent exchangeability graph can be found in polynomial time via reduction
to 2-SAT.

######  Theorem 6.1.

The following problem is NP-hard even if the two matroids $\mathbf{M}_{1}$ and
$\mathbf{M}_{2}$ are both $\mathbb{Q}$-representable: Given a common
independent set $I$, the source and sink sets $S_{I}$ and $T_{I}$, and the
values ${r_{\mathrm{min}}}((I\cup X)\setminus Y)$ for all the LE-pairs
$(X,Y)$, find a consistent exchangeability graph ${\tilde{D}}[I]$.

###### Proof.

We reduce the following problem, which is known to be NP-hard [14, 11].

4-coloring of 3-colorable graph
Input: A 3-colorable graph $G=(V,F)$. Goal: Find a 4-coloring of $G$.

We first implicitly construct two matroids $\mathbf{M}_{1}$ and
$\mathbf{M}_{2}$ on the same ground set $E$, a common independent set $I$, and
the source and sink sets $S_{I}$ and $T_{I}$ by setting the values
${r_{\mathrm{min}}}((I\cup X)\setminus Y)$ for each LE-pair $(X,Y)$ so that
there exists a natural correspondence between the consistent exchangeability
graphs and the $4$-colorings of $G$. We then give representations of
$\mathbf{M}_{1}$ and $\mathbf{M}_{2}$ over $\mathbb{Q}$ with respect to each
consistent exchangeability graph. The existence of a 3-coloring of $G$ implies
that there exists a true graph $D[I]$ that is consistent, i.e., the
constructed instance can indeed occur as the intersection of two
$\mathbb{Q}$-representable matroids. Thus, this completes the proof.

For each vertex $v\in V$, let us construct a vertex gadget consisting of four
elements $x_{1}^{v},x_{2}^{v}\in E\setminus(I\cup S_{I}\cup T_{I})$ and
$y_{1}^{v},y_{2}^{v}\in I$, which form an evil LE-pair
$(X^{v},Y^{v})=(\\{x_{1}^{v},x_{2}^{v}\\},\\{y_{1}^{v},y_{2}^{v}\\})$, as
follows. Define ${r_{\mathrm{min}}}((I\cup X^{v})\setminus
Y^{v})\coloneqq|I|-1$ and ${r_{\mathrm{min}}}((I\cup X^{\prime})\setminus
Y^{\prime})\coloneqq|I|-|Y^{\prime}|$ for any proper subpair
$(X^{\prime},Y^{\prime})$ of $(X^{v},Y^{v})$. Let
$a_{i,j}^{v}=(x_{i}^{v},y_{j}^{v})$ and $b_{i,j}^{v}=(y_{j}^{v},x_{i}^{v})$
for any $i,j\in\\{1,2\\}$. Then, the consistency with respect to the evil LE-
pair $(X^{v},Y^{v})$ imposes that a pair of arcs $a_{i,j}^{v}$ and
$b_{3-i,3-j}^{v}$ for exactly one pair $(i,j)$ of $i,j\in\\{1,2\\}$ is
included in ${\tilde{A}}[I]$ and the other three pairs are excluded (cf.
Example 4.5). These four possibilities correspond to which color is assigned
to the vertex $v$ in a $4$-coloring of $G$. For the sake of simplicity, let
$\\{(1,1),(1,2),(2,1),(2,2)\\}$ be the set of four colors, and a color $(i,j)$
assigned to $v$ is identified with the situation that
$a_{i,j}^{v},b_{3-i,3-j}^{v}\in{\tilde{A}}[I]$ in the vertex gadget (see
Figure 4).

For each edge $e=\\{u,w\\}\in F$, let us construct an edge gadget as follows.
We introduce six elements $x_{1}^{e,u},x_{1}^{e,w},x_{2}^{e,u},x_{2}^{e,w}\in
E\setminus(I\cup S_{I}\cup T_{I})$ and $y_{1}^{e},y_{2}^{e}\in I$. For each
$i\in\\{1,2\\}$, let
$(X_{i}^{e},Y_{i}^{e})=(\\{x_{i}^{e,u},x_{i}^{e,w}\\},\\{y_{i}^{e}\\})$.
Define ${r_{\mathrm{min}}}((I\cup X_{i}^{e})\setminus Y_{i}^{e})\coloneqq|I|$
and
${r_{\mathrm{min}}}(I+x_{i}^{e,u}-y_{i}^{e})\coloneqq{r_{\mathrm{min}}}(I+x_{i}^{e,w}-y_{i}^{e})\coloneqq|I|-1$.
Then, the consistency with respect to the subpairs of $(X_{i}^{e},Y_{i}^{e})$
imposes that one of $\\{(x_{i}^{e,u},y_{i}^{e}),(y_{i}^{e},x_{i}^{e,w})\\}$
and $\\{(x_{i}^{e,w},y_{i}^{e}),(y_{i}^{e},x_{i}^{e,u})\\}$ is a subset of
${\tilde{A}}[I]$ and the other is disjoint from ${\tilde{A}}[I]$ (see Figure
4).

Figure 4: The vertex gadgets for $u,w\in V$, together with the edge gadget for
$e=\\{u,w\\}\in F$. White and black vertices represent elements in
$E\setminus(I\cup S_{I}\cup T_{I})$ and in $I$, respectively. The two parts
with gray background are two evil LE-pairs $(X^{u},Y^{u})$ and $(X^{w},Y^{w})$
in the vertex gadgets, and the four parts enclosed by dotted lines are the LE-
pairs $(X_{i}^{e,v},Y_{i}^{e,v})$ $(i\in\\{1,2\\},~{}v\in\\{u,w\\})$ defined
in the edge gadget. The illustrated realization of exchangeability arcs
corresponds to assigning color $(1,1)$ to $u$ and $(1,2)$ to $w$, where we are
omitting all pairs of opposite directed arcs $(x,y)$ and $(y,x)$ that actually
exist between any pair of white and black vertices $x$ and $y$, respectively,
not included in any LE-pairs mentioned above (e.g., $x=x_{i}^{u}$ and
$y=y_{j}^{w}$ $(i,j\in\\{1,2\\})$, $x=x_{1}^{e,v}$ and $y=y_{2}^{v^{\prime}}$
$(v,v^{\prime}\in\\{u,w\\})$, or $x=x_{2}^{v}$ and $y=y_{i}^{e}$
$(v\in\\{u,w\\},~{}i\in\\{1,2\\})$).

In addition, let

$\displaystyle(X_{1}^{e,u},Y_{1}^{e,u})=(\\{x_{1}^{e,u},x_{1}^{u}\\},\,\\{y_{1}^{e},y_{1}^{u}\\}),\quad(X_{1}^{e,w},Y_{1}^{e,w})=(\\{x_{1}^{e,w},x_{1}^{w}\\},\,\\{y_{1}^{e},y_{1}^{w}\\}),$
$\displaystyle(X_{2}^{e,u},Y_{2}^{e,u})=(\\{x_{2}^{e,u},x_{1}^{u}\\},\,\\{y_{2}^{e},y_{2}^{u}\\}),\quad(X_{2}^{e,w},Y_{2}^{e,w})=(\\{x_{2}^{e,w},x_{1}^{w}\\},\,\\{y_{2}^{e},y_{2}^{w}\\}),$

and define ${r_{\mathrm{min}}}((I\cup X^{\prime})\setminus
Y^{\prime})\coloneqq|I|-|Y^{\prime}|$ for each subpair
$(X^{\prime},Y^{\prime})$ of $(X_{i}^{e,v},Y_{i}^{e,v})$ $(i\in\\{1,2\\},\
v\in\\{u,w\\})$. Then, the consistency with respect to the subpairs of
$(X_{i}^{e,v},Y_{i}^{e,v})$ imposes that $u$ and $w$ are assigned different
colors (see Figure 4). Suppose to the contrary that, for example, $u$ and $w$
are assigned the same color $(1,1)$, i.e.,
$a_{1,1}^{u}=(x_{1}^{u},y_{1}^{u})\in{\tilde{A}}[I]$ and
$a_{1,1}^{w}=(x_{1}^{w},y_{1}^{w})\in{\tilde{A}}[I]$. Then, the consistency
with respect to $(X_{1}^{e,u},Y_{1}^{e,u})$ imposes that
$(y_{1}^{e},x_{1}^{e,u})$ is excluded from ${\tilde{A}}[I]$, and the
consistency with respect to $(X_{1}^{e,w},Y_{1}^{e,w})$ imposes that
$(y_{1}^{e},x_{1}^{e,w})$ is excluded from ${\tilde{A}}[I]$ as well. This,
however, contradicts the consistency with respect to $(X_{1}^{e},Y_{1}^{e})$,
which imposes that either
$\\{(x_{1}^{e,u},y_{1}^{e}),(y_{1}^{e},x_{1}^{e,w})\\}$ or
$\\{(x_{1}^{e,w},y_{1}^{e}),(y_{1}^{e},x_{1}^{e,u})\\}$ must be included in
${\tilde{A}}[I]$. The collision of the color $(2,2)$ is forbidden in almost
the same way, and the collision of $(1,2)$ or $(2,1)$ is similarly forbidden
by the consistency with respect to $(X_{2}^{e,u},Y_{2}^{e,u})$,
$(X_{2}^{e,w},Y_{2}^{e,w})$, and $(X_{2}^{e},Y_{2}^{e})$. Thus, this edge
gadget represents that $u$ and $w$ are assigned different colors.

As the last step of the construction, we put two special elements $s,t\in
E\setminus I$ as a unique source in $S_{I}$ and a unique sink in $T_{I}$,
respectively; i.e., ${r_{\mathrm{min}}}(I+s)={r_{\mathrm{min}}}(I+t)=|I|$ and
${r_{\mathrm{min}}}(I+s+t)=|I|+1$. For each pair of $x\in E\setminus(I\cup
S_{I}\cup T_{I})$ and $y\in I$, we define

${r_{\mathrm{min}}}(I+s-y)\coloneqq{r_{\mathrm{min}}}(I+t-y)\coloneqq{r_{\mathrm{min}}}(I+s+x-y)\coloneqq{r_{\mathrm{min}}}(I+t+x-y)\coloneqq|I|,$

which means that $C_{2}(I,s)=I+s$ and $C_{1}(I,t)=I+t$. Also, for each LE-pair
$(X,Y)$ that we have not yet defined the value ${r_{\mathrm{min}}}((I\cup
X)\setminus Y)$, we define it as follows.

  * •

If $|X|=1$ or $|Y|=1$, then ${r_{\mathrm{min}}}((I\cup X)\setminus
Y)\coloneqq|I|-|Y|+1$.

  * •

If $|X|=|Y|=2$, then

    * –

${r_{\mathrm{min}}}((I\cup X)\setminus Y)\coloneqq|I|-1$ if there exists a
proper subpair $(X^{\prime},Y^{\prime})$ of $(X,Y)$ such that
$|X^{\prime}|+|Y^{\prime}|=3$ and ${r_{\mathrm{min}}}((I\cup
X^{\prime})\setminus Y^{\prime})=|I|-|Y^{\prime}|$ (such
$(X^{\prime},Y^{\prime})$ is a proper subpair of either $(X^{v},Y^{v})$ for
some $v\in V$ or $(X_{i}^{e,v},Y_{i}^{e,v})$ for some $i\in\\{1,2\\}$ and some
$v\in e\in E$), and

    * –

${r_{\mathrm{min}}}((I\cup X)\setminus Y)\coloneqq|I|$ otherwise (in this
case, $X\cup Y$ has a cycle of length $4$ or can be partitioned into two
disjoint cycles of length $2$).

We then see that

  * •

all the pairs $(u,v)$ with either $u\in E\setminus(I\cup S_{I}\cup T_{I})$ and
$v\in I$ or $u\in I$ and $v\in E\setminus(I\cup S_{I}\cup T_{I})$ are
suspicious arcs (recall Lemma 4.1 and the definition of suspicious arcs), and

  * •

every LE-pair $(X,Y)$ not designated in the construction of the vertex and
edge gadgets contains a pair of $x\in X$ and $y\in Y$ exchangeable in both
matroids, which can be determined from ${r_{\mathrm{min}}}(I+x-y)=|I|$, and
then induces no more correlation between two suspicious arcs in the gadgets
(recall Definition 4.3).

Thus, we essentially have uncertainty only in the vertex gadgets and the edge
gadgets, which are constrained so that each vertex gadget has four possible
situations corresponding to the four colors, and that two vertex gadgets
adjacent by an edge gadget are in different situations corresponding to the
validity of $4$-coloring. This gives a one-to-one correspondence between the
situations of the vertex gadgets in the consistent exchangeability graphs and
the $4$-colorings of $G$. Note that there may be multiple possible situations
of each edge gadget for the same situations of the vertex gadgets (e.g., for
an edge $e=\\{u,w\\}\in F$, if $u$ and $w$ are assigned color $(1,1)$ and
$(2,2)$, then either of
$\\{(x_{2}^{e,u},y_{2}^{e}),(y_{2}^{e},x_{2}^{e,w})\\}$ and
$\\{(x_{2}^{e,w},y_{2}^{e}),(y_{2}^{e},x_{2}^{e,u})\\}$ can be included in
${\tilde{A}}[I]$).

Finally, we give representations of $\mathbf{M}_{1}$ and $\mathbf{M}_{2}$ over
$\mathbb{Q}$ with respect to each consistent exchangeability graph, which
indeed satisfy the minimum rank values defined above. Fix a consistent
exchangeability graph ${\tilde{D}}[I]=(E\setminus I,I;{\tilde{A}}[I])$. We
construct the representation matrices $Z_{1}$ and $Z_{2}$ of $\mathbf{M}_{1}$
and $\mathbf{M}_{2}$, respectively, as follows. For each $i=1,2$, the row and
column sets of $Z_{i}$ correspond to $I\cup\\{s,t\\}$ and $E$, respectively.
We denote the $(y,x)$ entry of $Z_{i}$ by $Z_{i}[y,x]$, and the $(Y,X)$
submatrix of $Z_{i}$ by $Z_{i}[Y,X]$. As usual, each subset $X\subseteq E$
corresponds to the submatrix $Z_{i}[I\cup\\{s,t\\},X]$ in the sense that
$r_{i}(X)=\mathrm{rank}(Z_{i}[I\cup\\{s,t\\},X])$.

We start with defining $Z_{i}[I,I]$ as the identity matrix with $Z_{i}[y,y]=1$
$(\forall y\in I)$ and $Z_{i}[s,y]\coloneqq Z_{i}[t,y]\coloneqq 0$ for each
$y\in I$. We then define $Z_{1}[s,s]\coloneqq Z_{2}[t,t]\coloneqq 1$ and the
other entries of $Z_{i}[\\{s,t\\},\\{s,t\\}]$ as $0$. Also,
$Z_{1}[y,t]\coloneqq Z_{2}[y,s]\coloneqq 1$ and $Z_{1}[y,s]\coloneqq
Z_{2}[y,t]\coloneqq 0$ for each $y\in I$ (recall that $C_{2}(I,s)=I+s$ and
$C_{1}(I,t)=I+t$). For the remaining entries, we fix mutually distinct prime
numbers $p_{x,y}\in\mathbb{Q}$ for the pairs of $x\in E\setminus I$ and $y\in
I$, and define $Z_{i}[y,x]$ as either $p_{x,y}$ or $0$ as follows, so that any
$2\times 2$ submatrix of $Z_{i}$ having nonzero values at both diagonal
entries or both nondiagonal entries always becomes nonsingular:

$Z_{1}[y,x]\coloneqq\begin{cases}p_{x,y}&\text{if
$(y,x)\in{\tilde{A}}_{1}[I]$},\\\ 0&\text{otherwise},\end{cases}\qquad
Z_{2}[y,x]\coloneqq\begin{cases}p_{x,y}&\text{if
$(x,y)\in{\tilde{A}}_{2}[I]$},\\\ 0&\text{otherwise}.\end{cases}$

Then, it is not difficult to check that the constructed matrices indeed result
in two matroids satisfying the minimum rank values defined above, which
completes the proof. ∎

######  Remark 6.2.

The above reduction does not work for binary matroids, because the
simultaneous exchangeability (the nonsingularity of $2\times 2$ submatrices of
$Z_{i}$) is sometimes broken, thus providing additional information. The
tractability of finding a consistent exchangeability graph for special classes
of matroids (e.g., regular, binary, and $\mathbb{F}$-representable for some
finite field $\mathbb{F}$) is an interesting open problem. By Lemma 4.10, an
algorithm for finding consistent exchangeability graphs for a class would
immediately lead to the tractability of weighted matroid intersection in that
class under the minimum rank oracle.

######  Remark 6.3.

In the proof of Theorem 6.1, we only claim that all the consistent
exchangeability graphs obtained in the way described there cannot be
distinguished by the minimum rank values ${r_{\mathrm{min}}}((I\cup
X)\setminus Y)$ for the LE-pairs $(X,Y)$. The result might be strengthened by
showing that the same holds even if we observe ${r_{\mathrm{min}}}(Z)$ for all
the subsets $Z\subseteq E$. Such a strengthening would indicate the limitation
of any approach that relies on consistent exchangeability graphs.

##### Acknowledgements.

We are grateful to Yuni Iwamasa and Taihei Oki for the initial discussion on
the problem, and to Ryuhei Mizutani for a discussion on the relation to
$1/3$\- and $2/3$-submodular functions.

Yutaro Yamaguchi was supported by JSPS KAKENHI Grant Numbers 20K19743 and
20H00605, by Overseas Research Program in Graduate School of Information
Science and Technology, Osaka University, and by the Osaka University Research
Abroad Program. Yu Yokoi was supported JST PRESTO Grant Number JPMJPR212B and
JST ERATO Grant Number JPMJER2301. The research was supported by the Lendület
Programme of the Hungarian Academy of Sciences – grant number LP2021-1/2021,
by the Ministry of Innovation and Technology of Hungary – grant number ELTE
TKP 2021-NKTA-62, and by Dynasnet European Research Council Synergy project –
grant number ERC-2018-SYG 810115.

## References

  * [1] B. Aspvall, M. F. Plass, and R. E. Tarjan.  A linear-time algorithm for testing the truth of certain quantified boolean formulas.  Information Processing Letters, 8(3):121–123, 1979.
  * [2] M. Bárász.  Matroid intersection for the min-rank oracle.  Technical Report QP-2006-03, Egerváry Research Group, Budapest, 2006\.  www.cs.elte.hu/egres.
  * [3] K. Bérczi and A. Frank.  Variations for lovász’submodular ideas.  Building Bridges: Between Mathematics and Computer Science, pages 137–164, 2008.
  * [4] K. Bérczi, T. Király, Y. Yamaguchi, and Y. Yokoi.  Approximation by lexicographically maximal solutions in matching and matroid intersection problems.  Theoretical Computer Science, 910:48–53, 2022.
  * [5] K. Bérczi, T. Király, Y. Yamaguchi, and Y. Yokoi.  Matroid intersection under restricted oracles.  SIAM Journal on Discrete Mathematics, 37(2):1311–1330, 2023.
  * [6] R. A. Brualdi.  Comments on bases in dependence structures.  Bulletin of the Australian Mathematical Society, 1(2):161–167, 1969\.
  * [7] 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.).
  * [8] A. Frank.  A weighted matroid intersection algorithm.  Journal of Algorithms, 2(4):328–336, 1981.
  * [9] A. Frank.  Connections in Combinatorial Optimization, volume 38.  Oxford University Press, 2011.
  * [10] M. Grötschel, L. Lovász, and A. Schrijver.  Geometric Algorithms and Combinatorial Optimization.  Springer, 1988.
  * [11] V. Guruswami and S. Khanna.  On the hardness of 4-coloring a 3-colorable graph.  SIAM Journal on Discrete Mathematics, 18(1):30–40, 2004.
  * [12] P. Hall.  On representatives of subsets.  Journal of the London Mathematical Society, 1(1):26–30, 1935.
  * [13] S. Iwata, L. Fleischer, and S. Fujishige.  A combinatorial strongly polynomial algorithm for minimizing submodular functions.  Journal of the ACM, 48(4):761–777, 2001.
  * [14] S. Khanna, N. Linial, and S. Safra.  On the hardness of approximating the chromatic number.  Combinatorica, 20(3):393–415, 2000.
  * [15] 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.
  * [16] 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\.
  * [17] S. Krogdahl.  The dependence graph for bases in matroids.  Discrete Mathematics, 19(1):47–59, 1977.
  * [18] M. R. Krom.  The decision problem for a class of first-order formulas in which all disjunctions are binary.  Mathematical Logic Quarterly, 13(1-2):15–20, 1967.
  * [19] S. T. McCormick.  Submodular function minimization.  Handbooks in Operations Research and Management Science, 12:321–391, 2005.
  * [20] R. Mizutani and Y. Yoshida.  Polynomial algorithms to minimize $2/3$-submodular functions.  In International Conference on Integer Programming and Combinatorial Optimization, pages 323–336. Springer, 2024.
  * [21] J. Oxley.  Matroid Theory.  Oxford University Press, 2011.
  * [22] A. Schrijver.  A combinatorial algorithm minimizing submodular functions in strongly polynomial time.  Journal of Combinatorial Theory, Series B, 80(2):346–355, 2000\.
  * [23] A. Schrijver.  Combinatorial Optimization: Polyhedra and Efficiency.  Springer, 2003.