# Problems on Group-labeled Matroid Bases

Florian Hörsch CISPA, Saarbrücken, Germany. E-mail<EMAIL_ADDRESS>András Imolay MTA-ELTE Momentum Matroid Optimization Research Group,
Department of Operations Research, ELTE Eötvös Loránd University, Budapest,
Hungary. E-mail: {andras.imolay<EMAIL_ADDRESS>Ryuhei Mizutani
Department of Mathematical Informatics, Graduate School of Information Science
and Technology, The University of Tokyo, Tokyo, Japan. E-mail:
{ryuhei_mizutani<EMAIL_ADDRESS>Taihei Oki33footnotemark: 3 Tamás
Schwarcz22footnotemark: 2

###### Abstract

Consider a matroid equipped with a labeling of its ground set to an abelian
group. We define the label of a subset of the ground set as the sum of the
labels of its elements. We study a collection of problems on finding bases and
common bases of matroids with restrictions on their labels. For zero bases and
zero common bases, the results are mostly negative. While finding a non-zero
basis of a matroid is not difficult, it turns out that the complexity of
finding a non-zero common basis depends on the group. Namely, we show that the
problem is hard for a fixed group if it contains an element of order two,
otherwise it is polynomially solvable.

As a generalization of both zero and non-zero constraints, we further study
$F$-avoiding constraints where we seek a basis or common basis whose label is
not in a given set $F$ of forbidden labels. Using algebraic techniques, we
give a randomized algorithm for finding an $F$-avoiding common basis of two
matroids represented over the same field for finite groups given as operation
tables. The study of $F$-avoiding bases with groups given as oracles leads to
a conjecture stating that whenever an $F$-avoiding basis exists, an
$F$-avoiding basis can be obtained from an arbitrary basis by exchanging at
most $|F|$ elements. We prove the conjecture for the special cases when
$|F|\leq 2$ or the group is ordered. By relying on structural observations on
matroids representable over fixed, finite fields, we verify a relaxed version
of the conjecture for these matroids. As a consequence, we obtain a
polynomial-time algorithm in these special cases for finding an $F$-avoiding
basis when $|F|$ is fixed.

Keywords: matroids, matroid intersection, congruency constraint, exact-weight
constraint, additive combinatorics, algebraic algorithm, strongly base
orderability

##  1 Introduction

Several combinatorial optimization problems involve additional constraints,
such as parity, congruency, and exact-weight constraints [46, 55, 56, 57, 60].
These constraints are subsumed by _group-label constraints_ defined as
follows: the ground set $E$ is equipped with a labeling $\psi\colon
E\to\Gamma$ to an abelian group $\Gamma$ and a solution $X\subseteq E$ must
ensure that the sum of the labels of its entries is not in a prescribed
forbidden set $F\subseteq\Gamma$, i.e., $\psi(X)\coloneqq\sum_{e\in
X}\psi(e)\notin F$. We call such a solution _$F$ -avoiding_.

Particularly important special cases of group-label constraints include the
_non-zero_ ($F=\\{0\\}$) and _zero_ ($F=\Gamma\setminus\\{0\\}$) constraints,
where $F$-avoiding sets are referred to as _non-zero_ and _zero_ ,
respectively. The non-zero constraint has been extensively studied for path
problems on graphs as it generalizes constraints on parity and topology. This
line of research includes packing non-zero $A$-paths [14] as well as finding a
shortest odd $s$–$t$ path [62, Section 29.11e], a shortest non-zero $s$–$t$
path [32], and an $F$-avoiding $s$–$t$ path with $|F|\leq 2$ [38]. For these
problems, some literature allows $\Gamma$ to be non-abelian since the order of
operations can be naturally defined for paths. Problems related to non-zero
perfect bipartite matchings in $\mathbb{Z}_{2}$ have also been dealt with, see
[1, 22, 34]. The zero constraint, or, slightly more generally, the group-label
constraint with $|\Gamma\setminus F|=1$, can encode the congruency and exact-
weight constraints by setting $\Gamma$ to be a cyclic group $\mathbb{Z}_{m}$
and the integers $\mathbb{Z}$, respectively. Examples of congruency-
constrained problems include submodular function minimization [56], minimum
cut [57], and integer linear programming with totally unimodular coefficients
[55]. For the last problem, Nägele, Santiago, and Zenklusen [55] gave a
randomized strongly polynomial-time algorithm to test the existence of an
$F$-avoiding feasible solution, where the group is $\mathbb{Z}_{m}$ with prime
$m$ and $|F|\leq 2$, implying the congruency constraint if $m=3$. The exact-
weight constraint was first considered for the matching problem by
Papadimitriou and Yannakakis [60]. Mulmuley, Vazirani, and Vazirani [54] gave
a randomized polynomial-time algorithm for solving the problem using an
algebraic technique. Derandomizing this algorithm is a major open problem and
there is a collection of partial results for it, see e.g. [6, 22, 28, 65, 70].
Other exact problems include arborescences, matchings, cycles [3], and
independent sets or bases in a matroid [13, 19, 61].

In this work, we explore group-label constraints for matroid bases and matroid
intersection. Throughout the paper, we assume that any group $\Gamma$ is
abelian without mentioning it. In the problems Non-Zero Basis and Zero Basis,
we are given a matroid $M$ on a ground set $E$ and a group labeling
$\psi\colon E\to\Gamma$, and we are to find a non-zero or zero basis,
respectively, or to correctly report that no such basis exists. In
$F$-avoiding Basis along with the matroid $M$ and labeling $\psi$, we are also
given a forbidden label set $F\subseteq\Gamma$, and we need to find an
$F$-avoiding basis, that is a basis $B$ with $\psi(B)\not\in F$. In Non-Zero
Common Basis, Zero Common Basis, and $F$-avoiding Common Basis, instead of a
single matroid, we are given two matroids $M_{1}$ and $M_{2}$ on a common
ground set $E$ and seek a non-zero, zero, and $F$-avoiding common basis,
respectively. We also tackle the weighted variants of these problems, referred
to as Weighted Non-Zero Basis for example, where we are to find a feasible
solution minimizing a given weight function $w\colon E\to\mathbb{R}$.

We note that the target label $0$ in the non-zero and zero problems can be
changed to an arbitrary group element $g\in\Gamma$ by appending a coloop to
the ground set with label $-g$. Regarding the input of the group, we consider
the following three types: (i) operation and zero-test oracle, (ii) operation
table of a finite group, and (iii) a fixed finite group. Unless otherwise
stated, we assume that a group is given as the oracles and the matroids are
given as independence oracles. In this case, by a polynomial-time algorithm,
we mean an algorithm making polynomially many elementary steps, group
operations, and independence oracle calls. If the group is finite and is given
by its operation table, then the running time of a polynomial-time algorithm
can depend polynomially on the group size.

Our research follows the recent initiative by Liu and Xu [46], who addressed
Zero Basis111Called _Group-Constrained Matroid Base_ (GCMB) in [46].. They
conjectured that, given the existence of a zero basis, for any non-zero basis
$B$, there is a zero basis $B^{*}$ such that $|B^{*}\setminus B|\leq
D(\Gamma)-1$, where $D(\Gamma)$ denotes the Davenport constant of $\Gamma$
(see Section 6.3 for definition) and is upper-bounded by $|\Gamma|$. Liu and
Xu proved the conjecture for cyclic groups $\Gamma=\mathbb{Z}_{m}$ with the
order $m$ being prime power or the product of two primes, with the aid of an
additive combinatorics result by Schrijver and Seymour [63], deriving an FPT
algorithm parameterized by $|\Gamma|=m$ for Zero Basis. In Theorem 6.14, we
give a counterexample to this conjecture.

The non-zero constraint is closely related to _lattices_ studied by Lovász
[49]. The _lattice_ generated by vectors
$\\{v_{1},\dotsc,v_{n}\\}\subseteq\mathbb{R}^{n}$ is the set
$\\{\,\sum_{i=1}^{n}\lambda_{i}v_{i}\mathclose{}\nonscript\;|\nonscript\;\mathopen{}\lambda_{1},\dotsc,\lambda_{n}\in\mathbb{Z}\,\\}$.
For a set family $\mathcal{F}\subseteq 2^{E}$, let
$\operatorname{lat}(\mathcal{F})$ denote the lattice generated by the
characteristic vectors of $\mathcal{F}$. Every lattice has a _lattice basis_
$A=\\{a_{1},\dotsc,a_{n}\\}\subseteq\mathbb{Z}^{E}$, which is a set of
linearly independent vectors generating it. Since $\mathcal{F}$ and its
lattice basis $A$ generate the same lattice, $\mathcal{X}$ has a non-zero
member if and only if $A$ has a non-zero member, i.e.,
$\psi(a_{i})\coloneqq\sum_{e\in E}a_{i}(e)\psi(e)\neq 0$ for some $i$. This
implies that if a basis of $\operatorname{lat}(\mathcal{F})$ can be computed
in polynomial time, then the existence of a non-zero member of $\mathcal{F}$
can be decided in polynomial time. Such set families $\mathcal{F}$ include
matroid bases [61], common bases of a matroid and a partition matroid having
two classes [61], and perfect matchings [49, 50].

We below summarize existing and our results for each problem.

Non-Zero Basis

The tractability of Non-Zero Basis can be derived from the above lattice
argument together with a characterization of base lattices [61]. We observe
that for any zero basis $B$, there exists a non-zero basis $B^{*}$ such that
$|B^{*}\setminus B|\leq 1$, provided that at least one non-zero basis exists.
A weighted variant of this statement is shown in the same way. This result
generalizes an algorithm for Weighted Zero Basis with $\Gamma=\mathbb{Z}_{2}$
by Liu and Xu [46].

Non-Zero Common Basis

We show in Theorems 6.1 and 3.9 that Non-Zero Common Basis is polynomially
solvable if and only if $\Gamma$ does not contain $\mathbb{Z}_{2}$ as a
subgroup. Our hardness proof for $\Gamma=\mathbb{Z}_{2}$ is based on an
information-theoretic argument using sparse paving matroids, which is
independent of the $\textsf{{P}}\neq\textsf{{NP}}$ conjecture. The polynomial-
time algorithm for $\Gamma\not\geq\mathbb{Z}_{2}$ is a modification of the
negatively directed cycle elimination algorithm for weighted matroid
intersection [9]. In Theorem 3.11, we also give a 2-approximation algorithm
for Weighted Non-Zero Common Basis if $\Gamma\not\geq\mathbb{Z}_{2}$ and the
weight function is nonnegative. Finally, in Theorems 3.15 and 3.17, we solve
Weighted Non-Zero Common Basis for an arbitrary group when both matroids are
partition matroids or one of the matroids is a partition matroid defined by a
partition having two classes.

$F$-avoiding Basis and Common Basis

If the group is fixed and finite, (Weighted) $F$-avoiding Basis reduces to
polynomially many instances of (weighted) matroid intersection [46]. On the
other hand, it follows from the results of [19] that $F$-avoiding Basis
requires exponentially many independence oracle queries if $F$ is part of the
input and the group is finite and is given as an operation table, while the
same hardness of $F$-avoiding Common Basis follows from our Theorem 6.1 even
if the group is fixed and finite. Regarding positive results for $F$-avoiding
problems, our contribution is twofold. First, using similar ideas as in [13,
69], in Theorem 4.3 we give a randomized algebraic algorithm for $F$-avoiding
Common Basis in case where the matroids are represented over the same field
and the group is finite and is given as an operation table. We observe in
Theorem 4.4 that the algorithm can be derandomized in certain cases, including
$F$-avoiding Basis for graphic matroids. Second, we turn to the study of
$F$-avoiding Basis for cases where $|F|$ is fixed and the group is given by an
oracle. Motivated by the work of Liu and Xu [46], we propose 5.1 stating that
if at least one $F$-avoiding basis exists, then each basis can be turned into
an $F$-avoiding basis by exchanging at most $|F|$ elements. The validity of
the conjecture follows from the results of [46] for groups of prime order. We
show that the conjecture also holds if $\Gamma$ is an ordered group (Theorem
5.6) or if $|F|\leq 2$ (Theorem 5.40). By introducing a novel relaxation of
strong base orderability, in Theorem 5.17 we show that a relaxation of the
conjecture holds for $\mathrm{GF}(q)$-representable matroids for a fixed prime
power $q$. In Theorem 5.27, we prove a somewhat stronger version of this
result for graphic matroids. In each of these special cases, we obtain the
polynomial solvability of $F$-avoiding Basis for fixed $F$.

Zero Basis and Zero Common Basis

The zero constraint for $\Gamma=\mathbb{Z}$ corresponds to the exact-weight
constraint, implying that many problems are NP-hard, in particular, Zero Basis
is NP-hard even for uniform matroids (Theorem 6.6). It follows from the
results of [19] that Zero Basis requires exponentially many independence
oracle queries for a finite group given by operation table. We show the same
hardness of Zero Basis for any fixed infinite group (Theorem 6.11), and of
Zero Common Basis for any fixed nontrivial group (Theorem 6.12). On the other
hand, we obtain positive results from the aforementioned results on
$F$-avoiding problems. In particular, Zero Basis is polynomially solvable if
the group is fixed and finite [46], Theorem 4.3 implies a randomized
polynomial-time algorithm for Zero Common Basis for matroids represented over
the same field if $\Gamma$ is finite and is given as an operation table, and
using the results of [46], Theorem 5.17 implies an FPT algorithm for Zero
Basis when parameterized by $|\Gamma|$ if the matroids are representable over
a fixed, finite field (Corollary 5.24).

##### Other work related to group-labeled matroids

Bérczi and Schwarcz [12] showed hardness of partitioning into common bases,
see also [11, 31] for later results. A natural relaxation of that problem
gives rise to problems related to Non-Zero Common Basis for the group
$\mathbb{R}/\mathbb{Z}$. This relation is explained in Section 6.1.

It is straightforward to verify that the family of non-zero subsets of a set
satisfies the axiom of _delta-matroids_ , which are a generalization of
matroids introduced by Bouchet [8]. From this viewpoint, Non-Zero Basis offers
a tractable special case of the intersection of a matroid and a delta-matroid.
We note that the intersection of a matroid and a delta-matroid is intractable
in general, as it encompasses matroid parity [33, 48]. Kim, Lee, and Oum [39]
defined a delta-matroid, called a _$\Gamma$ -graphic delta-matroid_, from a
graph equipped with a labeling of vertices to an abelian group $\Gamma$. In
the definition, they employ a constraint similar to but different from non-
zero. Exploring the relationship between $\Gamma$-graphic delta-matroids and
our findings is left for future work.

##### Organization

The rest of this paper is organized as follows. Section 2 provides
preliminaries on groups and matroids. Section 3 deals with non-zero problems.
Section 4 provides an algebraic algorithm for $F$-avoiding Common Basis for
represented matroids. Section 5 studies $F$-avoiding Basis if $|F|$ is fixed.
Section 6 includes our hardness results for each of the problems. Finally,
Section 7 concludes this paper enumerating open problems.

##  2 Preliminaries

Let $\mathbb{N}$, $\mathbb{Z}_{\geq 0}$, $\mathbb{Z}$, $\mathbb{Q}$,
$\mathbb{R}_{\geq 0}$, and $\mathbb{R}$ denote the set of positive integers,
nonnegative integers, integers, rationals, nonnegative reals, and reals,
respectively. We let $[n]\coloneqq\\{1,\dotsc,n\\}$ for $n\in\mathbb{Z}_{\geq
0}$. For a set $S$, we simply write $S\setminus\\{x\\}$ as $S-x$ for $x\in S$
and $S\cup\\{y\\}$ as $S+y$ for $y\notin S$. For a set $E$ and
$r\in\mathbb{Z}_{\geq 0}$, we let $\binom{E}{r}\coloneqq\\{\,S\subseteq
E\mathclose{}\nonscript\;|\nonscript\;\mathopen{}|S|=r\,\\}$.

In this paper, all groups are implicitly assumed to be abelian. We use the
additive notation for the operations of groups except in Section 4. For
$m\in\mathbb{N}$, let $\mathbb{Z}_{m}=\\{0,\dotsc,m-1\\}$ denote the cyclic
group of order $m$. For groups $\Gamma_{1}$ and $\Gamma_{2}$, we mean by
$\Gamma_{1}\leq\Gamma_{2}$ that $\Gamma_{1}$ is a subgroup of $\Gamma_{2}$. A
group $\Gamma$ is said to be _ordered_ if $\Gamma$ is equipped with a total
order $\leq$ compatible with the operation of $\Gamma$ in the sense that
$a\leq b$ implies $a+c\leq b+c$ for all $a,b,c\in\Gamma$. A _labeling_ is a
function $\psi\colon E\to\Gamma$ from a set $E$ to a group $\Gamma$, and we
let $\psi(S)\coloneqq\sum_{x\in S}\psi(x)$ for $S\subseteq E$. Let
$\mathrm{GF}(q)$ denote the finite field of $q$ elements for a prime power
$q$.

We follow [17] for basic terminologies on graphs such as paths and cycles. The
vertex and edge sets of a graph $G$ are denoted by $V(G)$ and $E(G)$,
respectively. Similarly, $V(D)$ denotes the vertex set of a directed graph $D$
and $A(D)$ denotes its arc set. Given a weight function $w\colon
A(D)\to\mathbb{R}$ and a subgraph $C$ of $D$, the _weight_ of $C$ is defined
as $w(C)\coloneqq w(A(C))$. A weight function $w$ is said to be _conservative_
if $D$ does not contain a directed cycle of negative weight.

We refer the reader to [24, 62] for basics on matroid optimization. A
_matroid_ $M$ consists of a finite ground set $E(M)$ and a nonempty set family
$\mathcal{B}(M)\subseteq 2^{E(M)}$ such that for any
$B_{1},B_{2}\in\mathcal{B}(M)$ and $x\in B_{1}\setminus B_{2}$, there exists
$y\in B_{2}\setminus B_{1}$ such that $B_{1}-x+y\in\mathcal{B}(M)$. Elements
in $\mathcal{B}(M)$ are called _bases_. The next basis exchange property was
proved by Brualdi [10], see also [62, Theorem 39.12].

######  Lemma 2.1 (Brualdi [10]).

If $B$ and $B^{\prime}$ are bases of a matroid $M$, then there exists a
bijection $\phi\colon B\setminus B^{\prime}\to B^{\prime}\setminus B$ such
that $B-e+\phi(e)$ is a basis for each $e\in B\setminus B^{\prime}$.

Following [24], we define a _partition matroid_ as a direct sum of uniform
matroids, and a _unitary partition matroid_ as a direct sum of rank-1 uniform
matroids. We note that several authors refer to the latter object as partition
matroids. Given a matrix $A$ over some field, we denote by $M(A)$ the matroid
defined on the column indices of $A$ where a set is a basis of $M(A)$ if the
corresponding columns form a basis of the vector space spanned by the columns
of $A$. Given a connected graph $G$, its _cycle matroid_ $M(G)$ is the matroid
whose ground set is $E(G)$ and whose bases are the spanning trees of $G$. If
$M=M(A)$ for a matrix $A$ over a field $\mathbb{F}$ or a graph $A$, we say
that $M$ is _$\mathbb{F}$ -representable_ or _graphic_ , respectively.

##  3 Non-zero Basis and Common Basis

This section deals with the problem of finding non-zero bases and non-zero
common bases. In Section 3.1, we give some rather simple algorithmic results
on Non-Zero Basis. In Section 3.2, we give a collection of results on the more
complex algorithmic landscape of Non-Zero Common Basis.

###  3.1 Non-zero Basis

In this section, we consider (Weighted) Non-Zero Basis. The following theorem
can be derived from the description of the lattices of matroid bases by Rieder
[61]. In what follows we give a direct proof of the result.

######  Theorem 3.1.

Let $M$ be a matroid and $\psi\colon E(M)\to\Gamma$ a group labeling. The
following are equivalent:

  1. (i)

all bases of $M$ have the same label,

  2. (ii)

$M$ has a basis $B$ such that $\psi(B^{\prime})=\psi(B)$ holds for each basis
$B^{\prime}$ with $|B\setminus B^{\prime}|\leq 1$, and

  3. (iii)

$\psi$ is constant on each component of $M$.

###### Proof.

It is clear that (i) implies (ii) and (iii) implies (i). In what follows we
show that (ii) implies (iii). Let $B$ be a basis such that
$\psi(B^{\prime})=\psi(B)$ holds for each basis $B^{\prime}$ with $|B\setminus
B^{\prime}|\leq 1$. Let $G_{B}$ denote the bipartite graph with bipartition
$(B,E(M)\setminus B)$ and edge set
$\\{\,xy\mathclose{}\nonscript\;|\nonscript\;\mathopen{}x\in B,y\in
E(M)\setminus B,B-x+y\in\mathcal{B}(M)\,\\}$. By the assumption on $B$, it
follows that $\psi(x)=\psi(y)$ for each edge $xy$ of $G_{B}$. Then, $\psi$ is
constant on each connected component of the graph $G_{B}$, and thus (iii)
follows by using that the connected components of the graph $G_{B}$ coincide
with the components of the matroid $M$ [44]. ∎

Note that Theorem 3.1(iii) provides a characterization for “NO” instances of
Non-Zero Basis, while Theorem 3.1(ii) provides a simple algorithm for this
problem. Liu and Xu [46] gave the following extension of this algorithm for
Weighted Zero Basis with $\Gamma=\mathbb{Z}_{2}$, for which the zero and non-
zero constraints are equivalent. First, find a minimum weight basis
$B\in\mathcal{B}(M)$, and if $\psi(B)\neq 0$, then we are done. Otherwise,
consider all the bases of the form $B-x+y$ with $x\in B$ and $y\in
E(M)\setminus B$. Among these bases, if there is none with a non-zero label,
then there does not exist a non-zero basis, otherwise, choose a non-zero basis
of minimum weight among the considered ones. Actually, this algorithm works
correctly for Weighted Non-Zero Basis for any group and the proof of [46,
Proposition 1] can be modified to show its correctness. In what follows, we
give a different proof of this fact.

######  Lemma 3.2.

Let $M$ be a matroid, $\psi\colon E(M)\to\Gamma$ a group labeling, and
$w\colon E(M)\to\mathbb{R}$ a weight function. Then, for any minimum-weight
basis $B$, there exists a minimum-weight non-zero basis $B^{*}$ such that
$|B\setminus B^{*}|\leq 1$, provided that at least one non-zero basis exists.

###### Proof.

Let $B^{\prime}$ be a minimum-weight non-zero basis with $|B\setminus
B^{\prime}|$ being minimal. If $B=B^{\prime}$ then we are done, otherwise
$\psi(B)=0$. According to the symmetric exchange axiom, we can choose $x\in
B\setminus B^{\prime}$ and $y\in B^{\prime}\setminus B$ such that $B-x+y$ and
$B^{\prime}+x-y$ are both bases. As
$0\neq\psi(B)+\psi(B^{\prime})=\psi(B-x+y)+\psi(B^{\prime}+x-y)$, one of
$B-x+y$ and $B^{\prime}+x-y$ must be non-zero. Suppose $\psi(B-x+y)\neq 0$.
Since $w(B)+w(B^{\prime})=w(B-x+y)+w(B^{\prime}+x-y)$ and $w(B)$ has the
minimum weight, we have $w(B-x+y)\leq w(B^{\prime})$, which implies
$w(B-x+y)=w(B^{\prime})$ by $\psi(B-x+y)\neq 0$. Thus, we can take
$B^{*}=B-x+y$. If $\psi(B^{\prime}+x-y)\neq 0$, then it can be shown in the
same way that $B^{\prime}+x-y$ is a minimum-weight non-zero basis,
contradicting the assumption that $B^{\prime}$ is a minimum-weight non-zero
basis closest to $B$. ∎

We obtain the following from Lemma 3.2.

######  Theorem 3.3.

Weighted Non-Zero Basis can be solved in polynomial time.

###  3.2 Non-zero Common Basis

This section is dedicated to Non-Zero Common Basis. For the algorithmic
tractability, it turns out that it is decisive whether $\Gamma$ contains
$\mathbb{Z}_{2}$ or not. In Section 3.2.1, for the case that $\Gamma$ does not
contain $\mathbb{Z}_{2}$, we give a polynomial-time algorithm for Non-Zero
Common Basis and a polynomial-time approximation algorithm for the weighted
version of the problem. While the hardness proof for the case that $\Gamma$
contains $\mathbb{Z}_{2}$ is postponed to Section 6, we give a polynomial-time
algorithm solving the weighted version for arbitrary groups in case that both
matroids are partition matroids or one of the two matroids is a partition
matroid with two partition classes in Section 3.2.3. We further give a
characterization of the no-instances if $\Gamma$ does not contain
$\mathbb{Z}_{2}$ in Section 3.2.2 and we deal with a connection of Non-Zero
Common Basis and reconfiguration problems in Section 3.2.4.

####  3.2.1 Polynomial-time Algorithm with $\mathbb{Z}_{2}\not\leq\Gamma$

In this section, we show the polynomial solvability of Non-Zero Common Basis
when $\mathbb{Z}_{2}\not\leq\Gamma$, that is, $\Gamma$ does not contain any
element of order two. Later, we will show in Theorem 6.1 that the problem is
hard if $\mathbb{Z}_{2}\leq\Gamma$. Our algorithm is a modification of the
weighted matroid intersection algorithm given by Krogdahl [42, 43, 44] and
independently by Brezovec, Cornuéjols, and Glover [9].

We will use the following result on directed graphs. While several works
concentrated on finding non-zero paths and cycles in group-labeled graphs
[32], their setting does not seem to include group-labeled digraphs.
Therefore, we give a proof of the next result in Appendix A. While this result
may be of independent interest, it will later be applied as a subroutine.

######  Theorem 3.4.

Let $D$ be a digraph, $\psi\colon A(D)\rightarrow\Gamma$ a group labeling, and
$w\colon A(D)\rightarrow\mathbb{R}$ a conservative weight function. Then,
there is a polynomial-time algorithm that returns a non-zero directed cycle in
$D$ which is shortest with respect to $w$ or correctly reports that $D$
contains no non-zero directed cycle.

Let $M_{1}$ and $M_{2}$ be matroids on a common ground set $E$ and $\psi\colon
E\to\Gamma$ a group labeling. Given a common basis $B$, we define the digraph
$D_{M_{1},M_{2}}(B)$ on vertex set $E$ and the labeling $\psi^{\prime}$ on its
arcs as follows. For each $x\in B$ and $y\in E\setminus B$ such that
$B-x+y\in\mathcal{B}(M_{1})$, we add an arc $xy$ to $D_{M_{1},M_{2}}(B)$ with
label $\psi^{\prime}(xy)\coloneqq\psi(y)$. Similarly, for each $x\in B$ and
$y\in E\setminus B$ such that $B-x+y\in\mathcal{B}(M_{2})$, we add an arc $yx$
and with label $\psi^{\prime}(yx)\coloneqq-\psi(x)$.

######  Lemma 3.5.

Let $M_{1}$ and $M_{2}$ be matroids on a common ground set $E$ and $\psi\colon
E\to\Gamma$ a group labeling. Let $B$ and $B^{\prime}$ be common bases of
$M_{1}$ and $M_{2}$ such that $\psi(B)=0$ and $\psi(B^{\prime})\neq 0$. Then,
$D_{M_{1},M_{2}}(B)$ contains a non-zero directed cycle $C$ with
$V(C)\subseteq B\mathbin{\triangle}B^{\prime}$.

###### Proof.

By Lemma 2.1, $D_{M_{1},M_{2}}(B)$ contains a collection $P_{1}$ of
$|B\setminus B^{\prime}|$ pairwise vertex-disjoint arcs from $B\setminus
B^{\prime}$ to $B^{\prime}\setminus B$ and a collection $P_{2}$ of
$|B\setminus B^{\prime}|$ pairwise vertex-disjoint arcs from
$B^{\prime}\setminus B$ to $B\setminus B^{\prime}$. The union of $P_{1}$ and
$P_{2}$ has label $\psi(B^{\prime}\setminus B)-\psi(B\setminus
B^{\prime})=\psi(B^{\prime})-\psi(B)=\psi(B)\neq 0$ and consists of pairwise
vertex-disjoint directed cycles in $D_{M_{1},M_{2}}(B)$, hence it contains a
non-zero directed cycle. ∎

We will rely on the following two lemmas by Krogdahl [42, 43, 44] and
Brezovec, Cornuéjols, and Glover [9]. For the proof of Lemma 3.6, see also
[62, Theorem 39.13].

######  Lemma 3.6 (Krogdahl [42, 43, 44]).

Let $B$ be a basis of a matroid $M$ and consider $X\subseteq B$ and
$X^{\prime}\subseteq E(M)\setminus B$ with $|X|=|X^{\prime}|$. If there exists
a unique bijection $\phi\colon X\to X^{\prime}$ such that $B-e+\phi(e)$ is a
basis for each $e\in X$, then $(B\setminus X)\cup X^{\prime}$ is a basis.

######  Lemma 3.7 (Brezovec–Cornuéjols–Glover [9]).

Let $C$ and $C^{\prime}$ be two different directed cycles in a digraph $D$
with $V(C)=V(C^{\prime})$. Then, there exist directed cycles
$C_{1},\dots,C_{t}$ for some $t\geq 3$ such that $V(C_{i})\subsetneq V(C)$ for
$i\in[t]$ and each arc of $D$ appears in $C_{1},\dots,C_{t}$ in total as many
times as it appears in $C$ and $C^{\prime}$ in total.

The following result and proof are analogous to that of [9, Theorem 2]. In
that result, a weight function is given instead of a labeling, and the
constraint “non-zero” is replaced by “negative”.

######  Lemma 3.8.

Let $\Gamma$ be a group such that $\mathbb{Z}_{2}\not\leq\Gamma$. Let $M_{1}$
and $M_{2}$ be matroids on a common ground set $E$, $\psi\colon E\to\Gamma$ a
group labeling, and $B$ a common basis. If $C$ is a non-zero directed cycle of
$D_{M_{1},M_{2}}(B)$ whose vertex set is inclusion-wise minimal among non-zero
directed cycles, then $B\mathbin{\triangle}V(C)$ is a common basis.

###### Proof.

Let $C$ be a non-zero directed cycle such that there exists no non-zero
directed cycle $C^{\prime}$ with $V(C^{\prime})\subsetneq V(C)$. Let
$X\coloneqq V(C)\cap B$ and $X^{\prime}\coloneqq V(C)\setminus B$. Assume for
contradiction that $(B\setminus X)\cup X^{\prime}$ is not a common basis. We
may assume by symmetry that $(B\setminus X)\cup
X^{\prime}\not\in\mathcal{B}(M_{1})$. Let $P_{1}$ and $P_{2}$ denote the sets
of arcs of $C$ directed from $B$ to $E\setminus B$ and from $E\setminus B$ to
$B$, respectively. Note that $P_{1}$ and $P_{2}$ are matchings between $X$ and
$X^{\prime}$ directed from $X$ to $X^{\prime}$ and from $X^{\prime}$ to $X$,
respectively. As $(B\setminus X)\cup X^{\prime}\not\in\mathcal{B}(M_{1})$, by
Lemma 3.6 there exists a matching $P^{\prime}_{1}$ between $X$ and
$X^{\prime}$ directed from $X$ to $X^{\prime}$ in $D_{M_{1},M_{2}}(B)$ which
is different from $P_{1}$. Let $C^{\prime}$ be defined by
$A(C^{\prime})=A(C)-P_{1}+P^{\prime}_{1}$. Observe that
$\psi^{\prime}(C^{\prime})=\psi^{\prime}(C)$ and $C^{\prime}$ is either the
union of at least two pairwise vertex-disjoint directed cycles or a single
directed cycle. In the first case, $C^{\prime}$ is the union of vertex-
disjoint directed cycles $C_{1},\dots,C_{t}$ such that $V(C_{i})\subsetneq
V(C)$ for $i\in[t]$, thus
$0\neq\psi(C^{\prime})=\psi^{\prime}(C_{1})+\dots+\psi^{\prime}(C_{t})$
implies that $\psi^{\prime}(C_{i})\neq 0$ for some $i\in[t]$. In the second
case, let $C_{1},\dots,C_{t}$ be the directed cycles provided by Lemma 3.7,
then $0\neq 2\psi^{\prime}(C)=\psi^{\prime}(C_{1})+\dots+\psi^{\prime}(C_{t})$
implies that $\psi^{\prime}(C_{i})\neq 0$ for some $i\in[t]$, using that
$\mathbb{Z}_{2}\not\leq\Gamma$. In both cases, $\psi^{\prime}(C_{i})\neq 0$
holds for some directed cycle $C_{i}$ with $V(C_{i})\subsetneq V(C)$,
contradicting the choice of $C$. ∎

Combining Lemmas 3.5 and 3.8, we obtain the main result of the section.

######  Theorem 3.9.

Let $\Gamma$ be a group such that $\mathbb{Z}_{2}\not\leq\Gamma$. Let $M_{1}$
and $M_{2}$ be matroids on a common ground set $E$, $\psi\colon E\to\Gamma$ a
group labeling, and $B_{0}$ a zero common basis. Then, $M_{1}$ and $M_{2}$
have a non-zero common basis if and only if $D_{M_{1},M_{2}}(B_{0})$ contains
a non-zero directed cycle. Moreover, Non-Zero Common Basis is polynomially
solvable.

###### Proof.

If there exists a non-zero common basis $B^{*}$, then $D_{M_{1},M_{2}}(B_{0})$
contains a non-zero directed cycle by Lemma 3.5. Conversely, if
$D_{M_{1},M_{2}}(B_{0})$ contains a directed cycle, then let $C$ be a minimum
length non-zero directed cycle. Then, Lemma 3.8 implies that $B^{*}\coloneqq
B\mathbin{\triangle}V(C)$ is a common basis, and we have
$\psi(B^{*})=\psi(B_{0})+\psi^{\prime}(C)=\psi^{\prime}(C)\neq 0$.

This provides the following algorithm for Non-Zero Common Basis. First, we
find a common basis $B_{0}$. If no common basis exists or $B_{0}$ is non-zero,
we are done. Otherwise, we find a minimum length non-zero directed cycle $C$
in $D_{M_{1},M_{2}}(B_{0})$ using Theorem 3.4. If no non-zero directed cycle
exists then we report that there is no non-zero common basis, otherwise we
output $B_{0}\mathbin{\triangle}V(C)$. ∎

We turn to the study of Weighted Non-Zero Common Basis. Given two matroids
$M_{1}$ and $M_{2}$ on a common ground set $E$, a common basis $B$, and a
weight function $w\colon E\to\mathbb{R}$, we define the weight function
$w^{\prime}$ on the arcs of $D_{M_{1},M_{2}}(B)$ as follows. For each arc $xy$
such that $x\in B$, $y\in E\setminus B$ and $B-x+y\in\mathcal{B}(M_{1})$ we
define $w^{\prime}(xy)\coloneqq w(y)$, and for each arc $yx$ such that $x\in
B$, $y\in E\setminus B$ and $B-x+y\in\mathcal{B}(M_{2})$ we define
$w^{\prime}(yx)\coloneqq-w(x)$. Then, $B$ is a minimum-weight common basis if
and only if $w^{\prime}$ is conservative [43, 26, 9], see also [62, Theorem
41.5]. We observe the following relationship between the weight of a shortest
non-zero directed cycle in $D_{M_{1},M_{2}}(B)$ and the weights of non-zero
common bases of $M_{1}$ and $M_{2}$.

######  Lemma 3.10.

Let $M_{1}$ and $M_{2}$ be matroids on a common ground set $E$, $\psi\colon
E\to\Gamma$ a group labeling, and $w\colon E\to\mathbb{R}$ a weight function.
Let $B_{0}$ be a minimum-weight common basis and assume that $\psi(B_{0})=0$.
Let $C$ be a shortest non-zero directed cycle in $D_{M_{1},M_{2}}(B_{0})$ with
respect to $w^{\prime}$. Then, $w(B_{0}\mathbin{\triangle}V(C))\leq w(B^{*})$
holds for each non-zero common basis $B^{*}$.

###### Proof.

Let $B^{*}$ a non-zero common basis. As in the proof of Lemma 3.5, Lemma 2.1
implies that $D_{M_{1},M_{2}}(B_{0})$ contains vertex-disjoint directed cycles
$C_{1},\dots,C_{q}$ such that $V(C_{1})\cup\dots\cup
V(C_{q})=B_{0}\mathbin{\triangle}B^{*}$ and one of the directed cycles is non-
zero, say, $\psi(C_{1})\neq 0$. Using the definition of $w^{\prime}$ and the
facts that $C$ is a shortest non-zero directed cycle and $w^{\prime}$ is
conservative, we obtain

$w(B_{0}\mathbin{\triangle}V(C))=w(B_{0})+w^{\prime}(C)\leq
w(B_{0})+w^{\prime}(C_{1})\leq
w(B_{0})+\sum_{i=1}^{q}w^{\prime}(C_{i})=w(B^{*}).\qed$

We note that Lemma 3.10 generalizes Lemma 3.2, as in the special case
$M_{1}=M_{2}$ each arc of $D_{M_{1},M_{2}}(B_{0})$ is bidirectional, thus a
shortest non-zero directed cycle consists of two vertices.

In Lemma 3.10, the weight of $C$ is measured by $w^{\prime}$ (which takes
negative values on some arcs) so $V(C)$ is not necessarily inclusion-wise
minimal among the vertex sets of non-zero directed cycles. Thus, it does not
yield an algorithm for Weighted Non-Zero Common Basis. In fact, the complexity
of the problem remains open for a group $\Gamma$ with
$\mathbb{Z}_{2}\not\leq\Gamma$. Nevertheless, we use Lemma 3.10 to give a
2-approximation if the weight function $w$ is nonnegative.

######  Theorem 3.11.

Let $\Gamma$ be a group with $\mathbb{Z}_{2}\not\leq\Gamma$. Let $M_{1}$ and
$M_{2}$ be matroids on a common ground set $E$, $\psi\colon E\to\Gamma$ a
group labeling, and $w\colon E\to\mathbb{R}_{\geq 0}$ a weight function. Then,
there exists a polynomial-time algorithm that computes a non-zero common basis
$B$ that satisfies $w(B)\leq 2w(B^{*})$ for every non-zero common basis
$B^{*}$ or correctly outputs that there exists no non-zero common basis.

###### Proof.

First, we compute a minimum-weight common basis $B_{0}$. This is possible due
to the algorithm of Edmonds [20], see also [24, Section 13.2.2] for details.
If no common basis exists or $B_{0}$ is non-zero, we are done. Otherwise,
using Theorem 3.4 we compute a shortest non-zero directed cycle $C$ in
$D_{M_{1},M_{2}}(B_{0})$ with weight function $w^{\prime}$. If no non-zero
directed cycle exists then we obtain by Theorem 3.9 that no non-zero common
basis exists. Otherwise, using Theorem 3.4 we compute a shortest non-zero
directed cycle $C^{\prime}$ in $D_{M_{1},M_{2}}(B_{0})[V(C)]$ with unit
weights. We let the algorithm return $B\coloneqq
B_{0}\mathbin{\triangle}V(C^{\prime})$, which is a non-zero common basis by
Lemma 3.8. Using $B\subseteq B_{0}\cup V(C)$, $w\geq 0$, Lemma 3.10 and the
fact that $B_{0}$ is a minimum-weight common basis, we get that

$w(B)\leq w(B_{0}\cup V(C))\leq w(B_{0})+w(B_{0}\mathbin{\triangle}V(C))\leq
2w(B^{*})$

holds for each non-zero common basis $B^{*}$. ∎

####  3.2.2 Certificate for All Common Bases Being Zero

In this section we give a characterization for all all directed cycles of
$D_{M_{1},M_{2}}(B)$ having label zero, analogous to the weight-splitting
theorem of Frank [23]. By Theorem 3.9, this provides a certificate for the no-
instances of Non-Zero Common Basis if $\mathbb{Z}_{2}\not\leq\Gamma$.

For the characterization, we will use the following result on strongly
connected digraphs. Its special case for cyclic groups appears in [2, Theorem
10.5.1] where the authors note that its origin is unclear. The proof given
there shows that the result holds for any abelian group $\Gamma$ as well.

######  Theorem 3.12.

Let $D$ be a strongly connected digraph and $\psi\colon A(D)\to\Gamma$ a group
labeling. Then, all directed cycles of $D$ are zero if and only if there
exists a labeling $\varphi\colon V(D)\to\Gamma$ such that
$\psi(uv)=\varphi(v)-\varphi(u)$ for each arc $uv\in A(D)$.

To apply Theorem 3.12 to $D_{M_{1},M_{2}}(B)$, we need to ensure its strong
connectivity, which is described in the next statement.

######  Lemma 3.13.

Let $M_{1}$ and $M_{2}$ be matroids with the common ground set $E$ and the
same rank $r$, and let $B$ be a common basis of $M_{1}$ and $M_{2}$. Then,
$D_{M_{1},M_{2}}(B)$ is strongly connected if and only if
$r_{M_{1}}(X)+r_{M_{2}}(E\setminus X)>r$ holds for $\emptyset\neq X\subsetneq
E$.

###### Proof.

Since $M_{1}$ and $M_{2}$ have a common basis,
$r_{M_{1}}(X)+r_{M_{2}}(E\setminus X)\geq r$ holds for $X\subseteq E$. We show
that a set $X\subseteq E$ has in-degree zero in $D_{M_{1},M_{2}}(B)$ if and
only if $r_{M_{1}}(X)+r_{M_{2}}(E\setminus X)=r$. By definition, there is no
arc from $B\setminus X$ to $X\setminus B$ if and only if $B-x+y$ is not a
basis of $M_{1}$ for any $x\in B\setminus X$ and $y\in X\setminus B$. This is
equivalent to that $C_{M_{1}}(B,y)\subseteq(B\cap X)+y$ holds for every $y\in
X\setminus B$, which happens if and only if $B\cap X$ spans $X$ in $M_{1}$,
that is, $r_{M_{1}}(X)=|B\cap X|$. Similarly, there is no arc from
$E\setminus(B\cap X)$ to $B\cap X$ if and only if $r_{M_{2}}(E\setminus
X)=|B\setminus X|$. Therefore, no arc enters $X$ if and only if
$r_{M_{1}}(X)=|B\cap X|$ and $r_{M_{2}}(E\setminus X)=|B\setminus X|$ both
hold, which is equivalent to $r_{M_{1}}(X)+r_{M_{2}}(E\setminus X)=r$. ∎

We note that if $r_{M_{1}}(X)+r_{M_{2}}(E\setminus X)=r$ holds for a set
$\emptyset\neq X\subsetneq E$, then the common bases of $M_{1}$ and $M_{2}$
are exactly the sets that can be obtained as the union of a common basis of
$M_{1}\mathbin{|}X$ and $M_{2}\mathbin{/}(E\setminus X)$ and a common basis of
$M_{1}\mathbin{/}(E\setminus X)$ and $M_{2}\mathbin{|}X$. Therefore, $M_{1}$
and $M_{2}$ have two common bases of different labels if and only if one of
the smaller matroid pairs $M_{1}\mathbin{|}X$, $M_{2}\mathbin{/}(E\setminus
X)$ and $M_{1}\mathbin{/}(E\setminus X)$, $M_{2}\mathbin{|}X$ has two common
bases of different labels. This implies that when solving Non-Zero Common
Basis, we may assume that no such $X$ exists. Note that if such a set exists
then we can find it in polynomial time, e.g., by minimizing the the submodular
function $f(Z)\coloneqq r_{M_{1}}(Z)+r_{M_{2}}(E\setminus Z)$ over the sets
$\emptyset\neq Z\neq E$ which can be performed in polynomial time [15].

We are ready to give the main result of this section. Our proof is similar to
that of the weight-splitting theorem of Frank [23] given in [62, Section
41.3a].

######  Theorem 3.14.

Let $M_{1}$ and $M_{2}$ be matroids with the common ground set $E$ and the
same rank $r$. Assume that $r_{M_{1}}(X)+r_{M_{2}}(E\setminus X)>r$ holds for
every $\emptyset\neq X\subsetneq E$. Let $B$ be a common basis of $M_{1}$ and
$M_{2}$, and $\psi\colon E\to\Gamma$ a group labeling. Then,
$D_{M_{1},M_{2}}(B)$ contains no non-zero directed cycle if and only if there
exist labelings $\psi_{1},\psi_{2}\colon E\to\Gamma$ such that
$\psi=\psi_{1}+\psi_{2}$ and $\psi_{i}$ is constant on each connected
component of $M_{i}$ for $i=1,2$.

###### Proof.

By the assumption and Lemma 3.13, we get that $D_{M_{1},M_{2}}(B)$ is strongly
connected.

First suppose that there exist labelings $\psi_{1},\psi_{2}\colon E\to\Gamma$
such that $\psi=\psi_{1}+\psi_{2}$ and $\psi_{i}$ is constant on each
connected component of $M_{i}$ for $i=1,2$, and let
$C=x_{1},y_{1},x_{2},\ldots,x_{t},y_{t},x_{1}$ be a directed cycle in
$D_{M_{1},M_{2}}(B)$. Let $X\coloneqq\\{x_{1},\ldots,x_{t}\\}$ and
$Y\coloneqq\\{y_{1},\ldots,y_{t}\\}$. By symmetry and construction, we may
suppose that $X\subseteq B$ and $Y\subseteq E\setminus B$. By construction,
for $i\in[t]$, we have that $x_{i}$ and $y_{i}$ are in the same component of
$M_{1}$, hence $\psi_{1}(x_{i})=\psi_{1}(y_{i})$. Similarly, we have
$\psi_{2}(y_{i})=\psi_{2}(x_{i+1})$ for $i\in[t-1]$ and
$\psi_{2}(y_{t})=\psi_{2}(x_{1})$. This yields

$\displaystyle\psi^{\prime}(C)$ $\displaystyle=\psi(Y)-\psi(X)$
$\displaystyle=\psi_{1}(Y)-\psi_{1}(X)+\psi_{2}(Y)-\psi_{2}(X)$
$\displaystyle=\sum_{i=1}^{t}(\psi_{1}(y_{i})-\psi_{1}(x_{i}))+\sum_{i=1}^{t-1}(\psi_{2}(y_{i})-\psi_{2}(x_{i+1}))+(\psi_{2}(y_{t})-\psi_{2}(x_{1}))$
$\displaystyle=0.$

It follows that $D_{M_{1},M_{2}}(B)$ does not contain any non-zero directed
cycle.

Now suppose that $D_{M_{1},M_{2}}(B)$ does not contain any non-zero directed
cycle. Then, by Theorem 3.12, there exists a labeling $\varphi\colon
E\to\Gamma$ such that $\psi^{\prime}(xy)=\varphi(y)-\varphi(x)$ holds for each
arc $xy$ of $D_{M_{1},M_{2}}(B)$. Let $\psi_{1},\psi_{2}\colon E\to\Gamma$ be
defined by

$\psi_{1}(e)=\begin{cases}-\varphi(e)&\text{if $e\in B$},\\\
-\varphi(e)+\psi(e)&\text{if $e\in E\setminus
B$},\end{cases}\quad\psi_{2}(e)=\begin{cases}\varphi(e)+\psi(e)&\text{if $e\in
B$},\\\ \varphi(e)&\text{if $e\in E\setminus B$}.\end{cases}$

Then, $\psi=\psi_{1}+\psi_{2}$ holds by construction. Now let $x\in B$ and
$y\in E\setminus B$ such that $B-x+y$ is a basis of $M_{1}$. We obtain

$\displaystyle\psi_{1}(B-x+y)-\psi_{1}(B)$
$\displaystyle=\psi_{1}(y)-\psi_{1}(x)$
$\displaystyle=\psi(y)-\varphi(y)+\varphi(x)$
$\displaystyle=\psi^{\prime}(xy)-\psi^{\prime}(xy)$ $\displaystyle=0.$

It follows by Theorem 3.1 that $\psi_{1}$ is constant on every component of
$M_{1}$. A similar argument shows that $\psi_{2}$ is constant on every
component of $M_{2}$. ∎

####  3.2.3 Partition Matroids

When both matroids are partition matroids, we can drop the assumption
$\mathbb{Z}_{2}\not\leq\Gamma$ from Theorem 3.9 and extend it to the weighted
setting.

######  Theorem 3.15.

Weighted Non-Zero Common Basis is polynomially solvable if $M_{1}$ and $M_{2}$
are partition matroids.

###### Proof.

The proof relies on the following property of partition matroids.

######  Claim 3.16.

Let $B$ be a common basis and $C$ a directed cycle of $D_{M_{1},M_{2}}(B)$.
Then, $B\mathbin{\triangle}V(C)$ is a common basis.

###### Proof.

For $i=1,2$, let $M_{i}$ be the direct sum of uniform matroids on
$E^{i}_{1}\cup\dots\cup E^{i}_{t_{i}}$ having rank
$g^{i}_{1},\dots,g^{i}_{t_{i}}$, respectively. Then,
$\mathcal{B}(M_{i})=\\{\,B\subseteq
E\mathclose{}\nonscript\;|\nonscript\;\mathopen{}|B\cap E^{i}_{j}|=1\text{ for
each $j\in[t_{i}]$}\,\\}$, thus $B-x+y$ is a basis of $M_{i}$ for $x\in B$,
$y\in E\setminus B$ if and only if $\\{x,y\\}\subseteq E^{i}_{j}$ for some
$j\in[t_{i}]$. By the definition of $D_{M_{1},M_{2}}(B)$, this implies that
$|(V(C)\cap B)\cap E^{i}_{j}|=|(V(C)\setminus B)\cap E^{i}_{j}|$ for each
$j\in[t_{i}]$ and $i\in[2]$, thus $B\mathbin{\triangle}V(C)$ is a common
basis. ∎

We turn to the proof of the theorem. As in the proof of Theorem 3.11, we may
assume to have a minimum weight common basis $B_{0}$ with $\psi(B_{0})=0$, and
a shortest non-zero directed cycle $C$ in $D_{M_{1},M_{2}}(B_{0})$. Then,
$B_{0}\mathbin{\triangle}V(C)$ is a minimum weight non-zero common basis by
3.16 and Lemma 3.10. ∎

Given a graph $G$ and a function $b\colon V(G)\to\mathbb{Z}_{\geq 0}$, a
_perfect $b$-matching_ is an edge set $F\subseteq E(G)$ such that
$d_{F}(v)=b(v)$ for each $v\in V$. If $G$ is bipartite, then its perfect
$b$-matchings form the family of common bases of two partition matroids.
Therefore, Theorem 3.15 can be formulated as having a polynomial-time
algorithm for finding a minimum weight non-zero perfect $b$-matching in a
bipartite graph with weights and labels on its edges. For perfect matchings
and the group $\mathbb{Z}_{2}$, the idea of essentially the same algorithm as
ours was briefly mentioned in [34], where the authors noted that it can also
be derived from results of [1]. A formal description of the algorithm and a
proof of its correctness was given in [22] for a special weight function.

Next, we consider the special case of Weighted Non-Zero Common Basis when we
only assume that one of the matroids is a partition matroid. Without further
assumptions, this problem is not easier than the general one: a construction
similar to that of Harvey, Király and Lau [30] shows that the general problem
can be reduced to a special case when one of the matroids is a unitary
partition matroid and all partition classes have size two. In what follows, we
will consider the case when the partition matroid is defined by a partition
having two classes. In this special case, the polynomial solvability of Non-
Zero Common Basis follows from the corresponding lattice basis
characterization of Rieder [61]. We extend this result by solving the weighted
version of the problem.

######  Theorem 3.17.

Weighted Non-Zero Common Basis is polynomially solvable if $M_{2}$ is a
partition matroid defined by a partition having two classes.

In order to prove Theorem 3.17 we will use the following lemma to study the
directed cycles of $D_{M_{1},M_{2}}(B)$.

######  Lemma 3.18.

Let $m,k\in\mathbb{N}$, $A$ and $A^{\prime}$ disjoint $m$-element sets,
$V\coloneqq A\cup A^{\prime}$, $c\colon V\to[k]$ a function, and
$V_{i}\coloneqq\\{\,v\in
V\mathclose{}\nonscript\;|\nonscript\;\mathopen{}c(v)=i\,\\}$ for $i\in[k]$.
Consider a digraph $D$ on vertex set $V$ such that its arc set consists of $m$
vertex-disjoint arcs from $A$ to $A^{\prime}$ and the arc set
$\\{\,a^{\prime}a\mathclose{}\nonscript\;|\nonscript\;\mathopen{}i,j\in[m],c(a)=c(a^{\prime})\,\\}$.
Then, there exist vertex-disjoint directed cycles $C_{1},\dots,C_{t}$ in $D$
such that $V(C_{1})\cup\dots\cup V(C_{t})=V$ and $|V(C_{i})|\leq 2k$ for
$i\in[t]$.

###### Proof.

We use induction on $m$. Observe that each vertex of $D$ has outdegree at
least one. Indeed, the outdegree of each vertex $a\in A$ is one due to the
arcs from $A$ to $A^{\prime}$, and the outdegee of each $a^{\prime}\in
A^{\prime}$ is at least one since $|A\cap V_{c(a^{\prime})}|=|A^{\prime}\cap
V_{c(a^{\prime})}|\geq 1$. This implies that $D$ contains a directed cycle,
let $C$ be one of minimum length. It is not difficult to see that $C$ being of
minimum length implies that $c(a^{\prime}_{1})\neq c(a^{\prime}_{2})$ for all
distinct $a^{\prime}_{1},a^{\prime}_{2}\in A$. Then, $|V(C)|=2|V(C)\cap
A^{\prime}|\leq 2k$. Since $|V(C)\cap A\cap V_{i}|=|V(C)\cap A^{\prime}\cap
V_{i}|$ for each $i\in[k]$, it follows by induction that $D-V(C)$ contains a
collection of vertex-disjoint directed cycles $C_{1},\dots,C_{t}$ each of
which is of length at most $2k$ such that $V(C_{1})\cup\dots\cup
V(C_{t})=V\setminus V(C)$. The statement then follows by adding $C$ to the
collection $C_{1},\dots,C_{t}$. ∎

As a consequence, we derive the following property of $D_{M_{1},M_{2}}(B)$
when $M_{2}$ is a partition matroid and $B$ is a minimum-weight common basis.
In the following, the length of a directed cycle is its number of arcs while
“shortest” refers to the weight function.

######  Lemma 3.19.

Let $k\geq 1$, $M_{1}$ be a matroid and $M_{2}$ a partition matroid on ground
set $E$ such that $M_{2}$ is defined by a partition having $k$ classes. Let
$\psi\colon E\to\Gamma$ be a group labeling, $w\colon E\to\mathbb{R}$ a weight
function and $B$ a minimum-weight common basis of $M_{1}$ and $M_{2}$. Then,
the shortest non-zero directed cycle in $D_{M_{1},M_{2}}(B)$ has length at
most $2k$, provided that it has a non-zero directed cycle.

###### Proof.

Let $E_{1},\dots,E_{k}$ denote the partition defining $M_{2}$. Let $C$ be a
shortest non-zero directed cycle in $D_{M_{1},M_{2}}(B)$ with respect to
$\psi^{\prime}$ and $w^{\prime}$. Using the definition of
$D_{M_{1},M_{2}}(B)$, it follows that $|(V(C)\cap B)\cap
E_{i}|=|(V(C)\setminus B)\cap E_{i}|$ for each $i\in[k]$. Applying Lemma 3.18
to $A\coloneqq V(C)\cap B$, $A^{\prime}\coloneqq V(C)\setminus B$, the digraph
induced by $A\cup A^{\prime}$ in $D_{M_{1},M_{2}}(B)$, and the function
$c\colon V(C)\to[k]$ satisfying $E_{i}\cap V(C)=\\{\,v\in
V(C)\mathclose{}\nonscript\;|\nonscript\;\mathopen{}c(v)=i\,\\}$ for each
$i\in[k]$, we get that $D_{M_{1},M_{2}}(B)$ contains vertex-disjoint directed
cycles $C_{1},\dots,C_{t}$ such that $V(C_{1})\cup\dots\cup V(C_{t})=V(C)$ and
$|V(C_{i})|\leq 2k$ for each $i\in[t]$. As $B$ is a minimum-weight basis,
$w^{\prime}$ is conservative, this $w(C_{i})\leq w(C)$ for each $i\in[t]$.
Since $C$ is non-zero and $\psi(C)=\psi(C_{1})+\dots+\psi(C_{t})$, it follows
that $\psi(C_{i})\neq 0$ for some $i\in[t]$. As $C$ is a shortest non-zero
directed cycle, we get $i=t=1$, and the statement follows by $|V(C_{1})|\leq
2k$. ∎

We will use Lemma 3.19 for $k=2$ combined with the following observation.

######  Lemma 3.20.

Let $M_{1}$ and $M_{2}$ be matroids on a common ground set $E$, $\psi\colon
E\to\Gamma$ a group labeling, $w\colon E\to\mathbb{R}$ a weight function, and
$B$ a minimum-weight common basis. Suppose that $C$ is a shortest non-zero
directed cycle in $D_{M_{1},M_{2}}(B)$ and $|V(C)|\leq 4$. Then,
$B\mathbin{\triangle}V(C)$ is a common basis.

###### Proof.

Using the definition of $D_{M_{1},M_{2}}(B)$ we have that $|V(C)|\in\\{2,4\\}$
and $B\mathbin{\triangle}V(C)$ is a common basis for $|V(C)|=2$. It remains to
consider the case $|V(C)|=4$. Let $b_{1}b^{\prime}_{1}$,
$b^{\prime}_{1}b_{2}$, $b_{2}b^{\prime}_{2}$, $b^{\prime}_{2}b_{1}$ denote the
arcs of $C$ such that $b_{1},b_{2}\in B$ and
$b^{\prime}_{1},b^{\prime}_{2}\notin B$. Suppose that
$B\mathbin{\triangle}V(C)$ is not a common basis. By symmetry, we may assume
that it is not a basis of $M_{1}$. Then, Lemma 3.6 implies that
$B-b_{1}+b^{\prime}_{2}$ and $B-b_{2}+b^{\prime}_{1}$ are bases of $M_{1}$,
that is, $b_{1}b^{\prime}_{2}$ and $b_{2}b^{\prime}_{1}$ are arcs of
$D_{M_{1},M_{2}}(B)$. Let $C_{1}$ and $C_{2}$ denote the directed cycles with
arc sets $\\{b_{1}b^{\prime}_{2},b^{\prime}_{2}b_{1}\\}$ and
$\\{b_{2}b^{\prime}_{1},b^{\prime}_{1}b_{2}\\}$, respectively. Then, $C_{1}$
and $C_{2}$ are directed cycles in $D_{M_{1},M_{2}}(B)$ such that
$w(C_{i})\leq w(C)$ for $i=1,2$ and $\psi(C_{1})+\psi(C_{2})=\psi(C)\neq 0$,
thus $\psi(C_{i})\neq 0$ for some $i\in[2]$. This contradicts $C$ being a
shortest non-zero directed cycle. ∎

We are ready to prove Theorem 3.17.

###### Proof of Theorem 3.17.

As in the proof of Theorem 3.11, we may assume to have a minimum weight common
basis $B_{0}$ with $\psi(B_{0})=0$ and a shortest non-zero directed cycle $C$
in $D_{M_{1},M_{2}}(B_{0})$. Then, $B_{0}\mathbin{\triangle}V(C)$ is a common
basis by Lemmas 3.19 and 3.20, thus it is a minimum weight non-zero common
basis by Lemma 3.10. ∎

####  3.2.4 Relation to Reconfiguration Problems

We discuss the relation of Non-Zero Common Basis to a reconfiguration problem
on matroids. For common bases $B$ and $B^{\prime}$ of matroids $M_{1}$ and
$M_{2}$, we define a _reconfiguration sequence_ from $B$ to $B^{\prime}$ as a
sequence of common bases $B_{0},B_{1},\dots,B_{\ell}$ such that $B_{0}=B$,
$B_{\ell}=B^{\prime}$ and $|B_{i-1}\setminus B_{i}|=|B_{i}\setminus
B_{i-1}|=1$ for each $i\in[\ell]$. In general, a reconfiguration sequence
might not exist, in fact, it is hard to decide if a reconfiguration sequence
exists between given bases $B$ and $B^{\prime}$ [41]. Nevertheless, it is
known for some matroid pairs that a reconfiguration sequence exists and can be
found in polynomial time between any pair of common bases. Such matroid pairs
include a regular matroid and its dual [5], the family of arborescences (or
$r$-arborescences for a fixed root $r$) in a digraph [66], or more generally,
arc sets that can be partitioned into $k$ arborescences (or $r$-arborescences
for a fixed root $r$) for a fixed $k\geq 1$ [41]. Note that these arc sets can
be represented as common bases of two matroids, see [63, Corollary 53.1c]. We
show that Non-Zero Common Basis is solvable for such matroid pairs using an
idea similar to the solution of the exact arborescence problem for
$(0,1)$-valued weight functions by Barahona and Pulleyblank [3].

######  Theorem 3.21.

Let $M_{1}$ and $M_{2}$ be matroids such that a reconfiguration sequence
exists and can be found in polynomial time between any pair of common bases.
Then, Non-Zero Common Basis is polynomially solvable for $M_{1}$ and $M_{2}$.

###### Proof.

We may assume that $M_{1}$ and $M_{2}$ have a common basis. Let
$g_{1},\dots,g_{m}$ be an arbitrary ordering of the set
$\\{\,\psi(e)\mathclose{}\nonscript\;|\nonscript\;\mathopen{}e\in E\,\\}$. Let
us define $s\colon E\to\mathbb{Z}^{m}$ such that
$s(e)=(s_{1}(e),\dots,s_{m}(e))$ for each $e\in E$ where for each $i\in[m]$,
$s_{i}(e)=1$ if $\psi(e)=g_{i}$ and $s_{i}(e)=0$ otherwise. Compute a minimum
and maximum $s$-weight common basis $B_{-}$ and $B_{+}$, respectively, with
respect to the lexicographic ordering on $\mathbb{Z}^{m}$. If
$s(B_{-})=s(B_{+})$, then the $s$-weight of each common basis is the same,
implying that the label of each common basis is the same. Thus, in this case
we can output $B_{-}$ if $\psi(B_{-})\neq 0$, otherwise we correctly report
that no non-zero common basis exists. It remains to consider the case
$s(B_{-})\neq s(B_{+})$. By the assumption of the theorem, we can find a
sequence of common bases $B_{0},\dots,B_{\ell}$ such that $B_{0}=B_{-}$,
$B_{\ell}=B_{+}$ and $|B_{i}\setminus B_{i-1}|=1$ for each $i\in[\ell]$. Since
$s(B_{0})\neq s(B_{\ell})$, there exists $i\in[\ell]$ such that
$s(B_{i-1})\neq s(B_{i})$. As $|B_{i}\setminus B_{i-1}|=1$, this implies that
$\psi(B_{i})-\psi(B_{i-1})=g_{j}-g_{j^{\prime}}$ for some distinct
$j,j^{\prime}\in[m]$, in particular, $\psi(B_{i})\neq\psi(B_{i-1})$.
Therefore, at least one of $B_{i-1}$ and $B_{i}$ provides a solution to Non-
Zero Common Basis. ∎

##  4 Algebraic Algorithm for $F$-avoiding Basis and Common Basis

We present a randomized polynomial-time algorithm for $F$-avoiding Common
Basis for representable matroids given as matrices over a field $\mathbb{F}$
and a finite group $\Gamma$ given as an operation table. Our algorithm is a
generalization of the exact-weight matroid intersection algorithm for
representable matroids by Camerini, Galtiati, and Maffioli [13]. A similar
algebraic algorithm has also been considered by Webb [69, Section 3.7].

Before describing the algorithm, we introduce needed algebraic notions and
results. We assume that the arithmetic operations and the zero test over
$\mathbb{F}$ can be performed in constant time. In this section, we use the
multiplicative notation for the operation of $\Gamma$, and let $e$ denote the
group unit (zero) of $\Gamma$ instead of $0$. The _group ring_
$\mathbb{F}[\Gamma]$ of $\Gamma$ over $\mathbb{F}$ is the set of formal
$\mathbb{F}$-coefficient linear combinations of the elements in $\Gamma$,
i.e.,
$\mathbb{F}[\Gamma]\coloneqq\\{\,\sum_{g\in\Gamma}a_{g}g\mathclose{}\nonscript\;|\nonscript\;\mathopen{}a_{g}\in\mathbb{F}\;(g\in\Gamma)\,\\}$.
The addition and multiplication of
$f=\sum_{g\in\Gamma}a_{g}g\in\mathbb{F}[\Gamma]$ and
$h=\sum_{g\in\Gamma}b_{g}g\in\mathbb{F}[\Gamma]$ are naturally defined as
$f+h=\sum_{g\in\Gamma}(a_{g}+b_{g})g$ and
$fh=\sum_{g,g^{\prime}\in\Gamma}a_{g}b_{g^{\prime}}gg^{\prime}$. With these
operations, $\mathbb{F}[\Gamma]$ forms a commutative ring, containing
$\mathbb{F}$ as a subring under the natural identification $\mathbb{F}\ni
a\mapsto ae\in\mathbb{F}[\Gamma]$. Note that the operations of
$\mathbb{F}[\Gamma]$ and the zero test can be performed in polynomially many
operations of $\mathbb{F}$ and $\Gamma$.

Our algorithm will require the field $\mathbb{F}$ to be sufficiently large. If
$\mathbb{F}$ is a small finite field $\mathrm{GF}(q)$, where $q$ is a prime
power, we use the following result from algebraic computation to extend
$\mathbb{F}$ to $\mathrm{GF}(q^{d})$ by finding an irreducible polynomial
$p\in\mathbb{F}[x]$ of degree $d$ as
$\mathrm{GF}(q^{d})\simeq\mathbb{F}[x]/(p)$.

######  Theorem 4.1 (see [68, Corollarly 4.6, Theorem 14.42]).

Let $\mathbb{F}=\mathrm{GF}(q)$ for some prime power $q$ and $d\in\mathbb{N}$.
There is a randomized algorithm to find an irreducible polynomial of degree
$d$ over $\mathbb{F}$ in time polynomial in $\log q$ and $d$ in expectation.
After this preprocessing, we can represent every element in
$\mathrm{GF}(q^{d})$ as a $d$-tuple of elements in $\mathbb{F}$ and emulate
the arithmetic operations and the zero test over $\mathrm{GF}(q^{d})$ in time
polynomial in $d$.

For finite sets $R$ and $C$, we mean by an _$R\times C$ matrix_ a matrix of
size $|R|\times|C|$ whose rows and columns are identified with $R$ and $C$,
respectively. We simply write $[r]\times C$ as $r\times C$ for
$r\in\mathbb{Z}_{\geq 0}$. Given a ground set $E$ and a labeling $\psi\colon
E\to\Gamma$, we define an $E\times E$ diagonal matrix $D_{\psi}$ as follows:
for every $j\in E$, we set the $(j,j)$ diagonal entry of $D_{\psi}$ as
$x_{j}\psi(j)$, where $x_{j}$ is an indeterminate (variable) whose actual
value comes from $\mathbb{F}$. Then, $D_{\psi}$ is regarded as a matrix over
the group ring $\mathbb{F}(\\{x_{e}\\}_{e\in E})[\Gamma]$, where
$\mathbb{F}(\\{x_{e}\\}_{e\in E})$ denotes the rational function field over
$\mathbb{F}$ in $|E|$ indeterminates $\\{x_{e}\\}_{e\in E}$.

The following is a modification of a claim of Tomizawa and Iri [67], who first
used the Cauchy–Binet formula in the context of linear matroid intersection.

######  Lemma 4.2.

Let $\mathbb{F}$ be a field, $M_{1}$ and $M_{2}$ $\mathbb{F}$-representable
matroids with the common ground set $E$ and the same rank $r$, $A_{k}$ an
$r\times E$ matrix representing $M_{k}$ for $k=1,2$, and $\psi\colon
E\to\Gamma$ a labeling. Let $\Xi=A_{1}D_{\psi}A_{2}^{\top}$. Then, the
coefficient of $g\in\Gamma$ in $\det(\Xi)$ is a non-zero polynomial in
$\\{x_{j}\\}_{j\in E}$ if and only if a common basis with label $g$ exists.

###### Proof.

By the Cauchy–Binet formula, we can expand $\det(\Xi)$ as

$\displaystyle\det(\Xi)=\sum_{B\in\binom{E}{r}}\det(A_{1}[B])\det(A_{2}[B])\prod_{j\in
B}x_{j}\cdot\psi(B),$ (1)

where $A_{k}[B]$ denotes the submatrix of $A_{k}$ obtained by extracting the
columns in $B$ for $k=1,2$. Observe that $\det(A_{1}[B])\det(A_{2}[B])$ is
non-zero if and only if $B$ is a common basis of $M_{1}$ and $M_{2}$, and the
terms coming from different common bases do not cancel out thanks to the
factor $\prod_{j\in B}x_{j}$, proving the claim. ∎

Lemma 4.2 together with the Schwartz–Zippel lemma [47, 64, 71], division-free
determinant algorithm [35], search-to-decision reduction, and the field
extension for small fields give rise to a randomized algebraic algorithm for
$F$-avoiding Common Basis.

######  Theorem 4.3.

Let $\mathbb{F}$ be a field and $M_{1}$ and $M_{2}$ $\mathbb{F}$-representable
matroids with the common ground set $E$. There is a randomized algorithm that,
given matrices $A_{1}$ and $A_{2}$ over $\mathbb{F}$ representing $M_{1}$ and
$M_{2}$, respectively, the operation table of a finite abelian group $\Gamma$,
a group labeling $\psi\colon E\to\Gamma$, and a forbidden label set
$F\subseteq\Gamma$, solves $F$-avoiding Common Basis in expected polynomial
time.

###### Proof.

We may assume that $M_{1}$ and $M_{2}$ have the same rank $r$ and the matrices
$A_{1}$ and $A_{2}$ are of size $r\times E$. If $\mathbb{F}$ is a finite field
$\mathrm{GF}(q)$ and $q\leq 4nr$ with $n=|E|$, we first extend $\mathbb{F}$ to
$\mathrm{GF}(q^{d})$ so that it satisfies $|\mathrm{GF}(q^{d})|=q^{d}\geq 4nr$
by applying Theorem 4.1 with $d=\lceil\log_{q}2nr\rceil$. In the following, we
assume that $|\mathbb{F}|\geq 2nr$ holds.

Let $\Xi=A_{1}D_{\psi}A_{2}^{\top}$ be the matrix in Lemma 4.2 and
$H\subseteq\mathbb{F}$ an arbitrary finite set with $|H|\geq 2nr$. We first
build an algorithm for the decision version as follows: for every $j\in E$,
draw $a_{j}\in H$ from the uniform distribution over $H$, substitute $a_{j}$
for $x_{j}$ in $\Xi$, compute $\det(\Xi)\in\mathbb{F}[\Gamma]$, and report
that an $F$-avoiding common basis exists if the coefficient of $g$ in
$\det(\Xi)$ is non-zero for some $g\in\Gamma\setminus F$; otherwise, the
algorithm concludes that it does not. The complexity of this algorithm is
polynomial in $n$ and $|\Gamma|$ because the determinant over
$\mathbb{F}[\Gamma]$ can be calculated with polynomially many operations of
$\mathbb{F}[\Gamma]$ by using a division-free determinant algorithm, e.g.,
[35]. From Lemma 4.2, this algorithm reports correctly if there is no
$F$-avoiding common basis, and otherwise the probability of success can be
lower-bounded by $1-\frac{r}{|H|}\geq 1-\frac{1}{2n}$ via the Schwartz–Zippel
lemma since every non-vanishing term in $\det(\Xi)$ is of total degree $r$ as
a polynomial in $\\{x_{j}\\}_{j\in E}$.

To construct an actual $F$-avoiding common basis, we use the so-called search-
to-decision reduction based on the self-reducibility as follows. Fix an
arbitrary ordering $j_{1},\dotsc,j_{n}$ of $E$. From $k=1$ to $n$, we use the
above decision algorithm to test whether removing $j_{k}$ from the ground set
retains the existence of an $F$-avoiding common basis. If so, we actually
remove $j_{k}$ from $E$; otherwise, we do nothing. The removal of an element
is represented by deleting corresponding columns from $A_{1}$ and $A_{2}$. The
final ground set $E$ is an $F$-avoiding common basis if all invocations of the
decision algorithm have reported correctly. By the union bound, the
probability of success is at least $1-n\cdot\frac{1}{2n}=\frac{1}{2}$. We thus
check whether the final $E$ is an $F$-avoiding common basis or not and repeat
the algorithm until we get an $F$-avoiding common basis. Since the probability
of failing the first $k$ attempts is at most $\frac{1}{2^{k}}$ for any
$k\in\mathbb{N}$, the expected running time is upper-bounded by
$\sum_{k=1}^{\infty}\frac{k}{2^{k}}T=2T$, where $T$ is the running time of
each attempt. Thus, the expected running time is polynomially bounded. ∎

A _Pfaffian pair_ is a pair of $r\times n$ matrices $A_{1},A_{2}$ such that
$\det(A_{1}[B])\det(A_{2}[B])$ is a non-zero constant for any common basis $B$
[69]. This property implies that, if $\mathbb{F}=\mathbb{Q}$ and matroids are
given as a Pfaffian pair, then no cancel-out occurs in the summands of
$\det(\Xi)$ in the equation (1) even if we substitute $1$ for all $x_{i}$.
Therefore, we can derandomize the algorithm given in Theorem 4.3. Examples of
common bases of matroid pairs representable by Pfaffian pairs include spanning
trees, regular matroid bases, arborescences, perfect matchings in Pfaffian-
orientable bipartite graphs, and node-disjoint $S$–$T$ paths in planar graphs
[51].

######  Theorem 4.4.

$F$-avoiding Common Basis is polynomially solvable for
$\mathbb{Q}$-representable matroids if matroids are given as a Pfaffian pair
and a group is given as the operation table.

We can also generalize Theorem 4.3 to a randomized pseudo-polynomial-time
algorithm for the weighted problem as follows.

######  Theorem 4.5.

Let $\mathbb{F}$ be a field and $M_{1}$ and $M_{2}$ $\mathbb{F}$-representable
matroids on a common ground set $E$. There is a randomized algorithm that,
given matrices $A_{1}$ and $A_{2}$ over $\mathbb{F}$ representing $M_{1}$ and
$M_{2}$, respectively, the operation table of a finite abelian group $\Gamma$,
a group labeling $\psi\colon E\to\Gamma$, a forbidden label set
$F\subseteq\Gamma$, and a weight function $w\colon E\to\mathbb{Z}$, solves
Weighted $F$-avoiding Common Basis in pseudo-polynomial time in expectation.
If $\mathbb{F}=\mathbb{Q}$ and $(A_{1},A_{2})$ is a Pfaffian pair, the
algorithm can be derandomized.

###### Proof.

We modify each $(j,j)$ diagonal entry of $D_{\psi}$ as
$x_{j}\psi(j)\theta^{w(j)}$, where $\theta$ is an additional indeterminate.
Then, by the same argument as Lemma 4.2, the degree of the coefficient of $e$
in $\det(\Xi)$ with respect to $\theta$ is the maximum weight of an
$F$-avoiding common basis; see also [51, Proposition 2.5]. Therefore, via
random substitution, division-free determinant computation, and search-to-
decision reduction, we obtain a randomized pseudo-polynomial-time algorithm,
as given in the proof of Theorem 4.3. ∎

##  5 $F$-avoiding Basis with Fixed $|F|$

As we will see in Theorem 6.7, Zero Basis is hard for groups given by
operation tables. This implies the hardness of $F$-avoiding Basis if the set
$F$ of forbidden labels is part of the input. In this section, we study the
problem when $F$ has fixed size. Note that in contrast to the setting of
Section 4, we assume that $\Gamma$ is given as an operation oracle (and it is
not necessarily finite).

Related to the notion of $k$-closeness recently introduced by Liu and Xu [46],
we propose the following conjecture.

######  Conjecture 5.1.

Let $M$ be a matroid, $\psi\colon E(M)\to\Gamma$ a labeling, and
$F\subseteq\Gamma$ a finite collection of forbidden labels. Then, for any
basis $B$, there exists an $F$-avoiding basis $B^{*}$ with $|B\setminus
B^{*}|\leq|F|$, provided that at least one $F$-avoiding basis exists.

Note that Theorem 3.1 implies that 5.1 holds for $|F|=1$.

If 5.1 is true, then it is tight in the sense that for each $k\geq 1$ there
exists a group-labeled matroid and a set $F$ of $k$ forbidden labels such that
there exists an $F$-avoiding basis but $|B\setminus B^{*}|\geq k$ holds for
some basis $B$ and any $F$-avoiding basis $B^{*}$. Indeed, consider the
rank-$k$ uniform matroid on ground set $E=\\{e_{1},\dots,e_{2k}\\}$, the
labeling $\psi\colon E\to\mathbb{Z}_{k+1}$ given by $\psi(e_{i})=0$ for
$i\in[k]$ and $\psi(e_{i})=1$ for $i\in[2k]\setminus[k]$, and forbidden label
set $F=\mathbb{Z}_{k+1}\setminus\\{0\\}$. Then, the only $F$-avoiding basis is
$B^{*}=\\{e_{1},\dots,e_{k}\\}$ and we have $|B\setminus B^{*}|$ for the basis
$B=\\{e_{k+1},\dots,e_{2k}\\}$.

We can relax 5.1 as follows.

######  Conjecture 5.2.

There exists a function $f\colon\mathbb{N}\to\mathbb{N}$ with the following
property: If $M$ is a matroid, $\psi\colon E(M)\to\Gamma$ is a group labeling,
and $F\subseteq\Gamma$ is a finite collection of forbidden labels, then, for
any basis $B$, there exists an $F$-avoiding basis $B^{*}$ with $|B\setminus
B^{*}|\leq f(|F|)$, provided that at least one $F$-avoiding basis exists.

Conjectures 5.1 and 5.2 have algorithmic implications due to the following
simple observation.

######  Lemma 5.3.

Let $\alpha$ be a fixed positive integer. Further, let $M$ be a matroid,
$\psi\colon E(M)\to\Gamma$ a group labeling, and $F\subseteq\Gamma$ a finite
collection of forbidden labels, such that, for any basis $B$, there exists an
$F$-avoiding basis $B^{*}$ with $|B\setminus B^{*}|\leq\alpha$, provided that
at least one $F$-avoiding basis exists. Then, an $F$-avoiding basis of $M$ can
be found in polynomial time, if one exists.

###### Proof.

We first compute an arbitrary basis $B$ of $M$. Then, for every $X\subseteq B$
and every $Y\subseteq E(M)\setminus B$ with $|X|=|Y|\leq\alpha$, we test
whether $(B\setminus X)\cup Y$ is an $F$-avoiding basis of $M$. As there are
at most $\alpha n^{\alpha}$ choices for each of $X$ and $Y$, the desired
running time follows. If we find an $F$-avoiding basis during this procedure,
we return it. Otherwise, no $F$-avoiding basis exists by assumption. ∎

The following is an immediate consequence of Lemma 5.3.

######  Corollary 5.4.

If 5.2 holds, then $F$-avoiding Basis is solvable in polynomial time if $|F|$
is fixed.

Liu and Xu [46] defined a finite group $\Gamma$ to be _$k$ -close_ for an
integer $k\geq 1$, if for any matroid $M$, group labeling $\psi\colon
E(M)\to\Gamma$, element $g\in\Gamma$ and basis $B$, there exists a basis
$B^{*}$ with $|B\setminus B^{*}|\leq k$ and $\psi(B^{*})=g$, provided that $M$
has at least one basis with label $g$. Observe that 5.1 would imply
$(|\Gamma|-1)$-closeness, and 5.2 would imply $f(|\Gamma|-1)$-closeness of
each finite group $\Gamma$ for some function $f\colon\mathbb{N}\to\mathbb{N}$.
This would imply an FPT algorithm for Zero Basis when parameterized with
$|\Gamma|$ due to the following result which is a consequence of [46, Theorem
1].

######  Theorem 5.5 (see Liu–Xu [46]).

Assume that for each finite group $\Gamma$, there exists an integer $k$ such
that $\Gamma$ is $k$-close. Then, Zero Basis is FPT for finite groups when
parameterized by $|\Gamma|$.

Liu and Xu [46] observed that if all subgroups of $\Gamma$ satisfy a
conjecture by Schrijver and Seymour [63], then $\Gamma$ is
$(|\Gamma|-1)$-close. By the results of DeVos, Goddyn, and Mohar [16], this
implies that any cyclic group $\Gamma$ is $(|\Gamma|-1)$-close whose order is
a prime power or the product of two primes. The proof of [46, Theorem 4] does
not seem to generalize to our setting, thus, it is not clear whether the
conjecture of Schrijver and Seymour implies 5.1. If $\Gamma$ has prime order,
then Liu and Xu [46, Theorem 3] gave a simpler proof of
$(|\Gamma|-1)$-closeness. That proof also generalizes to show that 5.1 holds
for such groups.

Using results of Lemos [45], we can also prove that 5.1 holds for ordered
groups. The result is restated in the following theorem.

######  Theorem 5.6.

Let $M$ be a matroid, $\psi\colon E(M)\to\Gamma$ a labeling to an ordered
group $\Gamma$, $F\subseteq\Gamma$ a finite collection of forbidden labels,
$B$ a basis of $M$, and suppose that $M$ has an $F$-avoiding basis. Then,
there exists an $F$-avoiding basis $B^{*}$ of $M$ with $|B^{*}\setminus
B|\leq|F|.$

To prove the theorem, we will rely on the following results due to Lemos [45].

######  Theorem 5.7 (Lemos [45]).

Let $M$ be a matroid and $\psi\colon E(M)\to\Gamma$ a labeling, where $\Gamma$
is an ordered group.

  1. (a)

If $B$ and $B^{\prime}$ are bases such that $\psi(B^{\prime})<\psi(B)$, then
there exist elements $e\in B\setminus B^{\prime}$ and $f\in
B^{\prime}\setminus B$ such that $B-e+f$ is a basis with
$\psi(B-e+f)<\psi(B)$.

  2. (b)

Let $g_{0},\ldots,g_{m}$ be the unique ordering of
$\\{\,\psi(B)\mathclose{}\nonscript\;|\nonscript\;\mathopen{}B\text{ is a
basis of $M$}\,\\}$ such that $g_{0}<\dots<g_{m}$, and let $B_{0}$ be a basis
with $\psi(B_{0})=g_{0}$. Then, for any $k\in\\{0,\dots,m\\}$, there exists a
basis $B_{k}$ such that $\psi(B_{k})=g_{k}$ and $|B_{0}\setminus B_{k}|\leq
k$.

Note that while Lemos only considered the case $\Gamma=\mathbb{R}$, the same
proofs work for any ordered group $\Gamma$. We remark that statement (a)
follows from Lemma 2.1. Motivated by results of Kawamoto, Kajitani, and
Shinoda [37], Kano [36] stated four conjectures on spanning trees whose weight
is $k$-th largest among the weights of spanning trees. The first of these
conjectures was verified by Mayr and Plaxton [53], and statement (b) is its
extension to matroids by Lemos [45]. We show that Theorem 5.7 implies 5.1 for
ordered groups.

We first prove the following preliminary result as a conclusion from Theorem
5.7(a).

######  Proposition 5.8.

Let $M$ be a matroid, $\psi\colon E(M)\to\Gamma$ a labeling to an ordered
group $\Gamma$, and let $B$ be a basis of $M$. Then, there exists a sequence
$(B_{0},\ldots,B_{\ell})$ of bases of $M$ such that $B_{0}=B$, $B_{\ell}$ is a
minimum-label basis of $M$, and $\psi(B_{i})<\psi(B_{i-1})$ and
$|B_{i}\setminus B_{i-1}|=1$ hold for all $i\in[\ell]$.

###### Proof.

Suppose for contradiction that the desired sequence does not exist and that
$B$ is chosen so that $\psi(B)$ is minimum among all bases for which the
desired sequence does not exist. Let $B^{-}$ be a minimum-label basis. By
Theorem 5.7(a) applied to $B$ and $B^{-}$, there exists a basis $B^{\prime}$
with $\psi(B^{\prime})<\psi(B)$ and $|B\setminus B^{\prime}|=1$. Hence, by the
choice of $B$, we obtain that there exists a sequence
$(B_{0},\ldots,B_{\ell})$ of bases such that $B_{0}=B^{\prime}$, $B_{\ell}$ is
a minimum-label basis, and $\psi(B_{i})<\psi(B_{i-1})$ and $|B_{i}\setminus
B_{i-1}|=1$ hold for all $i\in[\ell]$. It follows that
$(B,B_{0},\ldots,B_{\ell})$ is a sequence with the desired properties, a
contradiction. ∎

We are now ready to prove that 5.1 holds when $\Gamma$ is an ordered group.

###### Proof of Theorem 5.6.

Let $g_{0},\ldots,g_{m}$ be the unique ordering of
$\\{\,\psi(B)\mathclose{}\nonscript\;|\nonscript\;\mathopen{}B\text{ is a
basis}\,\\}$ such that $g_{0}<\dots<g_{m}$.

######  Claim 5.9.

There exists a sequence $(B_{0},\ldots,B_{\ell})$ of bases with the following
properties: $g_{m}=\psi(B_{\ell})<\psi(B_{1})<\dots<\psi(B_{\ell})=g_{0}$,
$|B_{i}\setminus B_{i-1}|=1$ for all $i\in[\ell]$, and there exists some
$i_{0}\in\\{0,\ldots,\ell\\}$ with $B_{i_{0}}=B$.

###### Proof.

By Proposition 5.8, there exists a sequence
$(B^{\prime}_{0},\ldots,B^{\prime}_{\ell^{\prime}})$ of bases of $M$ such that
$B^{\prime}_{0}=B$, $\psi(B^{\prime}_{\ell^{\prime}})=g_{0}$, and
$\psi(B^{\prime}_{i})<\psi(B^{\prime}_{i-1})$ and $|B^{\prime}_{i}\setminus
B^{\prime}_{i-1}|=1$ hold for all $i\in[\ell^{\prime}]$. We now apply
Proposition 5.8 to $B$ and $-\psi$. We obtain that there exists a sequence
$(B^{\prime\prime}_{0},\ldots,B^{\prime\prime}_{\ell^{\prime\prime}})$ of
bases such that $B^{\prime\prime}_{0}=B$,
$\psi(B^{\prime\prime}_{\ell^{\prime\prime}})=g_{m}$, and
$\psi(B^{\prime\prime}_{i})>\psi(B^{\prime\prime}_{i-1})$ and
$|B^{\prime\prime}_{i}\setminus B^{\prime\prime}_{i-1}|=1$ hold for all
$i\in[\ell^{\prime\prime}]$. We obtain that
$(B^{\prime\prime}_{\ell^{\prime\prime}},\ldots,B^{\prime\prime}_{1},B,B^{\prime}_{1},\ldots,B^{\prime}_{\ell^{\prime}})$
is a sequence with the desired properties. ∎

Let $(B_{0},\dots,B_{\ell})$ be the sequence and $i_{0}$ the index provided by
5.9. We finish the proof through a distinction of two cases.

######  Case 5.10.

There exists some $i_{1}\in\\{0,\ldots,\ell\\}$ with $\psi(B_{i_{1}})\notin
F$.

We may suppose that $i_{1}$ is chosen with this property so that
$|i_{1}-i_{0}|$ is minimum. Further, by, symmetry, we may suppose that
$i_{1}>i_{0}$. As
$\\{\psi(B_{i_{0}}),\psi(B_{i_{0}+1}),\ldots,\psi(B_{i_{1}-1})\\}\subseteq F$
and $\psi(B_{j})\neq\psi(B_{j^{\prime}})$ for all distinct
$j,j^{\prime}\in\\{i_{0},\ldots,i_{1}-1\\}$, we obtain $i_{1}-i_{0}\leq|F|$.
It follows that $|B\setminus
B_{i_{1}}|\leq\sum_{i=i_{0}+1}^{i_{1}}|B_{i}\setminus
B_{i-1}|=i_{1}-i_{0}\leq|F|$. As $\psi(B_{i_{1}})\notin F$, the statement
follows.

######  Case 5.11.

$\psi(B_{i})\in F$ holds for all $i\in\\{0,\ldots,\ell\\}$.

As $\psi(B_{i})\neq\psi(B_{j})$ for all distinct $i,j\in\\{0,\ldots,\ell\\}$,
we have $\ell\leq|F|$. Let $p$ be the smallest integer such that $g_{p}\notin
F$ and $q$ be the smallest integer such that $g_{m-q}\notin F$. Observe that
$p$ and $q$ are well-defined as $M$ has an $F$-avoiding basis. As
$\\{g_{0},\ldots,g_{p-1}\\}\cup\\{g_{m-q+1},\ldots,g_{m}\\}\subseteq F$ and
$\\{g_{0},\ldots,g_{p-1}\\}$ and $\\{g_{m-q+1},\ldots,g_{m}\\}$ are disjoint,
we obtain $p+q\leq|F|$. Next, by Theorem 5.7(b), there exists a basis $B^{-}$
with $\psi(B^{-})=g_{p}$ and $|B_{\ell}\setminus B^{-}|\leq p$. Further,
applying Theorem 5.7(b) to $B_{\ell}$ and $-\psi$, we obtain that there exists
a basis $B^{+}$ of $M$ with $\psi(B^{+})=g_{m-q}$ and $|B_{0}\setminus
B^{+}|\leq q$. If $|B\setminus B^{-}|>|F|$ and $|B\setminus B^{+}|>|F|$ hold,
we obtain

$\displaystyle 2|F|$ $\displaystyle<|B\setminus B^{-}|+|B\setminus B^{+}|$
$\displaystyle\leq|B\setminus B_{\ell}|+|B_{\ell}\setminus B^{-}|+|B\setminus
B_{0}|+|B_{0}\setminus B^{+}|$ $\displaystyle\leq(\ell-i_{0})+p+i_{0}+q$
$\displaystyle=p+q+\ell$ $\displaystyle\leq 2|F|,$

a contradiction. We hence obtain that one of $|B\setminus B^{-}|\leq|F|$ and
$|B\setminus B^{+}|\leq|F|$ holds. As $\psi(B^{-})\notin F$ and
$\psi(B^{+})\notin F$ hold, the statement follows. ∎

###  5.1 Strongly Base Orderable Matroids and Relaxations

In this section, we introduce a relaxed notion of strong base-orderability,
called $(\alpha,k)$-weak base orderability, where $\alpha$ and $k$ are
positive integers. In Section 5.1.1, we define this notion and show its
relation to strong base-orderability and group-restricted bases. In Section
5.1.2 and Section 5.1.4, we conclude results for matroids representable over
fixed finite fields and graphic matroids, respectively.

####  5.1.1 $(\alpha,k)$-Weakly Base Orderable Matroids

A matroid is called _strongly base orderable_ if for any two bases
$B_{1},B_{2}$, there exists a bijection $\varphi\colon B_{1}\setminus B_{2}\to
B_{2}\setminus B_{1}$ such that $(B_{1}\setminus Z)\cup\varphi(Z)$ is a basis
for each $Z\subseteq B_{1}\setminus B_{2}$. For some positive integer $k$, we
say that the ordered basis pair $(B_{1},B_{2})$ has the $k$-exchange property
if there exist pairwise disjoint nonempty subsets $X_{1},\dots,X_{k}\subseteq
B_{1}\setminus B_{2}$ and $Y_{1},\dots,Y_{k}\subseteq B_{2}\setminus B_{1}$
such that $\left(B_{1}\setminus\bigcup_{i\in Z}X_{i}\right)\cup\bigcup_{i\in
Z}Y_{i}$ is a basis for each $Z\subseteq[k]$. For positive integers $\alpha$
and $k$, we define a matroid $M$ to be _weakly $(\alpha,k)$-base orderable_ if
the ordered pair $(B_{1},B_{2})$ has the $k$-exchange property for any two
bases $B_{1},B_{2}$ of $M$ with $|B_{1}\setminus B_{2}|\geq\alpha$. We note
that $(\alpha,k)$-weakly base orderability is a relaxation of _$k$ -base
orderability_ defined by Bonin and Savitsky [7], and our definition of the
$k$-exchange property differs from their definition of $k$-exchange-ordering.
Observe that strongly base orderable matroids are precisely the matroids that
are $(k,k)$-weakly base orderable for each $k\geq 1$.

For a matroid $M$ and two disjoint bases $B_{1},B_{2}$ of $M$ with $B_{1}\cup
B_{2}=E(M)$, we say that $(B_{1},B_{2})$ is a _basis partition_ of $M$. For a
basis $B$ of a matroid $M$, we say that a minor $M^{\prime}$ of $M$ is a
$B$-minor if it is obtained by contracting some elements of $B$ and deleting
some elements of $E(M)\setminus B$. We use the following simple observation
later.

######  Lemma 5.12.

Let $B_{1}$ and $B_{2}$ be two bases of a matroid $M$. Further, let
$M^{\prime}$ be a $B_{1}$-minor of $M$ such that
$(B_{1}^{\prime},B_{2}^{\prime})$ is a basis partition of $M^{\prime}$ and has
the $k$-exchange property for some $k\in\mathbb{N}$, where
$B_{i}^{\prime}\coloneqq B_{i}\cap E(M^{\prime})$ for $i=1,2$. Then,
$(B_{1},B_{2})$ has the $k$-exchange property in $M$.

###### Proof.

As $(B_{1}^{\prime},B_{2}^{\prime})$ has the $k$-exchange property in
$M^{\prime}$, there exist pairwise disjoint nonempty subsets
$X_{1},\dots,X_{k}\subseteq B^{\prime}_{1}$ and $Y_{1},\dots,Y_{k}\subseteq
B^{\prime}_{2}$ such that $\left(B_{1}^{\prime}\setminus\bigcup_{i\in
Z}X_{i}\right)\cup\bigcup_{i\in Z}Y_{i}$ is a basis for each $Z\subseteq[k]$.
For $Z\subseteq[k]$, let $B_{Z}\coloneqq\left(B_{1}\setminus\bigcup_{i\in
Z}X_{i}\right)\cup\bigcup_{i\in Z}Y_{i}$ and
$B^{\prime}_{Z}\coloneqq\left(B_{1}^{\prime}\setminus\bigcup_{i\in
Z}X_{i}\right)\cup\bigcup_{i\in Z}Y_{i}$. As $B_{1}^{\prime}\subseteq
B_{1}\setminus B_{2}$ and $B_{2}^{\prime}\subseteq B_{2}\setminus B_{1}$, it
suffices to prove that $B_{Z}$ is a basis of $M$ for every $Z\subseteq[k]$.
This follows from $B^{\prime}_{Z}$ being a basis of $M^{\prime}$ using that
$B_{Z}=B^{\prime}_{Z}\cup(B_{1}\setminus B^{\prime}_{1})$ and $M^{\prime}$ is
obtained from $M$ by contracting $B_{1}\setminus B^{\prime}_{1}$ and deleting
a subset of $E(M)\setminus B_{1}$. ∎

The following result is our main motivation to consider weak base
orderability. It establishes a connection between weak base orderability and
5.2.

######  Theorem 5.13.

Let $M$ be a matroid, $\psi\colon E(M)\to\Gamma$ a group labeling, and
$F\subseteq\Gamma$ a finite collection of forbidden labels. If $M$ is
$(\alpha,|F|+1)$-weakly base orderable, then for each basis $B$, there exists
an $F$-avoiding basis $B^{*}$ with $|B\setminus B^{*}|\leq\alpha-1$, provided
that at least one $F$-avoiding basis exists.

For the proof, we need the following result which is most likely routine.

######  Proposition 5.14.

Let $S$ be a finite set, $\psi\colon S\to\Gamma$ a group labeling, and
$0\notin F\subseteq\Gamma$ satisfying $|F|\leq|S|-1$. Then, there exists some
nonempty $S^{\prime}\subseteq S$ with $\psi(S^{\prime})\notin F$.

###### Proof.

Let $k\coloneqq|S|-1$ and let $s_{1},\ldots,s_{k+1}$ be an arbitrary ordering
of $S$. If $\psi(\\{s_{1},\ldots,s_{i}\\})=\psi(\\{s_{1},\ldots,s_{j}\\})$ for
some $1\leq i<j\leq k+1$, then $\psi(\\{s_{i+1},\ldots,s_{j}\\})=0\notin F$.
Otherwise, $\\{\psi(s_{1}),\psi(\\{s_{1},s_{2}\\}),\ldots,\psi(S)\\}$ contains
$k+1$ distinct values, hence at least one of them is not in $F$. ∎

###### Proof of Theorem 5.13.

Let $k\coloneqq|F|$ and let $B$ be a basis and $B^{\prime}$ an $F$-avoiding
basis minimizing $|B^{\prime}\setminus B|$. If $|B^{\prime}\setminus
B|\leq\alpha-1$, there is nothing to prove. We may hence suppose that
$|B^{\prime}\setminus B|\geq\alpha$. Then, as $M$ is $(\alpha,k+1)$-weakly
base orderable, there exist pairwise disjoint nonempty subsets
$X_{1},\dots,X_{k+1}\subseteq B^{\prime}\setminus B$ and
$Y_{1},\dots,Y_{k+1}\subseteq B\setminus B^{\prime}$ such that
$\left(B^{\prime}\setminus\bigcup_{i\in Z}X_{i}\right)\cup\bigcup_{i\in
Z}Y_{i}$ is a basis for each $Z\subseteq[k+1]$. We define
$\psi^{\prime}\colon[k+1]\rightarrow\Gamma$ by
$\psi^{\prime}(i)=\psi(Y_{i})-\psi(X_{i})$ for all $i\in[k+1]$. Observe that
$0\notin
F^{\prime}\coloneqq\\{\,f-\psi(B^{\prime})\mathclose{}\nonscript\;|\nonscript\;\mathopen{}f\in
F\,\\}$, as $B^{\prime}$ is an $F$-avoiding basis. It hence follows from
Proposition 5.14 that there exists some nonempty $Z\subseteq[k+1]$ with
$\psi^{\prime}(Z)\notin F^{\prime}$. Let
$B^{\prime\prime}\coloneqq\left(B^{\prime}\setminus\bigcup_{i\in
Z}X_{i}\right)\cup\bigcup_{i\in Z}Y_{i}$. By the definition of
$X_{1},\dots,X_{k+1}$ and $Y_{1},\dots,Y_{k+1}$, we obtain that
$B^{\prime\prime}$ is a basis of $M$. Further, we have
$\psi(B^{\prime\prime})=\psi(B^{\prime})+\psi^{\prime}(Z)\notin F$. Finally,
we have $|B^{\prime\prime}\setminus B|<|B^{\prime}\setminus B|$ since $Z$ is
nonempty. This contradicts the choice of $B^{\prime}$. ∎

As strongly base orderable matroids are $(k,k)$-weakly base orderable for any
$k\geq 1$, we also get the following.

######  Corollary 5.15.

Strongly base orderable matroids satisfy 5.1.

######  Remark 5.16.

Note that the proofs of Theorem 5.13 and Proposition 5.14 also show that 5.1
holds for a matroid $M$ if for any two bases $B,B^{\prime}$ of $M$ there exist
an ordering $b_{1},\dots,b_{r}$ of $B$ and an ordering
$b^{\prime}_{1},\dots,b^{\prime}_{r}$ of $B^{\prime}$ such that
$\\{b_{1},\dots,b_{i},b^{\prime}_{i+1},\dots,b^{\prime}_{j},b_{j+1},\dots,b_{r}\\}$
is a basis of $M$ for any $0\leq i\leq j\leq r$. Baumgart [4] called such an
ordering a _subsequence-interchangeable base ordering_ (SIBO for short), and
conjectured that any basis pair of a graphic matroid has a SIBO. Baumgart
showed that the conjecture holds for a pair of disjoint spanning trees of a
wheel graph. We are not aware of any basis pair of a matroid not having a
SIBO. However, the existence of an SIBO for any basis pair of a matroid would
imply a long-standing conjecture of Gabow [27] on the serial symmetric
exchange property of matroids.

####  5.1.2 Matroids Representable over Finite Fields

In this section, we prove that the concept of weakly base orderability allows
us to deal with a large class of matroids, namely all those which are
representable over a fixed finite field. More precisely, we prove the
following result.

######  Theorem 5.17.

There is a function $f\colon\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$
such that for every prime power $q$, every $\mathrm{GF}(q)$-representable
matroid is weakly $(f(q,k),k)$-orderable for any positive integer $k$.

On a high level, the proof works in the following way. First, relying on
results of [18] on the existence of certain submatrices of large matrices over
finite fields, we show that every $\mathrm{GF}(q)$-representable matroid has a
certain substructure. We then show that this substructure has the desired
property. From this, we can conclude the theorem.

In order to find this substructure, we deal with the matrices representing the
matroids in consideration. We first need some notation for these matrices. For
two matrices $A$ and $A^{\prime}$, we say that $A$ contains $A^{\prime}$ as a
permuted submatrix if $A^{\prime}$ can be obtained from $A$ by deleting and
permuting rows and columns. For a square matrix, we refer by its _size_ to its
number of rows. Let $q$ be a prime power. We say that a triple
$(\alpha,\beta,\gamma)$ of elements of $\mathrm{GF}(q)$ is feasible if
$\alpha\neq\beta$ and at least one of $\beta\neq 0$ and $\gamma\neq 0$ hold.
For a triple $(\alpha,\beta,\gamma)$ and a positive integer $t$, the
_$(\alpha,\beta,\gamma)$ -diagonal matrix_ of size $t$ is the $t\times t$
matrix $A=(A_{ij})$ such that

$A_{ij}=\begin{cases}\alpha&\text{if $i<j$,}\\\ \beta&\text{if $i=j$,}\\\
\gamma&\text{if $i>j$}\end{cases}$

for $i,j\in[t]$. We now collect some properties of
$(\alpha,\beta,\gamma)$-diagonal matrices. We first need the following result
due to Ding, Oporowski, Oxley, and Vertigan [18] showing that
$(\alpha,\beta,\gamma)$-diagonal matrices can always be found in sufficiently
large matrices over a fixed finite field.

######  Theorem 5.18 (Ding–Oporowski–Oxley–Vertigan [18, Theorem 2.3]).

There is a computable function
$f_{0}\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ with the following
property: Let $q$ be a prime power, $t$ a positive integer and $A$ a matrix
over $\mathrm{GF}(q)$ having at least $f_{0}(q,t)$ columns no two of which are
identical. Then, $A$ contains a permuted square submatrix $A^{\prime}$ of size
$t$ which is $(\alpha,\beta,\gamma)$-diagonal for a triple
$(\alpha,\beta,\gamma)$ with $\alpha\neq\beta$.

We actually need a slight strengthening of Theorem 5.18 which follows easily.

######  Proposition 5.19.

There is a computable function
$f_{1}\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ with the following
property: Let $q$ be a prime power, $t$ a positive integer and $A$ a matrix
over $\mathrm{GF}(q)$ having at least $f_{1}(q,t)$ columns no two of which are
identical. Then, $A$ contains a permuted square submatrix $A^{\prime}$ of size
$t$ which is $(\alpha,\beta,\gamma)$-diagonal for a feasible triple
$(\alpha,\beta,\gamma)$.

###### Proof.

Let $f_{0}$ be the function provided by Theorem 5.18. We prove the statement
for the function $f_{1}$ defined by $f_{1}(q,t)\coloneqq f_{0}(q,t+1)$ for
each $t\in\mathbb{N}$ and prime power $q$. Let $A$ be a matrix over
$\mathrm{GF}(q)$ having at least $f_{1}(q,t)$ columns no two of which are
identical. By Theorem 5.18, we obtain that $A$ has a permuted square submatrix
$A^{\prime}$ of size $t+1$ which is $(\alpha,\beta,\gamma)$-diagonal for some
triple $(\alpha,\beta,\gamma)$ with $\alpha\neq\beta$. If $\beta\neq 0$ or
$\gamma\neq 0$ holds, observe that $(\alpha,\beta,\gamma)$ is feasible. As the
submatrix of $A^{\prime}$ obtained by deleting the first row and the first
column is an $(\alpha,\beta,\gamma)$-diagonal matrix of size $t$, the
statement follows. We may hence suppose that $\beta=\gamma=0$. We obtain by
assumption that $\alpha\neq 0$. Let $A^{\prime\prime}$ be obtained from
$A^{\prime}$ by deleting the first column and the last row and then reversing
the order of the rows and the columns. Then, $A^{\prime\prime}$ is a permuted
submatrix of $A^{\prime}$ and hence $A$. Further, $A^{\prime\prime}$ is an
$(0,\alpha,\alpha)$-diagonal matrix of size $t$. As $\alpha\neq 0$, we obtain
that $(0,\alpha,\alpha)$ is feasible. Hence the statement follows. ∎

We are now ready to give the following result showing that every sufficiently
large matroid that is representable over a fixed finite field has a certain
substructure. The approach is to choose a matrix representing the matroid and
find a particular submatrix in this matroid using Proposition 5.19. After, we
show that a minor represented by this matrix can be obtained by applying
certain deletions and contractions.

######  Lemma 5.20.

There is a computable function
$f_{1}\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ with the following
properties: Let $q$ be a prime power, $k$ a positive integer, $M$ a
$\mathrm{GF}(q)$-representable matroid of rank at least $f_{1}(q,k)$ and
$(B_{1},B_{2})$ a basis partition of $M$. Then, there exists a $B_{1}$-minor
$M^{\prime}$ of $M$ that can be represented by a matrix of the form
$[I_{k}~{}A]$, where $I_{k}$ is the identity matrix of size $k$ and $A$ is an
$(\alpha,\beta,\gamma)$-diagonal matrix for a feasible triple
$(\alpha,\beta,\gamma)$, and the columns of $I_{k}$ correspond to the elements
of $B_{1}^{\prime}$ and those of $A$ correspond to the elements of
$B_{2}^{\prime}$, where $B_{i}^{\prime}\coloneqq B_{i}\cap E(M^{\prime})$ for
$i=1,2$.

###### Proof.

Let $f_{1}$ be the function provided by Proposition 5.19. As $(B_{1},B_{2})$
is a basis partition of $M$ and $M$ is $\mathrm{GF}(q)$-representable, we
obtain that $M$ can be represented by a matrix of the form $[I~{}A_{0}]$ over
$\mathrm{GF}(q)$, where $I$ is an identity matrix of size at least
$f_{1}(q,k)$, $A_{0}$ is a nonsingular matrix of the same size, and the
columns of $I$ correspond to $B_{1}$ and the columns of $A_{0}$ correspond to
$B_{2}$. As $A_{0}$ is nonsingular, in particular, it does not contain two
identical columns. It now follows from Proposition 5.19 that there exists a
permuted submatrix $A$ of $A_{0}$ which is an $(\alpha,\beta,\gamma)$-diagonal
matrix of size $k$ for a feasible triple $(\alpha,\beta,\gamma)$. Let
$X\subseteq B_{1}$ be the set of elements of $B_{1}$ whose corresponding
columns only contain 0’s in all rows which contribute to $A$ and let
$Y\subseteq B_{2}$ be the set of elements of $B_{2}$ whose corresponding
columns do not contribute to $A$. Let $M^{\prime}\coloneqq M/X\backslash Y$.
First observe that $M^{\prime}$ is a $B_{1}$-minor of $M$. For $i\in 1,2$, let
$B_{i}^{\prime}\coloneqq B_{i}\cap E(M^{\prime})$. Finally, observe that
$M^{\prime}$ is represented by $[I_{k}~{}A]$ where the columns of $I_{k}$
correspond to the elements of $B_{1}^{\prime}$ and the columns of $A$
correspond to the elements of $B_{2}^{\prime}$ if an appropriate labeling of
the columns is chosen. ∎

We will prove Theorem 5.17 by showing that matroids representable by a very
specific class of matrices satisfy its conclusion. For this, we need a
statement showing that certain matrices are nonsingular, which we derive from
an explicit formula for the determinants of $(\alpha,\beta,\gamma)$-triangular
matrices due to Efimov [21].

######  Lemma 5.21 (Efimov [21]).

Let $q$ be a prime power, $\alpha,\beta,\gamma\in\mathrm{GF}(q)$, and let $A$
denote the $(\alpha,\beta,\gamma)$-diagonal matrix of size $t$. Then,

$\det(A)=\begin{cases}\frac{\alpha{(\beta-\gamma)}^{t}-\gamma{(\beta-\alpha)}^{t}}{\alpha-\gamma}&\text{if
$\alpha\neq\gamma$,}\\\
{(\beta-\alpha)}^{t-1}((t-1)\cdot\alpha+\beta)&\text{if
$\alpha=\gamma$,}\end{cases}$

where in the last expression $(t-1)\cdot\alpha$ is shorthand for
$\alpha+\dotsb+\alpha$ ($t-1$ times).

######  Proposition 5.22.

Let $q$ be a prime power, $(\alpha,\beta,\gamma)$ a feasible triple, $t$ a
multiple of $q(q-1)$, and $A$ the $(\alpha,\beta,\gamma)$-diagonal matrix of
size $t$. Then, $A$ is nonsingular.

###### Proof.

As $(\alpha,\beta,\gamma)$ is feasible, $\alpha\neq\beta$ holds. First suppose
that $\alpha\neq\gamma$. If $\beta=\gamma$, we obtain $\beta=\gamma\neq 0$ by
the feasibility of $(\alpha,\beta,\gamma)$, hence
$\det(A)=\frac{-\gamma{(\beta-\alpha)}^{t}}{\alpha-\gamma}\neq 0$. Otherwise,
if $\beta\neq\gamma$, then using that $t$ is divisible by $q-1$, we obtain

$\displaystyle\det(A)=\frac{\alpha{(\beta-\gamma)}^{t}-\gamma{(\beta-\alpha)}^{t}}{\alpha-\gamma}=\frac{\alpha-\gamma}{\alpha-\gamma}\neq
0.$

Now suppose that $\alpha=\gamma$. As $\alpha\neq\beta$ and $t$ is divisible by
$q$, we obtain that

$\det(A)={(\beta-\alpha)}^{t-1}((t-1)\cdot\alpha+\beta)={(\beta-\alpha)}^{t}\neq
0.\qed$

We are now ready to conclude the result for the specific class of matroids.

######  Lemma 5.23.

There is a computable function
$f_{2}\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ with the following
properties: Let $q$ be a prime power, $k$ a positive integer, and $M$ a
matroid that can be represented by $[I~{}A]$ over $\mathrm{GF}(q)$, where $I$
is an identity matrix of size $f_{2}(q,k)$ and $A$ is an
$(\alpha,\beta,\gamma)$-diagonal matrix of the same size for a feasible triple
$(\alpha,\beta,\gamma)$. Next, let $B_{1}$ and $B_{2}$ be the subsets of
$E(M)$ corresponding to $I$ and $A$, respectively. Then, $(B_{1},B_{2})$ is a
basis partition of $M$ and has the $k$-exchange property.

###### Proof.

Let $f_{2}$ be the function defined by $f_{2}(q,k)\coloneqq q(q-1)k$ for all
positive integers $q$ and $k$. By Proposition 5.22, we have that $A$ is
nonsingular and hence $(B_{1},B_{2})$ is a basis partition of $M$. For
$i\in[k]$, let $X_{i}$ be the subset of $B_{1}$ and $Y_{i}$ be the subset of
$B_{2}$ that corresponds to the columns of indices $q(q-1)(i-1)+1$ to
$q(q-1)i$ of $I$ and $A$, respectively. For $Z\subseteq[k]$, let
$B_{Z}\coloneqq\left(B_{1}\setminus\bigcup_{i\in
Z}X_{i}\right)\cup\bigcup_{i\in Z}Y_{i}$. It suffices to prove that $B_{Z}$ is
a basis of $M$ for every $Z\subseteq[k]$. To this end, consider some fixed
$Z\subseteq[k]$. Observe that the matrix obtained from restricting $[I~{}A]$
to the columns corresponding to $B_{Z}$ can be transformed into a matrix of
the form $\begin{bmatrix}I^{\prime}&A_{1}\\\ O&A^{\prime}\end{bmatrix}$ by
exchanging rows and columns. Here, $I^{\prime}$ is the identity matrix of size
$q(q-1)(k-|Z|)$, $O$ is a zero matrix, $A^{\prime}$ is an
$(\alpha,\beta,\gamma)$-diagonal matrix of size $q(q-1)|Z|$, and $A_{1}$ is an
arbitrary matrix. As the size of $A^{\prime}$ is divisible by $q(q-1)$, we
obtain by Proposition 5.22 that $A^{\prime}$ is nonsingular. It follows that
$\begin{bmatrix}I^{\prime}&A_{1}\\\ O&A^{\prime}\end{bmatrix}$ is nonsingular
and hence $M\mathbin{|}B_{Z}$ is the free matroid. As $|B_{Z}|=|B_{1}|$ by
construction, we obtain that $B_{Z}$ is a basis of $M$. This finishes the
proof. ∎

Finally, we combine Lemmas 5.20, 5.23 and 5.12 to conclude Theorem 5.17.

###### Proof of Theorem 5.17.

We prove the statement for the function
$f\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ defined by $f(q,k)\coloneqq
f_{1}(f_{2}(q,k),k)$ for each $k\in\mathbb{N}$ and prime power $q$. Let
$B_{1}$ and $B_{2}$ be bases of a $\mathrm{GF}(q)$-representable matroid $M$
with $|B_{1}\setminus B_{2}|\geq f(q,k)$. We need to prove that
$(B_{1},B_{2})$ has the $k$-exchange property. Let $M^{\prime}\coloneqq
M\mathbin{/}(B_{1}\cap B_{2})\mathbin{\backslash}(E(M)\setminus(B_{1}\cup
B_{2}))$. Further, for $i=1,2$, let $B_{i}^{\prime}\coloneqq B_{i}\cap
E(M^{\prime})$ and observe that $(B_{1}^{\prime},B_{2}^{\prime})$ is a basis
partition of $M^{\prime}$. It follows from Lemma 5.20 that there exists a
$B_{1}^{\prime}$-minor $M^{\prime\prime}$ of $M^{\prime}$ that can be
represented by a matrix of the form $[I~{}A]$, where $I$ is the identity
matrix of size $f_{2}(q,k)$, $A$ is an $(\alpha,\beta,\gamma)$-diagonal matrix
of size $f_{2}(q,k)$ for a feasible triple $(\alpha,\beta,\gamma)$ and the
columns of $I$ and $A$ correspond to the elements of $B^{\prime\prime}_{1}$
and $B^{\prime\prime}_{2}$, respectively, where $B_{i}^{\prime\prime}\coloneqq
B_{i}^{\prime}\cap E(M^{\prime\prime})$ for $i=1,2$. We now obtain from Lemma
5.23 that $(B_{1}^{\prime\prime},B_{2}^{\prime\prime})$ is a basis partition
of $M^{\prime\prime}$ and has the $k$-exchange property in $M^{\prime\prime}$.
As $M^{\prime\prime}$ is a $B_{1}$-minor of $M$, we now obtain from Lemma 5.12
that $(B_{1},B_{2})$ has the $k$-exchange property in $M$. ∎

Combining Theorems 5.17 and 5.13, Lemma 5.3, and Theorem 5.5, we get the
following.

######  Corollary 5.24.

Let $q$ be a prime power, $M$ a $\mathrm{GF}(q)$-representable matroid,
$\psi\colon E\to\Gamma$ a group labeling and $F\subseteq\Gamma$ a finite set
of forbidden labels. When $|F|$ is fixed, then $F$-avoiding Basis is solvable
in polynomial time. Moreover, if $|\Gamma|$ is finite, then Zero Basis is FPT
when parameterized by $|\Gamma|$.

####  5.1.3 Binary and Regular Matroids

As a strengthening of the $k$-exchange property, we say that the basis pair
$(B_{1},B_{2})$ of a matroid has the _elementary $k$-exchange property_ if
there exist $k$-element subsets $X\subseteq B_{1}\setminus B_{2}$ and
$Y\subseteq B_{2}\setminus B_{1}$ and a bijection $\varphi\colon X\to Y$ such
that $(B_{1}\setminus Z)\cup\varphi(Z)$ is a basis for each $Z\subseteq X$.
Note that this is equivalent to requiring $|X_{i}|=|Y_{i}|=1$ for each
$i\in[k]$ in the definition of the $k$-exchange property. We define a matroid
$M$ to be _elementarily $(\alpha,k)$-weakly base orderable_ if $(B_{1},B_{2})$
has the elementary $k$-exchange property for any pair of basis $B_{1}$ and
$B_{2}$ with $|B_{1}\setminus B_{2}|\geq\alpha$.

It turns out that all regular matroids are elementarily $(f(k),k)$-weakly base
orderable for some large function $f\colon\mathbb{N}\to\mathbb{N}$, while the
same is not true for binary matroids. While these results do not have
immediate algorithmic applications, we believe that they are interesting in
their own respect.

The following result shows that the statement of Theorem 5.17 does not hold if
we require elementary $(f(k),k)$-weak base orderability instead of
$(f(k),k)$-weak base orderability, not even for binary matroids.

######  Theorem 5.25.

Let $r\geq 4$ be an even integer and let $M$ denote the binary matroid
represented by $[I_{r}~{}J_{r}-I_{r}]$ where $I_{r}$ is the identity matrix
and $J_{r}$ is the square all-one matrix of size $r$. Then, $M$ is not
elementarily $(r,3)$-weakly base orderable.

###### Proof.

Let $x_{1},\dots,x_{r}$ and $y_{1},\dots,y_{r}$ denote the elements of $E(M)$
corresponding to the first and last $r$ columns of $[I_{r}~{}J_{r}-I_{r}]$,
respectively. Let $B_{1}\coloneqq\\{x_{1},\dots,x_{r}\\}$ and
$B_{2}\coloneqq\\{y_{1},\dots,y_{r}\\}$. Since $r$ is even, both $B_{1}$ and
$B_{2}$ are bases of $M$. Assume that $M$ is elementarily $(r,3)$-weakly base
orderable, then there exist 3-element subsets $X\subseteq B_{1}$ and
$Y\subseteq B_{2}$ and a bijection $\varphi\colon X\to Y$ such that
$(B_{1}\setminus Z)\cup\varphi(Z)$ is a basis for each $Z\subseteq X$. We may
assume by symmetry that $X=\\{x_{1},x_{2},x_{3}\\}$. Since $(B_{1}\setminus
X)\cup\\{y_{1},y_{2},y_{3}\\}$ is not a basis, $Y\neq\\{y_{1},y_{2},y_{3}\\}$,
thus we may assume that $\varphi(x_{1})=y_{4}$. For $i\in\\{2,3\\}$,
$(B_{1}\setminus\\{x_{1},x_{i}\\})\cup\\{y_{4},\varphi(x_{i})\\}$ being a
basis implies that $\varphi(x_{i})\in\\{y_{1},y_{i}\\}$, while
$B_{1}-x_{i}+\varphi(y_{i})$ being a basis implies that $\varphi(x_{i})\neq
y_{i}$. This shows that $\varphi(y_{i})=y_{1}$ for $i\in\\{2,3\\}$, which is a
contradiction. ∎

By using that the binary matroid of $[I_{4}~{}J_{4}-I_{4}]$ is not regular, we
can show the following statement strenghtening of Theorem 5.17 holds for
regular matroids. The proof is a modification of that of Theorem 5.17.

######  Theorem 5.26.

There is a computable function $f^{\prime}\colon\mathbb{N}\to\mathbb{N}$ such
that every regular matroid is elementarily $(f^{\prime}(k),k)$-weakly base
orderable for any positive integer $k$.

###### Proof.

Let $f^{\prime}(k)\coloneqq f_{1}(2,\max\\{k,4\\})$ for $k\in\mathbb{N}$ where
$f_{1}$ is the function provided by Lemma 5.20. Let $B_{1}$ and $B_{2}$ be
bases of a regular matroid $M$ with $|B_{1}\setminus B_{2}|\geq
f^{\prime}(k)$, we need to show that $(B_{1},B_{2})$ has the elementary
$k$-exchange property. We may assume that $k\geq 4$. Let $M^{\prime}\coloneqq
M/(B_{1}\cap B_{2})\backslash(E(M)\setminus(B_{1}\cup B_{2}))$, and
$B^{\prime}_{i}\coloneqq B_{i}\cap E(M^{\prime})$ for $i=1,2$. Observe that
$(B^{\prime}_{1},B^{\prime}_{2})$ is a basis partition of $M^{\prime}$. It
follows from Lemma 5.20 that there exists a $B^{\prime}_{1}$-minor
$M^{\prime\prime}$ of $M^{\prime}$ that can be represented over $GF(2)$ by a
matrix of the form $[I_{k}~{}A]$ where $I_{k}$ is the identity matrix of size
$k$, $A$ is an $(\alpha,\beta,\gamma)$-diagonal matrix of size $k$ for a
feasible triple $(\alpha.\beta,\gamma)$ and the columns of $I_{k}$ and $A$
correspond to the elements of $B^{\prime\prime}_{1}$ and
$B^{\prime\prime}_{2}$, respectively where $B^{\prime\prime}_{i}\coloneqq
B^{\prime}_{i}\cap E(M^{\prime\prime})$ for $i=1,2$. By the feasibility of
$(\alpha,\beta,\gamma)$, we have
$(\alpha,\beta,\gamma)\in\\{(0,1,0),(0,1,1),(1,0,1)\\}$. If
$(\alpha,\beta,\gamma)=(1,0,1)$, then $A=J_{k}-I_{k}$ where $J_{k}$ is the
all-ones matrix of size $k$. Then, as $k\geq 4$, $M^{\prime\prime}$ has a
minor that can represented by $[I_{4}~{}J_{4}-I_{4}]$ over $GF(2)$. This is a
contradiction, as this matroid is not regular (see e.g. [59, page 645]), and
the class of regular matroid is minor-closed. We concluded that
$(\alpha,\beta,\gamma)\in\\{(0,1,0),(0,1,1)\\}$. Let $\varphi\colon
B^{\prime\prime}_{1}\to B^{\prime\prime}_{2}$ denote the bijection mapping the
element of $B^{\prime\prime}_{1}$ corresponding to the $i$th column if $I_{k}$
to the element of $B^{\prime\prime}_{2}$ corresponding to the $i$th column of
$A$ for $i\in[k]$. Fix a subset $Z\subseteq B^{\prime\prime}_{1}$. As in the
proof of Lemma 5.23, the columns of $[I~{}A]$ corresponding to
$(B^{\prime\prime}_{1}\setminus Z)\cup\varphi(Z)$ can be transformed into a
matrix of the form $\begin{bmatrix}I_{|Z|}&A_{1}\\\ O&A^{\prime}\end{bmatrix}$
where $I_{|Z|}$ is the identity matrix of size $|Z|$, $A^{\prime}$ is the
$(\alpha,\beta,\gamma)$-diagonal matrix of size $k-|Z|$, $O$ is an all-zeros
matrix and $A_{1}$ is an arbitrary matrix. This matrix is nonsingular, as its
determinant equals to $1$ by $(\alpha,\beta,\gamma)\in\\{(0,1,0),(0,1,1)\\}$.
It follows that $(B^{\prime\prime}_{1}\setminus Z)\cup\varphi(Z)$ is a basis
for each $Z\subseteq B^{\prime\prime}_{1}$, thus
$(B^{\prime\prime}_{1},B^{\prime\prime}_{2})$ has the elementary $k$-exchange
property. Using Lemma 5.28, we conclude that $M$ is elementarily
$(f^{\prime}(k),k)$-weakly base orderable. ∎

####  5.1.4 Graphic Matroids

As graphic matroids are regular, they are elementarily $(f(k),k)$-weakly base
orderable by Theorem 5.26 for some large function
$f\colon\mathbb{N}\to\mathbb{N}$. We give an independent proof from the proofs
of Theorems 5.17 and 5.26, which shows that for graphic matroids there exists
such a function $f$ satisfying $f(k)=O(k^{3})$.

######  Theorem 5.27.

Graphic matroids are elementarily $(3k^{3},k)$-weakly base orderable for any
$k\geq 1$.

For the proof, we will use the following statement which can be proved
analogously to Lemma 5.12.

######  Lemma 5.28.

Let $B_{1}$ and $B_{2}$ be two bases of a matroid $M$. Further, let
$M^{\prime}$ be a $B_{1}$-minor of $M$ such that
$(B^{\prime}_{1},B^{\prime}_{2})$ is a basis partition of $M^{\prime}$ and has
the elementary $k$-exchange property for some $k\geq 1$, where
$B^{\prime}_{i}\coloneqq B_{i}\cap E(M^{\prime})$ for $i=1,2$. Then,
$(B_{1},B_{2})$ has the elementary $k$-exchange property in $M$.

Next, we introduce some notation from graph theory. For a graph $G$, we use
the notations $V(G)$ and $E(G)$ to denote its set of vertices and edges,
respectively. Throughout this section, for a graph $G$, a spanning subgraph
$H$ of $G$, $F\subseteq E(H)$ and $F^{\prime}\subseteq E(G)\setminus E(H)$, we
use $H-F$ for $(V(G),E(H)\setminus F)$ and $H+F^{\prime}$ for $(V(G),E(H)\cup
F^{\prime})$. For disjoint subsets $U_{1},U_{2}\subseteq V(G)$ we use the
notations $\delta_{G}(U_{1},U_{2})\coloneqq\\{\,u_{1}u_{2}\in
E(G)\mathclose{}\nonscript\;|\nonscript\;\mathopen{}u_{1}\in U_{1},u_{2}\in
U_{2}\,\\}$ and $\delta_{G}(U_{1})\coloneqq\delta_{G}(U_{1},V(G)\setminus
U_{1})$. We use the notation $\delta_{G}(v)=\delta_{G}(\\{v\\})$ for a vertex
$v\in V(G)$, and $d_{G}(v)=|\delta_{G}(v)|$ denotes the degree of $v$. For a
subset $U\subseteq V(G)$ we say that an edge $uv$ is _induced_ by $U$ if
$u,v\in U$, and $G[U]$ denotes the graph on vertex set $U$ whose edges are the
edges of $G$ induced by $U$. An edge $uv$ _links_ the (not necessarily
disjoint) subsets $U_{1},U_{2}\subseteq V(G)$ if $u\in U_{1}$ and $v\in
U_{2}$. The following statement follows from Euler’s theorem on Eulerian
walks, and can also be found in [29].

######  Proposition 5.29.

Let $T$ be a tree with $\ell$ vertices of odd degree. Then, the minimum number
of edge-disjoint paths covering the edges of $T$ equals $\lceil\ell/2\rceil$.

######  Corollary 5.30.

Let $T$ be a tree and let $k$ denote the number of its leaves. Then, the edges
of $T$ can be covered by $k-1$ edge-disjoint paths.

###### Proof.

If $T$ has $n$ vertices from which $\ell$ have odd degrees, then
$2n-2=\sum_{v\in V}d_{T}(v)\geq k+(\ell-k)\cdot 3+(n-\ell)\cdot 2$, thus
$\ell/2\leq k-1$. ∎

We will also use the following observation.

######  Lemma 5.31.

Let $G$ be a graph containing a Hamiltonian path $P=v_{1},\dots,v_{n}$ and let
$Z\subseteq E(G)\setminus E(P)$ with $|Z|\geq k\ell$ for two integers
$k,\ell\geq 0$. Then, either there exists some $q\in[n]$ such that
$|Z\cap\delta_{G}(\\{v_{1},\ldots,v_{q-1}\\},\\{v_{q},\ldots,v_{n}\\})|\geq k$
or there exists a collection of $\ell$ edge-disjoint cycles in $G$ each of
which contains exactly one edge of $Z$.

###### Proof.

We prove the statement by induction on $\ell$. Let $i$ be the smallest integer
in $[n]$ such that $\\{v_{1},\ldots,v_{i}\\}$ induces an edge of $Z$. Observe
that there exists a cycle $C$ with $V(C)\subseteq\\{v_{1},\ldots,v_{i}\\}$
that contains exactly one edge of $Z$. If
$|\delta_{G}(\\{v_{1},\ldots,v_{i-1}\\},\\{v_{i},\ldots,v_{n}\\})\cap Z|\geq
k$, there is nothing to prove. We may hence suppose that this is not the case,
so $G-\\{v_{1},\ldots,v_{i-1}\\}$ contains at least $(\ell-1)k$ edges of $Z$.
We obtain by induction that either there exists some $q\in\\{i+1,\ldots,n\\}$
such that
$|Z\cap\delta_{G}(\\{v_{i},\ldots,v_{q-1}\\},\\{v_{q},\ldots,v_{n}\\})|\geq k$
or there exists a collection $\mathcal{C}$ of $\ell-1$ edge-disjoint cycles in
$G-\\{v_{1},\ldots,v_{i-1}\\}$ each of which contains exactly one edge of $Z$.
In the first case, we obtain
$|Z\cap\delta_{G}(\\{v_{1},\ldots,v_{q-1}\\},\\{v_{q},\ldots,v_{n}\\})|\geq|Z\cap\delta_{G}(\\{v_{i},\ldots,v_{q-1}\\},\\{v_{q},\ldots,v_{n}\\})|\geq
k$ and in the second case, we obtain the desired collection of cycles by
adding $C$ to $\mathcal{C}$. ∎

We are now ready to prove Theorem 5.27. Vaguely speaking, we use the fact that
every large tree either contains a lot of leaves or contains long paths.
Either of these structures will prove beneficial for us.

###### Proof of Theorem 5.27.

Assume that $\alpha\geq k\geq 1$ are integers such that there exists a graphic
matroid which is not elementarily $(\alpha,k)$-weakly base orderable. Let $G$
be a connected graph representing such a matroid with the minimal number of
edges possible. There exist spanning trees $T_{1}$ and $T_{2}$ of $G$ not
satisfying the elementary $k$-exchange property with $|E(T_{1})\setminus
E(T_{2})|\geq\alpha$. By Lemma 5.28, contracting $E(T_{1})\cap E(T_{2})$ and
deleting $E(G)\setminus(E(T_{1})\cup E(T_{2}))$ in $G$ gives a graph which is
also not elementarily $(\alpha,k)$-weakly base orderable. Hence, using that
$G$ has the minimum number of edges, we obtain $E(T_{1})\cap
E(T_{2})=\emptyset$ and $E(T_{1})\cup E(T_{2})=E(G)$. This means that
$|E(T_{1})|\geq\alpha$ and for any choice of $k$-element subsets $X\subseteq
E(T_{1})$ and $Y\subseteq E(T_{2})$ and any bijection $\varphi\colon
X\rightarrow Y$, there exists some $Z\subseteq X$ such that
$T_{1}-Z+\varphi(Z)$ is not a spanning tree of $G$.

######  Claim 5.32.

$T_{1}$ has less than $k$ leaves.

###### Proof.

Suppose otherwise, and let $L$ be a set of $k$ leaves of $T_{1}$. For every
$v\in L$, let $x_{v}$ be the unique edge in $\delta_{T_{1}}(v)$, and let
$X\coloneqq\\{\,x_{v}\mathclose{}\nonscript\;|\nonscript\;\mathopen{}v\in
L\,\\}$. By Lemma 2.1, there exists a bijection $\phi\colon E(T_{1})\to
E(T_{2})$ such that $T_{1}-e+\phi(e)$ is a spanning tree for each $e\in
E(T_{1})$. Let $y_{v}\coloneqq\phi(x_{v})$ for $v\in L$, define
$Y\coloneqq\\{\,y_{v}\mathclose{}\nonscript\;|\nonscript\;\mathopen{}v\in
L\,\\}$ and let $\varphi$ denote the restriction of $\phi$ to $X$. Observe
that $|X|=|Y|=|L|=k$. By the choice of $G$, $T_{1}$ and $T_{2}$, there exists
some $Z\subseteq X$ such that $T_{1}-Z+\varphi(Z)$ contains a cycle $C$. Note
that $Z$ is nonempty since $T_{1}$ is a spanning tree. Let
$v_{1},\dots,v_{\ell}\in L$ such that
$E(C)\cap\varphi(Z)=\\{y_{v_{1}},\dots,y_{v_{\ell}}\\}$. Since
$T_{1}-x_{v_{i}}+y_{v_{i}}$ is a spanning tree for $i\in[\ell]$, the edge
$y_{v_{i}}$ is incident to $v_{i}$, that is, $y_{v_{i}}=\\{u_{i},v_{i}\\}$ for
some $u_{i}\in V(G)$. As $v_{i}$ is isolated in $T_{1}-Z$, both edges incident
to $v_{i}$ in $C$ are in
$E(C)\cap\varphi(Z)=\\{y_{v_{1}},\dots,y_{v_{\ell}}\\}$, thus
$v_{i}\in\\{u_{1},\dots,u_{\ell}\\}$. We showed that
$\\{v_{1},\dots,v_{\ell}\\}\subseteq\\{u_{1},\dots,u_{\ell}\\}$, hence
$\\{v_{1},\dots,v_{\ell}\\}=\\{u_{1},\dots,u_{\ell}\\}$ and each of
$v_{1},\dots,v_{\ell}$ has degree two in $\\{y_{v_{1}},\dots,y_{v_{\ell}}\\}$.
This contradicts that $T_{2}$ is a spanning tree. ∎

######  Claim 5.33.

$T_{1}$ does not contain edge-disjoint paths $P_{1}$ and $P_{2}$ such that
$V(P_{1})$ and $V(P_{2})$ are linked by at least $2k$ edges.

###### Proof.

Suppose otherwise, so there exist edge-disjoint paths $P_{1}$ and $P_{2}$ and
a set $E^{\prime}$ of at least $2k$ edges in $E(T_{2})$ linking $V(P_{1})$ and
$V(P_{2})$. For $i\in[2]$, let $W_{i}$ be the set of vertices in $V(P_{i})$
incident to an edge in $E^{\prime}$. As $T_{2}[W_{1}\cup W_{2}]$ is a forest,
we obtain $|W_{1}|+|W_{2}|\geq|E^{\prime}|+1\geq 2k+1$. By symmetry, we may
suppose that $|W_{1}|\geq\lceil(|W_{1}|+|W_{2}|)/2\rceil\geq k+1$. Let
$P_{1}=v_{1},\ldots,v_{q}$, and let $q_{0}\in[q]$ be the unique index such
that $v_{q_{0}}$ is in the same component of $T_{1}-E(P_{1})$ as $V(P_{2})$.
As $|W_{1}|\geq k+1$, there exist indices $1\leq i_{1}<\dots<i_{k}\leq q$ such
that $\\{v_{i_{1}},\dots,v_{i_{k}}\\}\subseteq W_{1}-v_{q_{0}}$. Note that
$\\{v_{i_{1}},\dots,v_{i_{k}}\\}\subseteq V(P_{1})\setminus V(P_{2})$, as if
$P_{1}$ and $P_{2}$ have a common vertex then $V(P_{1})\cap
V(P_{2})=\\{v_{q_{0}}\\}$. For $j\in[k]$, let $y_{j}$ be an edge in
$E^{\prime}$ incident to $v_{i_{j}}$, let $x_{j}\coloneqq
v_{i_{j}}v_{i_{j}+1}$ if $i_{j}<q_{0}$, and let $x_{j}\coloneqq
v_{i_{j}}v_{i_{j}-1}$ if $i_{j}>q_{0}$. Let
$X\coloneqq\\{\,x_{j}\mathclose{}\nonscript\;|\nonscript\;\mathopen{}j\in[k]\,\\}$,
$Y\coloneqq\\{\,y_{j}\mathclose{}\nonscript\;|\nonscript\;\mathopen{}j\in[k]\,\\}$
and let $\varphi\colon X\to Y$ be defined by $\varphi(x_{j})=y_{j}$ for
$j\in[k]$. We prove that $T_{1}-Z+\varphi(Z)$ is a spanning tree for each
$Z\subseteq X$ by showing that each vertex of $P_{1}$ is contained in the same
component of $T_{1}-Z+\varphi(Z)$ as $V(P_{2})$. By symmetry, it suffices to
prove the statement for vertices $v_{s}$ with $s\in[q]$ and $s\geq q_{0}$. We
prove it by induction on $s$, the statement holds for $s=q_{0}$ by the
definition of $q_{0}$. Let $s\geq q_{0}+1$. If
$v_{s}\not\in\\{v_{i_{1}},\dots,v_{i_{k}}\\}$, or $s=i_{j}$ for some $j\in[k]$
and $x_{j}=v_{i_{j}}v_{i_{j}-1}\not\in Z$, then $T_{1}-Z+\varphi(Z)$ contains
the edge $v_{s}v_{s-1}$, thus the statement follows by induction. Otherwise,
$s=i_{j}$ for some $j\in[k]$ with $x_{j}\in Z$, thus $T-Z+\varphi(Z)$ contains
the edge $y_{j}$ which links $v_{i_{j}}$ to $V(P_{2})$. This shows that
$T_{1}-Z+\varphi(Z)$ is a spanning tree for each $Z\subseteq X$, which is a
contradiction by $|X|=|Y|=k$. ∎

######  Claim 5.34.

$G$ does not contain a collection of $k$ edge-disjoint cycles each of which
contains exactly one edge of $T_{2}$.

###### Proof.

Suppose otherwise and let $\mathcal{C}$ be a collection of such cycles. For
every $C\in\mathcal{C}$, let $y_{C}$ be the unique edge in $E(C)\cap E(T_{2})$
and let $x_{C}$ be an arbitrary edge in $E(C)\cap E(T_{1})$. Let
$X\coloneqq\\{\,x_{C}\mathclose{}\nonscript\;|\nonscript\;\mathopen{}C\in\mathcal{C}\,\\},Y\coloneqq\\{\,y_{C}\mathclose{}\nonscript\;|\nonscript\;\mathopen{}C\in\mathcal{C}\,\\}$,
and let $\varphi\colon X\rightarrow Y$ be the mapping with
$\varphi(x_{C})=y_{C}$ for every $C\in\mathcal{C}$. Observe that $|X|=|Y|=k$.
We prove by induction on $|Z|$ that $T_{1}-Z+\varphi(Z)$ is a spanning tree
for each $Z\subseteq X$. If $|Z|\geq 1$, then let $x_{C}\in Z$ be an arbitrary
element. $T\coloneqq T_{1}-(Z-x_{C})+\varphi(Z-x_{C})$ is a spanning tree by
the induction hypothesis. The fundamental cycle of $y_{C}$ with respect to $T$
is $C$, in particular it contains $x_{C}$, thus
$T_{1}-Z+\varphi(Z)=T-x_{C}+y_{C}$ is a spanning tree. This contradicts the
choice of $G$, $T_{1}$, and $T_{2}$. ∎

By 5.32 and Corollary 5.30, we obtain that there exists a collection
$\mathcal{P}$ of at most $k-2$ edge-disjoint paths in $T_{1}$ such that
$\bigcup_{P\in\mathcal{P}}E(P)=E(T_{1})$. By 5.33, for any two distinct paths
$P_{1},P_{2}\in\mathcal{P}$ at most $2k-1$ edges link $V(P_{1})$ to
$V(P_{2})$. If $V(P)$ induces at least $2k^{2}$ edges of $T_{2}$ for some
$P\in\mathcal{P}$, then Lemma 5.31 implies that either there exists a set of
$2k$ edges of $E(T_{2})$ linking two edge-disjoint subpaths of $P$ or there
exists a collection of $k$ edge-disjoint cycles in $G$ each of which contains
exactly one edge of $E(T_{2})$. We obtain contradictions to Claims 5.33 and
5.34, respectively. Therefore, $V(P)$ induces at most $2k^{2}-1$ edges of
$T_{2}$ for each $P\in\mathcal{P}$, hence

$|E(T_{2})|\leq\binom{k-2}{2}\cdot(2k-1)+(k-2)\cdot(2k^{2}-1)=\frac{6k^{3}-19k^{2}+15k-2}{2}<3k^{3}.$

We got that $\alpha\leq|E(T_{2})|<3k^{3}$ for any $\alpha\geq k$ such that
some graphic matroid is not elementarily $(\alpha,k)$-weakly base orderable,
that is, graphic matroids are elementarily $(3k^{3},k)$-weakly base orderable.
∎

###  5.2 Two forbidden labels

The objective of this section is to prove the following restatement of the
case $|F|=2$ of 5.1. Vaguely speaking, we first reduce the problem to matroids
on six elements and then combine some earlier results with a particular
treatment for the cycle matroid of $K_{4}$.

In order to prove the result, we need to prove that an $F$-avoiding basis can
be found by exchanging at most two elements which we do by means of a
contradiction. The following two results allow us to only consider the case
when the matroid has rank three. This also follows from the proof of [46,
Theorem 2], but we give proofs to keep the paper self-contained.

######  Lemma 5.35.

Let $M$ be a matroid, $\psi\colon E(M)\rightarrow\Gamma$ a group labeling and
$F\subseteq\Gamma$ a finite set of labels. Suppose that there exists at least
one $F$-avoiding basis of $M$. If there exists a basis $A$ such that
$|A\setminus A^{\prime}|\geq|F|+1$ for all $F$-avoiding bases $A^{\prime}$ of
$M$, then there also exists a basis $B$ and an $F$-avoiding basis $B^{*}$ such
that $|B\setminus B^{*}|=|F|+1$ and $|B\setminus B^{\prime}|\geq|F|+1$ for all
$F$-avoiding bases $B^{\prime}$.

###### Proof.

Let $B$ be a basis of $M$ for which the minimum of $|B\setminus B^{\prime}|$
over all $F$-avoiding bases $B^{\prime}$ is minimum among all bases that
satisfy $|B\setminus B^{\prime}|\geq|F|+1$ for all $F$-avoiding bases
$B^{\prime}$ and let $B^{*}$ be an $F$-avoiding basis for which this minimum
is attained. Observe that $B$ is well-defined by assumption and if
$|B\setminus B^{*}|=|F|+1$, there is nothing to prove. We may hence suppose
that $|B\setminus B^{*}|\geq|F|+2$. By the basis exchange axiom, there exist
$x\in B\setminus B^{*}$ and $y\in B^{*}\setminus B$ such that $B_{1}\coloneqq
B-x+y$ is a basis. Clearly, by $|B\setminus B_{1}|=1$ and the choice of $B$,
we have $\psi(B_{1})\in F$. If there exists an $F$-avoiding basis $B_{1}^{*}$
with $|B_{1}\setminus B_{1}^{*}|\leq|F|$, we obtain $|B\setminus
B_{1}^{*}|\leq|B\setminus B_{1}|+|B_{1}\setminus B_{1}^{*}|\leq|F|+1$, a
contradiction. We hence obtain $|B_{1}\setminus B^{\prime}|\geq|F|+1$ for
every $F$-avoiding basis $B^{\prime}$. Further, we have $|B_{1}\setminus
B^{*}|=|B\setminus B^{*}|-1$, a contradiction to the choice of $B$. ∎

######  Proposition 5.36.

Let $M$ be a matroid, $\psi\colon E(M)\rightarrow\Gamma$ a group labeling,
$F\subseteq\Gamma$ a finite subset of labels and let $B$ be a basis such that
$|B\setminus\bar{B}|\geq|F|+1$ for every $F$-avoiding basis $\bar{B}$. Let
$M^{\prime}$ be obtained from $M$ by contracting a set $X\subseteq B$, let
$B^{\prime}\coloneqq B\setminus X$ and let
$F^{\prime}\coloneqq\\{\,f-\psi(X)\mathclose{}\nonscript\;|\nonscript\;\mathopen{}f\in
F\,\\}$. Then, $|B^{\prime}\setminus\bar{B^{\prime}}|\geq|F|+1$ for every
basis $F^{\prime}$-avoiding basis $\bar{B^{\prime}}$ of $M^{\prime}$.

###### Proof.

Suppose otherwise, so there exists a basis $B_{1}^{\prime}$ of $M^{\prime}$
which is $F^{\prime}$-avoiding and satisfies $|B^{\prime}\setminus
B_{1}^{\prime}|\leq|F|$. Let $B_{1}\coloneqq B_{1}^{\prime}\cup X$, then
$B_{1}$ is a basis of $M^{\prime}=M/X$ by the definition of contraction.
Observe that $\psi(B_{1})=\psi(B_{1}^{\prime})+\psi(X)\notin F$ as
$\psi(B_{1}^{\prime})\notin F^{\prime}$. Further, by construction and as
$B^{\prime}$ and $B_{1}^{\prime}$ are bases of $M^{\prime}$, we have
$|B_{1}|=|B|-|B^{\prime}|+|B_{1}^{\prime}|=|B|$. Hence $B_{1}$ is an
$F$-avoiding basis of $M$ with $|B\setminus B_{1}|=|B^{\prime}\setminus
B_{1}^{\prime}|\leq|F|$, a contradiction. ∎

It will turn out that in the forthcoming proof, the cycle matroid of $K_{4}$
will play a crucial role. It needs to be treated separately due to the
following result. Mayhew and Royle [52] showed by the implementation
experiment that the number of rank-3 matroids on six elements which is not
strongly base orderable is one. Since $M(K_{4})$ is not strongly base
orderable, we can see that a rank-3 matroid on six elements is either
isomorphic to $M(K_{4})$ or strongly base orderable.

######  Proposition 5.37 (Mayhew–Royle [52]).

Let $M$ be a rank-3 matroid on six elements that is not isomorphic to
$M(K_{4})$. Then, $M$ is strongly base orderable.

We now give our main result for the special case that the matroid in
consideration is the cycle matroid of $K_{4}$.

######  Lemma 5.38.

Let $M\coloneqq M(K_{4})$, let $\psi\colon E(M)\to\Gamma$ be a group labeling
and let $F\subseteq\Gamma$ be a 2-element set such that $M$ has at least one
$F$-avoiding basis. Then, for any basis $B$, there exists an allowed basis
$B^{*}$ with $|B\setminus B^{*}|\leq 2$.

###### Proof.

Suppose otherwise, so there exist two bases $B$ and $B^{*}$ of $M$ such that
$|B\setminus B^{\prime}|\geq 3$ for every allowed basis $B^{\prime}$ and
$B^{*}$ is an allowed basis. By symmetry, we may suppose that
$B=\\{a_{1},a_{2},a_{3}\\}$ and $B^{*}=\\{b_{1},b_{2},b_{3}\\}$ where for
$i\in[3]$, the edges of $K_{4}$ corresponding to $a_{i}$ and $b_{i}$ are
marked in Fig. 1.

Figure 1: A drawing of $K_{4}$ with the edge labeling used in the proof of
Lemma 5.38.

Let $F=\\{f_{1},f_{2}\\}$. By symmetry, we may suppose that $\psi(B)=f_{1}$.

######  Claim 5.39.

For any $\emptyset\neq X\subsetneq B$ and $\emptyset\neq Y\subsetneq B^{*}$
such that $B-X+Y$ and $B^{*}+X-Y$ are bases, we have
$\psi(B-X+Y)=\psi(B^{*}+X-Y)=f_{2}$.

###### Proof.

Let $B_{1}=B-X+Y$ and $B_{2}=B^{*}+X-Y$. For $i\in[2]$, the label of $B_{i}$
is $f_{1}$ or $f_{2}$ since otherwise $B_{i}$ is an allowed basis and is
closer to $B$ than $B^{*}$. In addition, if $B_{i}$ has label $f_{1}$ for some
$i\in[2]$, we obtain

$\displaystyle\psi(B_{3-i})=\psi(B)+\psi(B^{*})-\psi(B_{i})=f_{1}+\psi(B^{*})-f_{1}=\psi(B^{*}),$

a contradiction to the previous observation. ∎

As $B-a_{1}+b_{1}$ and $B^{*}-b_{1}+a_{1}$ are bases of $M$, we obtain
$\psi(B-a_{1}+b_{1})=f_{2}$ by 5.39 and hence
$\psi(b_{1})-\psi(a_{1})=\psi(B-a_{1}+b_{1})-\psi(B)=f_{2}-f_{1}$ . Similar
arguments show
$\psi(b_{2})-\psi(a_{1})=\psi(b_{3})-\psi(a_{1})=\psi(b_{1})-\psi(a_{2})=\psi(b_{1})-\psi(a_{3})=f_{2}-f_{1}$.
In particular, we obtain $\psi(a_{1})=\psi(a_{2})=\psi(a_{3})$ and
$\psi(b_{1})=\psi(b_{2})=\psi(b_{3})$, so
$\psi(b_{i})-\psi(a_{j})=f_{2}-f_{1}$ for all $i,j\in[3].$ As $B-a_{1}+b_{1}$
and $B^{*}-b_{1}+a_{1}$ are bases of $M$, we obtain
$\psi(B^{*}-b_{1}+a_{1})=f_{2}$ by 5.39.

This yields

$\displaystyle
f_{2}=\psi(B^{*}-b_{1}+a_{1})=\psi(B)+(\psi(b_{2})-\psi(a_{2}))+(\psi(b_{3})-\psi(a_{3}))=f_{1}+2(f_{2}-f_{1}),$

so $f_{1}=f_{2}$, which is a contradiction because $f_{1}$ and $f_{2}$ are
distinct labels. ∎

We are now ready to prove the main result of this section.

######  Theorem 5.40.

Let $M$ be a matroid, $\psi\colon E(M)\rightarrow\Gamma$ a group labeling, and
let $F$ be a 2-element subset of $\Gamma$. For any basis $B$, there exists an
$F$-avoiding basis $B^{*}$ such that $|B\setminus B^{*}|\leq 2$, provided that
there exists at least one $F$-avoiding basis.

###### Proof.

Suppose otherwise. Then, by Lemma 5.35, there exists a basis $B$ with
$|B\setminus B^{\prime}|\geq 3$ for all $F$-avoiding bases $B^{\prime}$ and an
$F$-avoiding basis $B_{1}$ with $|B\setminus B_{1}|=3$. Let
$M^{\prime}\coloneqq M/(B\cap B_{1})\setminus(E(M)\setminus(B\cup B_{1}))$,
$B^{\prime}\coloneqq B\setminus B_{1}$, $B_{1}^{\prime}\coloneqq B\setminus
B_{1}$, and
$F^{\prime}\coloneqq\\{\,f-\psi(X)\mathclose{}\nonscript\;|\nonscript\;\mathopen{}f\in
F\,\\}$. We obtain by Proposition 5.36 that
$|B^{\prime}\setminus\bar{B^{\prime}}|\geq 3$ for every $F^{\prime}$-avoiding
basis $\bar{B^{\prime}}$ of $M^{\prime}$. Further, we have
$\psi(B_{1}^{\prime})=\psi(B_{1})-\psi(X)\notin F^{\prime}$. Observe that
$M^{\prime}$ is a matroid on 6 elements. By Proposition 5.37, we obtain that
$M^{\prime}$ is either strongly base orderable or isomorphic to $M(K_{4})$. If
$M^{\prime}$ is strongly base orderable, we obtain a contradiction to
Corollary 5.15. If $M^{\prime}$ is isomorphic to $M(K_{4})$, we obtain a
contradiction to Lemma 5.38. ∎

##  6 Hardness and Negative Results

In this section, we give the algorithmic hardness results and counterexamples
contained in this work. Sections 6.1 and 6.2 contain algorithmic
intractability results and Section 6.3 contains a counterexample to a
conjecture of Liu and Xu [46].

###  6.1 Hardness of Non-zero Common Basis with $\mathbb{Z}_{2}\leq\Gamma$

We here show that Non-Zero Common Basis is intractable for any group $\Gamma$
such that $\mathbb{Z}_{2}\leq\Gamma$. This implies that the condition on
$\Gamma$ in Theorem 3.9 is crucial indeed. Then, we explain the relation of
this result to common base packing and dual lattices.

######  Theorem 6.1.

Non-Zero Common Basis requires an exponential number of independence queries
for any fixed group $\Gamma$ such that $\mathbb{Z}_{2}\leq\Gamma$.

We will use the following statement which can be derived from e.g. [24,
Theorem 5.3.5]. The matroids arising in the form as in Lemma 6.2 coincide with
_sparse paving matroids_ of rank at least two.

######  Lemma 6.2.

Let $r\geq 2$ be an integer, $E$ a ground set of size at least $r$, and
$\mathcal{H}\subseteq\binom{E}{r}$ such that $|H\cap H^{\prime}|\leq r-2$ for
each distinct $H_{1},H_{2}\in\mathcal{H}$. Then,
$\binom{E}{r}\setminus\mathcal{H}$ forms the family of bases of a matroid of
rank $r$.

Using this construction and an information-theoretic argument, we prove
Theorem 6.1. We note that the construction of the sparse paving matroid used
in our proof is closely related to the notion of $\Pi$-matroids introduced in
[19].

###### Proof of Theorem 6.1.

As $\Gamma$ contains $\mathbb{Z}_{2}$ as a subgroup, we may suppose that
$\Gamma=\mathbb{Z}_{2}$. Let $r\geq 2$, $A=\\{a_{1},\dots,a_{r}\\}$ and
$B=\\{b_{1},\dots,b_{r}\\}$ be disjoint sets of size $r$, and $E\coloneqq
A\cup B$. Consider

$\mathcal{H}\coloneqq\\{\,H\subseteq
E\mathclose{}\nonscript\;|\nonscript\;\mathopen{}\text{$|H\cap\\{a_{1},b_{1}\\}|=\dots=|H\cap\\{a_{r},b_{r}\\}|=1$,
$|H\cap A|$ is odd}\,\\}.$

Observe that $|H_{1}\cap H_{2}|\leq r-2$ holds for any two distinct
$H_{1},H_{2}\in\mathcal{H}$. Indeed, if $|H_{1}\cap A|=|H_{2}\cap A|$, then
$H_{1}\setminus H_{2}$ contains at least one element of $A$ and at least one
element of $B$, otherwise $|H_{1}\cap A|$ and $|H_{2}\cap A|$ differ by at
least two since both of them are odd. Then, by Lemma 6.2,
$\binom{E}{r}\setminus\mathcal{H}$ forms the basis family of a sparse paving
matroid $M$. Let $N$ denote the unitary partition matroid defined by partition
classes $\\{a_{1},b_{1}\\},\dots,\\{a_{r},b_{r}\\}$, and $\psi\colon
E\to\mathbb{Z}_{2}$ the labeling defined by $\psi(a_{1})=\dots=\psi(a_{r})=1$
and $\psi(b_{1})=\dots=\psi(b_{r})=0$. The common bases of $M$ and $N$ are
exactly the sets containing one element from each of the pairs
$\\{a_{1},b_{1}\\},\dots,\\{a_{r},b_{r}\\}$ and an even number of elements
from $A$, hence all common bases of $M$ and $N$ have label zero. For any
$H\in\mathcal{H}$ let $M_{H}$ denote the sparse paving matroid with family of
bases $\binom{E}{r}\setminus(\mathcal{H}\setminus\\{H\\})$. Observe that
$M_{H}$ is well-defined for all $H\in\mathcal{H}$ by Lemma 6.2. Since $H$ is a
common basis of $M_{H}$ and $N$ having label 1, any algorithm for Non-Zero
Common Basis must distinguish between the instance $M,N,\psi$ and the
instances $M_{H},N,\psi$ for $H\in\mathcal{H}$. Since the only way to
distinguish $M$ and an $M_{H}$ is to query the independence of $H$, any
algorithm solving Non-Zero Common Basis must query the independence of each
$H\in\mathcal{H}$, and thus uses at least $|\mathcal{H}|=2^{r-1}$ independence
queries. ∎

######  Remark 6.3.

Bérczi and Schwarcz [12] showed that any algorithm which decides if the common
ground set of two matroids can be partitioned into two common bases requires
an exponential number of oracle queries. Observe that if $r$ is odd in the
proof of Theorem 6.1, then $E$ cannot be partitioned into two common bases of
$M$ and $N$, while $(H,E\setminus H)$ is a partition into two common bases of
$M_{H}$ and $N$ for any $H\in\mathcal{H}$. This gives a new and simpler proof
of the result of [12].

The previous connection of a partitioning problem and a certain non-zero
problem is no coincidence: relaxations of partitioning problems are related to
certain non-zero problems for the group $\mathbb{R}/\mathbb{Z}\simeq[0,1)$ via
_dual lattices_. The _dual_ of a lattice $L\subseteq\mathbb{R}^{n}$ is the set
$L^{*}\coloneqq\\{\,y\in\mathbb{R}^{n}\mathclose{}\nonscript\;|\nonscript\;\mathopen{}y^{T}x\in\mathbb{Z}~{}(x\in
L)\,\\}$. For a set family $\mathcal{F}\subseteq 2^{E}$, the dual of
$\operatorname{lat}(\mathcal{F})$ is
$\operatorname{lat}^{*}(\mathcal{F})\coloneqq\\{\,y\in\mathbb{R}^{E}\mathclose{}\nonscript\;|\nonscript\;\mathopen{}y(F)\in\mathbb{Z}~{}(F\in\mathcal{F})\,\\}$
by letting $y(F)\coloneqq\sum_{e\in F}y_{e}$ for $F\subseteq E$. Therefore,
deciding membership in the dual lattice $\operatorname{lat}^{*}(\mathcal{F})$
is equivalent to deciding the existence of a non-zero member of $\mathcal{F}$
for a labeling to the group $\mathbb{R}/\mathbb{Z}\cong[0,1)$. By Hermite’s
theorem [24, Theorem 4.1.23], $\operatorname{lat}(\mathcal{F})$ is related to
its dual by
$\operatorname{lat}(\mathcal{F})=\\{\,x\in\mathbb{R}^{E}\mathclose{}\nonscript\;|\nonscript\;\mathopen{}\nexists
y\in\operatorname{lat}^{*}(\mathcal{F})\text{ with
}y^{T}x\not\in\mathbb{Z}\,\\}$.