# On the Complexity of Matroid Isomorphism Problem

Raghavendra Rao B.V The Institute of Mathematical Sciences,C.I.T.
Campus,Chennai 600 113, India<EMAIL_ADDRESS>Jayalal Sarma M.N Institute
for Theoretical Computer Science,Tsinghua University,Beijing 100 084, China.
<EMAIL_ADDRESS>The work was done when this author was also a graduate
student at the Institute of Mathematical Sciences, Chennai, India.

###### Abstract

We study the complexity of testing if two given matroids are isomorphic. The
problem is easily seen to be in $\Sigma_{2}^{p}$. In the case of linear
matroids, which are represented over polynomially growing fields, we note that
the problem is unlikely to be $\Sigma_{2}^{p}$-complete and is
${\mathsf{co}}{\mathsf{NP}}$-hard. We show that when the rank of the matroid
is bounded by a constant, linear matroid isomorphism, and matroid isomorphism
are both polynomial time many-one equivalent to graph isomorphism.

We give a polynomial time Turing reduction from graphic matroid isomorphism
problem to the graph isomorphism problem. Using this, we are able to show that
graphic matroid isomorphism testing for planar graphs can be done in
deterministic polynomial time. We then give a polynomial time many-one
reduction from bounded rank matroid isomorphism problem to graphic matroid
isomorphism, thus showing that all the above problems are polynomial time
equivalent.

Further, for linear and graphic matroids, we prove that the automorphism
problem is polynomial time equivalent to the corresponding isomorphism
problems. In addition, we give a polynomial time membership test algorithm for
the automorphism group of a graphic matroid.

##  1 Introduction

Isomorphism problems over various mathematical structures have been a source
of intriguing problems in complexity theory (see [AT05]). The most important
problem of this domain is the well-known graph isomorphism problem. Though the
complexity characterization of the general version of this problem is still
unknown, there have been various interesting special cases of the problem
which are known to have polynomial time algorithms [BGM82, Luk80]. In this
paper we talk about isomorphism problem associated with matroids.

A matroid $M$ is a combinatorial object defined over a finite set $S$ (of size
$m$) called the ground set, equipped with a non-empty family ${\mathcal{I}}$
of subsets of $S$ (containing the empty subset) which is closed under taking
of subsets and satisfies the exchange axiom : for any
$I_{1},I_{2}\in{\mathcal{I}}$ such that $|I_{1}|>|I_{2}|$, $\exists x\in
I_{1}\setminus I_{2}$, $I_{2}\cup\\{x\\}\in{\mathcal{I}}$. The sets in
${\mathcal{I}}$ are called independent sets. The rank of the matroid is the
size of the maximal independent set. This provides useful abstractions of many
concepts in combinatorics and linear algebra [Whi35]. The theory of matroids
is a well studied area of combinatorics [Oxl92]. We study the problem of
testing isomorphism between two given matroids.

Two matroids $M_{1}$ and $M_{2}$ are said to be isomorphic if there is a
bijection between the elements of the ground set which maps independent sets
to independent sets, (or equivalently circuits to circuits, or bases to bases,
see section 2). Quite naturally, the representation of the input matroids is
important in deciding the complexity of the algorithmic problem.

There are several equivalent representations of a matroid. For example,
enumerating the maximal independent sets (called bases) or the minimal
dependent sets (called circuits) also defines the matroid. These
representations, although can be exponential in the size of the ground set,
indeed exist for every matroid, by definition. With this enumerative
representation, Mayhew [May08] studied the matroid isomorphism problem, and
shows that the problem is equivalent to graph isomorphism problem. However, a
natural question is whether the problem is difficult when the representation
of the matroid is more implicit?. In a black-box setting, one can also
consider the input representation in the form of an oracle or a black-box,
where the oracle answers whether a given set is independent or not.

More implicit (and efficient) representation of matroids have been studied.
One natural way is to identify the given matroid with matroids defined over
combinatorial or algebraic objects which have implicit descriptions. A general
framework in this direction is the representation of a matroid over a field. A
matroid $M=(S,\mathcal{I})$ of rank $r$ is said to be representable over a
field $\mathbb{F}$ if there is a map, $\phi:S\to\mathbb{F}^{r}$ such that,
$\forall A\subseteq S$, $A\in\mathcal{I}\iff\phi(A)$ is linearly independent
over $\mathbb{F}^{r}$ as a vector space. However, there are matroids which do
not admit linear representations over any field. (For example, the Vamós
Matroid, See Proposition 6.1.10, [Oxl92].). In contrast, there are matroids
(called regular matroids) which admit linear representations over all fields.

Another natural representation for a matroid is over graphs. For any graph
$X$, we can associate a matroid $M(X)$ as follows: the set of edges of $X$ is
the ground set, and the acyclic subgraphs of the given graph form the
independent sets. A matroid $M$ is called a graphic matroid (also called
polygon matroid or cyclic matroid) if it is isomorphic to $M(X)$ for some
graph $X$. It is known that graphic matroids are linear. Indeed, the incidence
matrix of the graph will give a representation over $\mbox{$\mathbb{F}$}_{2}$.
There are linear matroids which are not graphic. (See [Oxl92] for more
details.)

The above definitions themselves highlight the importance of testing
isomorphism between two given matroids. We study the isomorphism problem for
the case of linear matroids (Linear Matroid Isomorphism problem ($\mbox{\sc
LMI})$ and graphic matroids (Graphic Matroid Isomorphism problem (GMI)).

From a complexity perspective, the general case of the problem is in
$\Sigma_{2}^{p}$. However, it is not even clear a priori if the problem is in
${\mathsf{NP}}$ even in the above restricted cases where there are implicit
representations. But we note that for the case of graphic matroids the problem
admits an ${\mathsf{NP}}$ algorithm. Hence an intriguing question is about the
comparison of this problem to the well studied graph isomorphism problem.

At an intuitive level, in the graph isomorphism problem we ask for a map
between the vertices that preserves the adjacency relations, whereas in the
case of graphic matroid isomorphism, we ask for maps between the edges such
that the set of cycles (or spanning trees) in the graph are preserved. As an
example, in the case of trees, any permutation gives a 2-isomorphism, where as
computing the isomorphism between trees is known to be
${\mathsf{L}}$-complete. This indicates that the reduction between the
problems cannot be obtained by a local replacement of edges with gadgets, and
has to consider the global structure.

An important result in this direction, due to Whitney (see [Whi32]), says that
in the case of 3-connected graphs, the graphs are isomorphic if and only if
the corresponding matroids are isomorphic (see section 5). Thus the problem of
testing isomorphism of graphs and the corresponding graphic matroids are
equivalent for the case of 3-connected graphs are equivalent. Despite this
similarity between the problems, to the best of our knowledge, there has not
been a systematic study of GMI and its relationships to graph isomorphism
problem (GI). This immediately gives a motivation to study the isomorphism
problem for 3-connected graphs. In particular, from the recent results on
graph isomorphism problem for these classes of graphs [DLN08, TW08], it
follows that graphic matroid isomorphism problem for 3-connected planar graphs
${\mathsf{L}}$-complete.

In this context we study the general, linear and graphic matroid isomorphism
problems. Our main contributions in the paper are as follows:

  * •

Matroid isomorphism problem is easily seen to be in $\Sigma_{2}^{p}$. In the
case of linear matroids where the field is also a part of the input we observe
that the problem is ${\mathsf{co}}{\mathsf{NP}}$-hard (Proposition 3.4), and
is unlikely to be $\Sigma_{2}^{p}$-complete (Proposition 3.2). We also observe
that when the rank of the matroid is bounded, linear matroid isomorphism, and
matroid isomorphism are both equivalent to GI (Theorem 3.5)111We note that,
although not explicitly stated, the equivalence of bounded rank matroid
isomorphism and and graph isomorphism also follows from the results of Mayhew
[May08]. However, it is not immediately clear if the GI-hard instances are
linearly representable. Our proofs are different and extends this to linear
matroids.

  * •

We develop tools to handle colouring of ground set elements in the context of
isomorphism problem. We show that coloured version of the linear matroid
isomorphism and graphic matroid isomorphisms are as hard as the general
version (Lemma 4.2, 4.1). As an immediate application of this, we show that
the automorphism problems for graphic matroids and linear matroids are
polynomial time Turing equivalent to the corresponding isomorphism problems.
In this context, we also give a polynomial time membership test algorithm for
the automorphism group of a graphic matroid (Theorem 6.5).

  * •

We give a polynomial time Turing reduction from graphic matroid isomorphism
problem to the graph isomorphism problem by developing an edge colouring
scheme which algorithmically uses a decomposition given by [HT73] (and [CE80])
and reduce the graphic matroid (Theorem 5.3). Our reduction, in particular
implies that the graphic matroid isomorphism testing for planar graphs can be
done in deterministic polynomial time (Corollary 5.9).

  * •

Finally, we give a reduction from bounded rank matroid isomorphism problem to
graphic matroid isomorphism (Theorem 5.11), thus showing that all the above
problems are poly-time equivalent.

Table 1 below summarizes the complexity of matroid isomorphism problem under
various input representations.

Repn. of $M_{1},M_{2}$ | Complexity Bounds for MI
---|---
List of Ind. sets |  GI-complete [May08]
Linear |  GI-hard, ${\mathsf{co}}{\mathsf{NP}}$-hard ([Hli07, OW02]).
Linear (bounded rank) |  GI complete
Graphic | Turing equivalent to GI
Planar | ${\mathsf{P}}$
Planar 3-connected |  ${\mathsf{L}}$-complete
Table 1: Complexity of MI under various input representations

##  2 Notations and Preliminaries

All the complexity classes used here are standard and we refer the reader to
any standard text book (for e.g. see [Gol08]). Now we collect some basic
definitions on matroids (see also [Oxl92]). Formally, a matroid $M$ is a pair
$(S,{\mathcal{I}})$, where $S$ is a finite set called the ground set of size
$m$ and ${\mathcal{I}}$ is a collection of subsets of $S$ such that: (1) the
empty set $\phi$, is in ${\mathcal{I}}$. (2) If $I_{1}\in I$ and $I_{2}\subset
I_{1}$, then $I_{2}\in{\mathcal{I}}$. (3) If $I_{1},I_{2}\in{\mathcal{I}}$
with $|I_{1}|<|I_{2}|$, then $\exists x\in I_{2}\setminus I_{1}$ such that
$I_{1}\cup\\{x\\}$ is in ${\mathcal{I}}$.

The Rank function of a matroid is a map rank: $2^{S}\to\mathbb{N}$, is defined
for a $T\subseteq S$, as the maximum size of any element of ${\mathcal{I}}$
that is contained in $T$. The rank of the matroid is the maximum value of this
function. A circuit is a minimal dependent set. Spanning sets are subsets of
$S$ which contains at least one basis as its subset. Notice that a set
$X\subseteq S$ is spanning if and only if $rank(X)=rank(S)$. Moreover, $X$ is
a basis set if and only if it is a minimal spanning set. For any $F\subseteq
S$, $cl(F)=\\{x\in S~{}:~{}rank(F\cup x)=~{}rank(F)\\}$. A set $F\subseteq S$
is a flat if $cl(F)=F$. Hyperplanes are flats which are of rank $r-1$, where
$r=\mbox{\sc Rank}(S)$. $X\subseteq S$ is a hyperplane if and only if it is a
maximal non-spanning set.

An isomorphism between two matroids $M_{1}$ and $M_{2}$ is a bijection
$\phi:S_{1}\to S_{2}$ such that $\forall C\subseteq
S_{1}:C\in{\mathcal{C}}_{1}~{}\iff~{}\phi(C)\in{\mathcal{C}}_{2}$, where
${\mathcal{C}}_{1}$ and ${\mathcal{C}}_{2}$ are the family of circuits of the
matroids $M_{1}$ and $M_{2}$ respectively. Now we state the computational
problems more precisely.

######  Problem 1 ($\mbox{\sc Matroid Isomorphism}(\mbox{\sc MI})$).

Given two matroids $M_{1}$ and $M_{2}$ as their independent set oracles, does
there exist an isomorphism between the two matroids?

Given a matrix $A$ over a field $\mathbb{F}$, we can define a matroid $M[A]$
with columns of $A$ as the ground set and linearly independent columns as the
independent sets of $M[A]$. A matroid $M=(E,{\mathcal{I}})$ with rank$=r$ is
said to be representable over $\mathbb{F}$, if there is amap
$\Phi:E\to\mbox{$\mathbb{F}$}^{r}$ such that $I\in{\mathcal{I}}\iff\Phi(I)$ is
linearly independent in $\mbox{$\mathbb{F}$}^{n}$. Linear matroids are
matroids representable over fields. Without loss of generality we can assume
that the representation is of the form of a matrix where the columns of the
matrix correspond to the ground set elements. We assume that the field on
which the matroid is represented is also a part of the input, also that the
field has at least $m$ elements and at most $poly(m)$ elements, where
$m=poly(n)$.

######  Problem 2 ($\mbox{\sc Linear Matroid Isomorphism}(\mbox{\sc LMI})$).

Given two matrices $A$ and $B$ over a given field $\mathbb{F}$ does there
exist an isomorphism between the two linear matroids represented by them?.

As mentioned in the introduction, given a graph $X=(V,E)$ ($|V|=n,|E|=m$), a
classical way to associate a matroid $M(X)$ with $X$ is to treat $E$ as ground
set elements, the bases of $M(X)$ are spanning forests of $X$. Equivalently
circuits of $M(X)$ are simple cycles in $X$. A matroid $M$ is called graphic
iff $\exists X$ such that $M=M(X)$.

Evidently, adding vertices to a graph $G$ with no incident edges will not
alter the matroid of the graph. Without loss of generality we can assume that
$G$ does not have self-loops.

######  Problem 3 ($\mbox{\sc Graphic Matroid Isomorphism}(\mbox{\sc GMI})$).

Given two graphs $X_{1}$ and $X_{2}$ does there exist an isomorphism between
$M(X_{1})$ and $M(X_{2})$?.

Another associated terminology in the literature is about 2-ismorphism. Two
graphs $X_{1}$ and $X_{2}$ are said to $2$-isomorphic (denoted by
$X_{1}\cong_{2}X_{2}$) if their corresponding graphic matroids are isomorphic.
Thus the above problem asks to test if two given graphs are 2-isomorphic.

In a rather surprising result, Whitney [Whi33] came up with a combinatorial
characterisation of 2-isomorpic graphs. We briefly describe it here. Whitney
defined the following operations.

  * •

Vertex Identification: Let $v$ and $v^{\prime}$ be vertices of distinct
components of $X$. We modify $X$ by identifying $v$ and $v^{\prime}$ as a new
vertex $\bar{v}$.

  * •

Vertex Cleaving: This is the reverse operation of vertex identification so
that a graph can only be cleft at the a cut-vertex or at a vertex incident
with a loop.

  * •

Twisting: Suppose that the graph $X$ is obtained from the disjoint graphs
$X_{1}$ and $X_{2}$ by identifying vertices $u_{1}$ of $X_{1}$ and $u_{2}$ of
$X_{2}$ as the vertex $u$ of $X$, identifying vertices $v_{1}$ of $X_{1}$ and
$v_{2}$ of $X_{2}$ as the vertex $v$ of $X$. In a twisting of $X$ about
$\\{u,v\\}$, we identify, instead $u_{1}$ with $v_{2}$ and $u_{2}$ with
$v_{1}$ to get a new graph $X^{\prime}$.

######  Theorem 2.1 (Whitney’s 2-ismorphism theorem).

([Whi33], see also [Oxl92]) Let $X_{1}$ and $X_{2}$ be two graphs having no
isolated vertices. Then $M(X_{1})$ and $M(X_{2})$ are isomorphic if and only
if $X_{1}$ can be transformed to a graph isomorphic to $X_{2}$ by a sequence
of operations of vertex identification, cleaving and/or twisting.

The graphic matroids of planar graphs are called planar matroids. We now
define the corresponding isomorphism problem for graphic matroids,

######  Problem 4 ($\mbox{\sc Planar Matroid Isomorphism}(\mbox{\sc PMI})$).

Given two planar graphs $X_{1}$ and $X_{2}$ does there exist an isomorphism
between their graphic matroids ?.

As a basic complexity bound, it is easy to see that $\mbox{\sc
MI}\in\Sigma_{2}^{p}$. Indeed, the algorithm will existentially guess a
bijection $\sigma:S_{1}\to S_{2}$ and universally verify if for every subset
$C\subseteq S_{1}$, $C\in{\mathcal{C}}_{1}\iff\sigma(C)\in{\mathcal{C}}_{2}$
using the independent set oracle.

##  3 Linear Matroid Isomorphism

In this section we present some observations and results on Linear Matroid
Isomorphism. Some of these follow easily from the techniques in the
literature. We make them explicit in a form that is relevant to the problem
that we are considering.

We first observe that using the arguments similar to that of [KST93] one can
show $\overline{\mbox{\sc LMI}}\in{\mathsf{BP}}.\Sigma_{2}^{\mathsf{P}}$
(Notice that an obvious upper bound for this problem is $\Pi_{2}$). We include
some details of this here while we observe some points about the proof.

######  Proposition 3.1.

$\overline{\mbox{\sc LMI}}\in{\mathsf{BP}}.\Sigma_{2}^{\mathsf{P}}$

###### Proof.

Let $M_{1}$ and $M_{2}$ be the given linear matroids having $m$ columns each.
We proceed as in [KST93], for the case of GI. To give a
${\mathsf{BP}}.\Sigma_{2}^{\mathsf{P}}$ algorithm for $\overline{\mbox{\sc
LMI}}$, define the following set:

$N(M_{1},M_{2})=\left\\{(N,\phi):(N\cong M_{1})\lor(N\cong M_{2})\land\phi\in
Aut(N)\right\\}$

where $Aut(H)$ contains all the permutations (bijections) which are
isomorphisms of matroid $N$ to itself. The key property that is used in
[KST93] has the following easy counterpart in our context.

For any matroid $M$ on a ground set of size $m$, if $Aut(M)$ denote the
automorphism group of $M$, $\\#M$ denotes the number of different matroids
isomorphic to $M$, $|Aut(M)|*(\\#M)=|S_{m}|$.

$M_{1}\cong M_{2}\implies|N(M_{1},M_{2})|=m!$ $M_{1}\not\cong
M_{2}\implies|N(M_{1},M_{2})|=2.m!$

As in [KST93], we can amplify this gap and then using a good hash family and
utilise the gap to distinguish between the two cases. In the final protocol
(before amplifying) the verifier chooses a hash function and sends it to the
prover, the prover returns a tuple $(N,\phi)$ along with a proof that this
belongs to $N(M_{1},M_{2})$. (Notice that this will not work over very large
fields, especially over infinite fields.) Verifier checks this claim along
with the hash value of the tuple. This can be done in $\Sigma_{2}^{p}$. Hence
the entire algorithm gives an upper bound of
${\mathsf{BP}}.\exists.\Sigma_{2}^{p}={\mathsf{BP}}.\Sigma_{2}^{p}$, and thus
the result follows. ∎

Now, we know that [Sch99], if
$\Pi_{2}^{p}\subseteq{\mathsf{BP}}.\Sigma_{2}^{p}$ then
${\mathsf{PH}}={\mathsf{BP}}.\Sigma_{2}^{p}=\Sigma_{3}^{p}$. Thus we get the
following:

######  Theorem 3.2.

$\mbox{\sc LMI}\in\Sigma_{2}^{p}$. In addition, $\mbox{\sc LMI}\textrm{ \em is
}\Sigma_{2}^{\mathsf{P}}\textrm{\em-
hard}\implies{\mathsf{PH}}=\Sigma_{3}^{\mathsf{P}}$.

We notice that a special case of this is already known to be
${\mathsf{co}}{\mathsf{NP}}$-hard. A matroid of rank $k$ is said to be uniform
if all subsets of size at most $k$ are independent. Testing if a given linear
matroid of rank $k$ is uniform is known to be ${\mathsf{coNP}}$-complete
[OW02]. We denote them by $U_{k,m}$, the uniform matroid whose ground set is
of $m$ elements. Now notice that the above result is equivalent to checking if
the given linear matroid of rank $k$ is isomorphic to $U_{k,m}$. To complete
the argument, we use a folklore result that $U_{k,m}$ is representable over
any field $\mathbb{F}$ which has at least $m$ non-zero elements. We give some
details here since we have not seen an explicit description of this in the
literature.

######  Claim 3.3.

Let $|\mbox{$\mathbb{F}$}|>m$, $U_{k,m}$ has a representation over
$\mathbb{F}$.

###### Proof.

Let $\\{\alpha_{1},\ldots,\alpha_{m}\\}$ be distinct elements of $\mathbb{F}$,
and $\\{s_{1},\ldots,s_{m}\\}$ be elements of the ground set of $U_{k,m}$
Assign the vector
$(1,\alpha_{i},\alpha_{i}^{2},\ldots,\alpha_{i}^{k-1})\in\mbox{$\mathbb{F}$}^{k}$
to the element $s_{i}$. Any $k$ subset of these vectors forms a Vandermonde
matrix, and hence linearly independent. Any larger set is dependent since the
vectors are in $\mbox{$\mathbb{F}$}^{k}$. ∎

This gives us the following proposition.

######  Proposition 3.4.

LMI is ${\mathsf{co}}{\mathsf{NP}}$-hard.

The above proposition also holds when the representation is over infinite
fields. In this case, the proposition also more directly follows from a result
of Hlinený [Hli07], where it is shown that the problem of testing if a spike
(a special kind of matroids) represented by a matrix over $\mathbb{Q}$ is the
free spike is ${\mathsf{co}}{\mathsf{NP}}$ complete. He also derives a linear
representation for spikes.

Now we look at bounded rank variant of the problem. We denote by $\mbox{\sc
LMI}_{b}$ ($\mbox{\sc MI}_{b}$), the restriction of LMI (MI) for which the
input matrices have rank bounded by $b$. In the following we use the following
construction due to Babai [Bab78] to prove $\mbox{\sc
LMI}_{b}\equiv_{m}^{p}\mbox{\sc GI}$.

Given a graph $X=(V,E)$ ($3\leq k\leq d$, where, $d$ is the minimum vertex
degree of $X$), define a matroid $M=St_{k}(X)$ of rank $k$ with the ground set
as $E$ as follows: every subset of $k-1$ edges is independent in $M$ and every
subset of $E$ with $k$ edges is independent if and only if they do not share a
common vertex. Babai proved that $Aut(X)\cong Aut(St_{k}(X))$ and also gave a
linear representation for $St_{k}(X)$ (Lemma 2.1 in [Bab78]) for all $k$ in
the above range.

######  Theorem 3.5.

For any constant $b\geq 3$, $\mbox{\sc LMI}_{b}\equiv_{m}^{p}\mbox{\sc GI}$.

###### Proof.

$\mbox{\sc GI}\leq_{m}^{p}\mbox{\sc LMI}_{b}$: Let $X_{1}=(V_{1},E_{1})$ and
$X_{2}=(V_{2},E_{2})$ be the given GI instance. We can assume that the minimum
degree of the graph is at least $3$ since otherwise we can attach cliques of
size $n+1$ at every vertex. We note that from Babai’s proof we can derive the
following stronger conclusion.

######  Lemma 3.6.

$X_{1}\cong X_{2}\iff\forall~{}k\in[3,d],~{}St_{k}(X_{1})\cong St_{k}(X_{2})$

###### Proof.

Suppose $X_{1}\cong X_{2}$ via a bijection $\pi:V_{1}\to V_{2}$. (The
following proof works for any $k\in[3,d]$.) Let $\sigma:E_{1}\to E_{2}$ be the
map induced by $\pi$. That is $\sigma(\\{u,v\\})=\\{\pi(u),\pi(v)\\}$.
Consider an independent set $I\subseteq E_{1}$ in $St_{k}(X_{1})$. If $|I|\leq
k-1$ then $|\sigma(I)|\leq k-1$ and hence $\sigma(I)$ is independent in
$St_{k}(X_{2})$. If $|I|=k$, and let $\sigma(I)$ be dependent. This means that
the edges in $\sigma(I)$ share a common vertex $w$ in $X_{2}$. Since $\pi$ is
an isomorphism which induces $\sigma$, $\pi^{-1}(w)$ must be shared by all
edges in $I$. Thus $I$ is independent if and only if $\sigma(I)$ is
independent. Suppose $St_{k}(X_{1})\cong St_{k}(X_{2})$ via a bijection
$\sigma:E_{1}\to E_{2}$. By definition, any subset $H\subseteq E_{1}$ is a
hyperplane of $St_{k}(X_{1})$ if and only if $\sigma(H)$ is a hyperplane of
$St_{k}(X_{2})$. Now we use the following claim which follows from [Bab78].

######  Claim 3.7 ([Bab78]).

For any graph $X$, any dependent hyperplane in $St_{k}(X)$ is a maximal set of
edges which share a common vertex (forms a star) in $X$, and these are the
only dependent hyperplanes.

Now we define the graph isomorphism $\pi:V_{1}\to V_{2}$ as follows. For any
vertex $v$, look at the star $E_{1}(v)$ rooted at $v$, we know that
$\sigma(E_{1}(v))=E_{2}(v^{\prime})$ for some $v^{\prime}$. Now set
$\pi(v)=v^{\prime}$. From the above claim, $\pi$ is an isomorphism. ∎

It remains to show that representation for $St_{k}(X)$ ($X=(V,E)$) can be
computed in polynomial time. We choose $k=3$ (by the above proof, $\exists k$
and $\forall k$ in the Lemma 3.6 are equivalent). Now we show that the
representation of $St_{k}(X)$ given in [Bab78] is computable in polynomial
time. The representation of $St_{k}(X)$ is over a field $\mathbb{F}$ such that
$|\mbox{$\mathbb{F}$}|\geq|V|^{2k-1}$. For $e=\\{u,v\\}\in E$ assign a vector
$b_{e}=[1,(x_{u}+x_{v}),(x_{u}x_{v}),y_{e,1},\ldots,y_{e,k-3}]\in\mbox{$\mathbb{F}$}^{k}$,
where $x_{u},x_{v}$ and $y_{e,i}$ are distinct unknowns. To represent
$St_{k}(X)$ we need to ensure that the $k$-subsets of the columns
corresponding to a basis form a linearly independent set, and all the
remaining $k$-subsets form a dependent set. Babai [Bab78] showed that by the
above careful choice of $b_{e}$, it will be sufficient to ensure only the
independence condition. He also proved the existence of a choice of values for
the variables which achieves this if $|\mbox{$\mathbb{F}$}|\geq|V|^{2k-1}$.

We make this constructive. As $k$ is a constant, the number of bases is
bounded by ${\mathsf{poly}}(m)$. We can greedily choose the value for each
variable at every step, such that on assigning this value, the resulting set
of constant ($k\times k$) size matrices are non-singular. Since there exists a
solution, this algorithm will always find one. Thus we can compute a
representation for $St_{k}(X)$ in polynomial time.

$\mbox{\sc LMI}_{b}\leq_{m}^{p}\mbox{\sc GI}$: Let $A_{k\times m}$ and
$B_{k\times m}$ be two matrices of rank $b$ at the input. Now define the
following bipartite graph $X_{A}=(U_{A},V_{A},E_{A})$ (similarly for $X_{B}$),
where $U_{A}$ has a vertex for each column of $A$, and $V_{A}$ has a vertex
for each maximal independent set of $A$ (Notice that there are at most
${m\choose b}=O(m^{b})$ of them) and $\forall i\in U_{A},I\in V_{A},\
\\{i,I\\}\in E_{A}\iff i\in I$. Now we claim that $M(A)\cong M(B)\iff$
$X_{A}\cong X_{B}$ where the isomorphism maps $V_{A}$ to $V_{B}$, and which is
reducible to GI. It is easy to see that the matroid isomorphism can be
recovered from the map between the sets. ∎

Observe that the reduction $\mbox{\sc LMI}_{b}\leq_{m}^{p}\mbox{\sc GI}$ can
be done even if the input representation is an independent set oracle. This
gives the following corollary.

######  Corollary 3.8.

$\mbox{\sc LMI}_{b}\equiv_{m}^{p}\mbox{\sc MI}_{b}\equiv_{m}^{p}\mbox{\sc
GI}$.

##  4 Isomorphism Problem of Coloured Matroids

Vertex or edge colouring is a classical tool used extensively in proving
various results in graph isomorphism problem. We develop similar techniques
for matroid isomorphism problems too.

An edge-$k$-colouring of a graph $X=(V,E)$ is a function
$f:E\to\\{1,\ldots,k\\}$. Given two coloured graphs
$X_{1}=(V_{1},E_{1},f_{1})$ and $X_{2}=(V_{2},E_{2},f_{2})$, the Coloured-GMI
asks for an isomorphism which preserves the colours of the edges. Not
surprisingly, we can prove the following.

######  Lemma 4.1.

Coloured-GMI is ${\mathsf{AC}}^{0}$ many-one reducible to GMI.

###### Proof.

Let $X_{1}=(V_{1},E_{1},f_{1})$ and $X_{2}=(V_{2},E_{2},f_{2})$, be the two
$k$-coloured graphs at the input, with $n=|V_{1}|=|V_{2}|$. For every edge
$e=(u,v)\in E_{1}$ (respectively $E_{2}$), add a path
$P_{e}=\\{(u,v_{e,1}),(v_{e,1},v_{e,2}),\ldots,(v_{e,n+f_{1}(e)},v)\\}$ of
length $n+f_{1}(e)$ (respectively $n+f_{2}(e)$)Where $v_{e,1},\ldots
v_{e,n+f_{1}(e)}$ are new vertices. Let $X_{1}^{\prime}$ and $X_{2}^{\prime}$
be the two new graphs thus obtained. By definition, any 2-isomorphism between
$X_{1}^{\prime}$ and $X_{2}^{\prime}$ can only map cycles of equal length to
themselves. There are no simple cycles of length more than $n$ in the original
graphs. Thus, given any 2-isomorphism between $X_{1}^{\prime}$ and
$X_{2}^{\prime}$, we can recover a 2-isomorphism between $X_{1}$ and $X_{2}$
which preserves the colouring and vice versa. ∎

Now we generalize the above construction to the case of linear matroid
isomorphism. Coloured-LMI denotes the variant of LMI where the inputs are the
linear matroids $M_{1}$ and $M_{2}$ along with colour functions
$c_{i}:\\{1,\ldots,m\\}\to\mbox{$\mathbb{N}$},i\in\\{1,2\\}$. The problem is
to test if there is an isomorphism between $M_{1}$ and $M_{2}$ which preserves
the colours of the column indices. We have,

######  Lemma 4.2.

Coloured-LMI is ${\mathsf{AC}}^{0}$ many-one reducible to LMI.

###### Proof.

Let $M_{1}$ and $M_{2}$ be two coloured linear matroids represented over a
field $\mathbb{F}$. We illustrate the reduction where only one column index of
$M_{1}$ (resp. $M_{2}$) is coloured. Without loss of generality, we assume
that there are no two vectors in $M_{1}$ (resp.$M_{2}$) which are scalar
multiples of each other.

We transform $M_{1}$ and $M_{2}$ to get two matroids $M_{1}^{\prime}$ and
$M_{2}^{\prime}$. In the transformation, we add more columns to the matrix
(vectors to the ground set) and create dependency relations in such a way that
any isomorphism between the matroids must map these new vectors in $M_{1}$ to
the corresponding ones $M_{2}$.

We describe this transformation in a generic way for a matroid $M$. Let
$\\{e_{1},\ldots,e_{m}\\}$ be the column vectors of $M$, where
$e_{i}\in\mbox{$\mathbb{F}$}^{n}$. Let $e=e_{1}$ be the coloured vector in
$M$.

Choose $m^{\prime}>m$, we construct $\ell=m+m^{\prime}$ vectors $f_{1},\ldots
f_{\ell}\in\mbox{$\mathbb{F}$}^{n+m^{\prime}}$ as the columns of the following
$(n+m^{\prime})\times\ell$ matrix. The $i^{\mathrm{th}}$ column of the matrix
represents $f_{i}$.

$\left[\begin{array}[]{cccc|cccccccc}e_{11}&e_{21}&\ldots&e_{m1}&e_{11}&0&\ldots&0&0&\ldots&0\\\
e_{12}&e_{22}&\ldots&e_{m2}&0&e_{12}&\ldots&0&0&\ldots&0\\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\\
e_{1m}&e_{2m}&\ldots&e_{mm}&0&0&\ldots&e_{1m}&0&\ldots&0\\\ \hline\cr
0&0&\ldots&0&1&-1&0&0&{2}&0\\\ \vdots&\vdots&\ldots&\vdots&0&1&-1&0&{2}&0\\\
\vdots&\vdots&\ldots&\vdots&\vdots&\vdots&\ddots&\ddots&{2}&\vdots\\\
0&0&\ldots&0&0&0&\ldots&&0&1&-1\\\ 0&0&\ldots&0&-1&0&\ldots&&0&0&1\\\
\end{array}\right]$

where $-1$ denotes the additive inverse of $1$ in $\mathbb{F}$. Denote the
above matrix as $M^{\prime}=\begin{pmatrix}A&B\\\ C&D\end{pmatrix}$. Let
$S=\\{f_{m+1},\ldots,f_{m+m^{\prime}}\\}$. We observe the following:

  1. 1.

Columns of $B$ generate $e_{1}$. Since $C$ is a $0$-matrix $f_{1}\in Span(S)$.

  2. 2.

Columns of $D$ are minimal dependent. Any proper subset of columns of $D$ will
split the $1$, $-1$ pair in at least a row and hence will be independent.

  3. 3.

$S$ is linearly independent. Suppose not. Let
$\sum_{i=m}^{m+m^{\prime}}\alpha_{i}f_{i}=0$. Restricting this to the columns
of $B$ gives that $\alpha_{j}=0$ for first $j$ such that $e_{1j}\neq 0$. Thus
this gives a linearly dependent proper subset of columns of $B$, and
contradicts the above observation.

  4. 4.

If for any $f\notin S$, $f=\sum_{f_{i}\in S}\alpha_{i}f_{i}$, then
$\alpha_{i}$’s must be the same.

Now we claim that the newly added columns respect the circuit structure
involving $e_{1}$. Let $\mathcal{C}$ and $\mathcal{C}^{\prime}$ denote the set
of circuits of $M$ and $M^{\prime}$ respectively.

######  Claim 4.3.

$\displaystyle\left\\{e_{1},e_{i_{2}},\ldots,e_{i_{k}}\right\\}\in\mathcal{C}$
$\displaystyle\iff$
$\displaystyle\left\\{f_{1},f_{i_{2}}\ldots,f_{i_{k}}\right\\}\in\mathcal{C}^{\prime}\textrm{
and }$
$\displaystyle\left\\{f_{i_{2}},\ldots,f_{i_{k}},f_{m+1},\ldots,f_{m+m^{\prime}}\right\\}\in\mathcal{C}^{\prime}$

###### Proof.

Suppose $c=\\{e_{1},e_{i_{2}},\ldots,e_{i_{k}}\\}$ is a circuit in $M$. Then
clearly $\\{f_{1},f_{i_{2}},\ldots,f_{i_{k}}\\}$ is a cycle, since they are
nothing but vectors in $c$ extended with $0$s. Since
$\\{f_{i_{2}},\ldots,f_{i_{k}}\\}$ and $\\{f_{m+1},\ldots,f_{m+m^{\prime}}\\}$
both generate $f_{1}$, the set
$F=\\{f_{i_{2}},\ldots,f_{i_{k}},f_{m+1},\ldots,f_{m+m^{\prime}}\\}$ is a
linearly dependent set. Now we argue that $F$ is a minimal dependent set, and
hence is a circuit. Denote by $G$ the set $\\{f_{i_{2}},\ldots,f_{i_{k}}\\}$.

Suppose not, let $F^{\prime}\subset F$ be linearly dependent. Since $S$ is
linearly independent (property 3 above), we note that
$F^{\prime}\not\subseteq\\{f_{m+1},\ldots,f_{m+m^{\prime}}\\}$. Therefore,
$f_{i_{j}}\in F^{\prime}$ for some $0\leq j\leq k$. Since $F^{\prime}$ is
dependent, express $f_{j}$ in terms of the other elements in $F^{\prime}$:

$f_{j}=\sum_{g\in G}\gamma_{g}g+\sum_{s\in S}\delta_{s}s$

Since $G$ is linearly independent, at least one of the $\delta_{s}$ should be
non-zero. Restrict this to the matrices $C$ and $D$. This gives a non-trivial
dependent proper subset of $D$ and hence a contradiction. ∎

From the above two observations and the fact that there is no other column in
$M$ which is a multiple of $e$, the set
$f(e)=\\{f_{1},f_{m+1},\ldots,f_{m+m^{\prime}}\\}$ is a unique circuit of
length $m^{\prime}+1$ in $M^{\prime}$, where $e$ is column which is coloured.

Now we argue about the isomorphism between $M_{1}^{\prime}$ and
$M_{2}^{\prime}$ obtained from the above operation, and there is a unique
circuit of length $m^{\prime}+1>m$ in both $M_{1}^{\prime}$ and
$M_{2}^{\prime}$ corresponding to two vectors $e\in M_{1}$ and $e^{\prime}\in
M_{2}$. Hence any matroid isomorphism should map these sets to each other.
From such an isomorphism, we can recover the a matroid isomorphism between
$M_{1}$ and $M_{2}$ that maps between $e$ and $e^{\prime}$, thus preserving
the colours. Indeed, if there is a matroid isomorphism between $M_{1}$ and
$M_{2}$, that can easily be extended to $M_{1}^{\prime}$ and $M_{2}^{\prime}$.

For the general case, let $k$ be the number of different colour classes and
$c_{i}$ denote the size of the $i$th colour class. Then for each vector $e$ in
the color class $i$, we add $l_{i}=m+m^{\prime}+i$ many new vectors, which
also increases the dimension of the space by $l_{i}$. Thus the total number of
vectors in the new matroid is $\sum c_{i}(l_{i})\leq m^{3}$. Similarly, the
dimension of the space is bounded by $m^{3}$. This completes the proof of
Lemma 4.2.

∎

##  5 Graphic Matroid Isomorphism

In this section we study GMI. Unlike in the case of the graph isomorphism
problem, an ${\mathsf{NP}}$ upper bound is not so obvious for GMI. We start
with the discussion of an ${\mathsf{NP}}$ upper bound for GMI.

As stated in Theorem 2.1, Whitney gave an exact characterization of when two
graphs are 2-isomorphic, in terms of three operations; twisting, cleaving and
identification. Note that it is sufficient to find 2-isomorphisms between
2-connected components of $X_{1}$ and $X_{2}$. In fact, any matching between
the sets of 2-connected components whose edges connect 2-isomorphic components
will serve the purpose. This is because, any 2-isomorphism preserves simple
cycles, and any simple cycle of a graph is always within a 2-connected
component. Hence we can assume that both the input graphs are 2-connected and
in the case of 2-connected graphs, twist is the only possible operation.

The set of separating pairs does not change under a twist operation. Despite
the fact that the twist operations need not commute, Truemper [Tru80] gave the
following bound.

######  Lemma 5.1 ([Tru80]).

Let $X$ be a 2-connected graph of $n$ vertices, and let $Y$ be a graph
$2$-isomorphic to $X$, then: $X$ can be transformed to graph $X^{\prime}$
isomorphic to $Y$ through a sequence at most $n-2$ twists.

Using this lemma we get an ${\mathsf{NP}}$ upper bound for GMI. Given two
graphs, $X_{1}$ and $X_{2}$, the ${\mathsf{NP}}$ machine just guesses the
sequence of $n-2$ separating pairs which corresponding to the 2-isomorphism.
For each pair, guess the cut w.r.t which the twist operation is to be done,
and apply each of them in sequence to the graph $X_{1}$ to obtain a graph
$X_{1}^{\prime}$. Now ask if $X_{1}^{\prime}\cong X_{2}^{\prime}$. This gives
an upper bound of $\exists.\mbox{\sc GI}\subseteq{\mathsf{NP}}$. Thus we have,

######  Proposition 5.2.

GMI is in ${\mathsf{NP}}$.

This can also be seen as an ${\mathsf{NP}}$-reduction from GMI to GI. Now we
will give a deterministic reduction from GMI to GI. Although, this does not
improve the ${\mathsf{NP}}$ upper bound, it implies that it is unlikely that
GMI is hard for ${\mathsf{NP}}$ (Using methods similar to that of Proposition
3.2, one can also directly prove that if GMI is ${\mathsf{NP}}$-hard, then
${\mathsf{PH}}$ collapses to the second level).

Now we state the main result of the paper:

######  Theorem 5.3.

$\mbox{\sc GMI}\leq_{T}^{p}\mbox{\sc GI}$

Let us first look into the case of 3-connected graphs. A separating pair is a
pair of vertices whose deletion leaves the graph disconnected. A 3-connected
graph is a connected graph which does not have any separating pairs. Whitney
([Whi32]) proved the following equivalence,

######  Theorem 5.4 (Whitney, [Whi32]).

$X_{1}$ and $X_{2}$ be 3-connected graphs, $X_{1}\cong_{2}X_{2}\iff X_{1}\cong
X_{2}$.

Before giving a formal proof of Theorem 5.3, we describe the idea roughly
here:

### Basic Idea:

Let $X_{1}$ and $X_{2}$ be the given graphs. From the above discussion, we can
assume that the given graph is 2-connected.

In [HT73], Hopcroft and Tarjan proved that every 2-connected graph can be
decomposed uniquely into a tree of 3-connected components, bonds or
polygons.222Cunningham et al. [CE80] shows that any graphic matroid $M(X)$ is
isomorphic to $M(X_{1})\oplus M(X_{2})\ldots\oplus
M(X_{k})/\\{e_{1},e_{2},\ldots,e_{k}\\}$, where $M(X_{1}),\ldots,M(X_{k})$ are
3-connected components, bonds or polygons of $M(X)$ and $e_{1},\ldots,e_{k}$
are the virtual edges. However, it is unclear if this can be turned into a
reduction from GMI to GI using edge/vertex colouring. Moreover, [HT73] showed
that this decomposition can be computed in polynomial time. The idea is to
then find the isomorphism classes of these 3-connected components using
queries to GI (see theorem 5.4), and then colour the tree nodes with the
corresponding isomorphism class, and then compute a coloured tree isomorphism
between the two trees produced from the two graphs.

A first mind block is that these isomorphisms between the 3-connected
components need not map separating pairs to separating pairs. We overcome this
by colouring the separating pairs (in fact the edge between them), with a
canonical label of the two sub trees which the corresponding edge connects. To
support this, we observe the following. There may be many isomorphisms between
two 3-connected components which preserves the colours of the separating
pairs. However, the order in which the vertices are mapped within a separating
pair is irrelevant, since any order will be canonical up to a twist operation
with respect to the separating pair.

So with the new colouring, the isomorphism between 3-connected components maps
a separating pair to a separating pair, if and only if the two pairs of sub
trees are isomorphic. However, even if this is the case, the coloured sub
trees need not be isomorphic. This creates a simultaneity problem of colouring
of the 3-connected components and the tree nodes and thus a second mind block.

We overcome this by colouring again using the code for coloured sub trees, and
then finding the new isomorphism classes between the 3-connected components.
This process is iterated till the colours stabilize on the tree as well as on
the individual separating pairs (since there are only linear number of
3-connected components). Once this is ensured, we can recover the
2-isomorphism of the original graph by weaving the isomorphism of the
3-connected components guided by the tree adjacency relationship. In addition,
if two 3-connected components are indeed isomorphic in the correctly aligned
way, the above colouring scheme, at any point, does not distinguish between
them.

Now we convert this idea into an algorithm and a formal proof.

### Breaking into Tree of 3-connected components:

We use the algorithm of Hopcroft and Tarjan [HT73] to compute the set of
3-connected components of a 2-connected graph in polynomial time. We will now
describe some details of the algorithm which we will exploit.

Let $X(V,E)$ be a $2$-connected graph. Let $Y$ be a connected component of
$X\setminus\\{a,b\\}$, where $a,b$ is a separating pair. $X$ is an excisable
component w.r.t $\\{a,b\\}$ if $X\setminus Y$ has at least $2$ edges and is
$2$-connected. The operation of excising $Y$ from $X$ results in two graphs:
$C_{1}=X\setminus Y$ plus a virtual edge joining $(a,b),$ and $C_{2}=$ the
induced subgraph on $X\cup\\{a,b\\}$ plus a virtual edge joining $(a,b)$. This
operation may introduce multiple edges.

The decomposition of $X$ into its 3-connected components is achieved by the
repeated application of the excising operation (we call the corresponding
separating pairs as excised pairs) until all the resulting graphs are free of
excisable components. This decomposition is represented by a graph $G_{X}$
with the 3-connected components of $X$ as its vertices and two components are
adjacent in $G_{X}$ if and only if they share a virtual edge. In the above
explanation, the graph $G_{X}$ need not be a tree as the components which
share a separating pair will form a clique.

To make it a tree, [HT73] introduces another component corresponding to the
virtual edges thus identifying all the virtual edges created in the same
excising operation with each other.

Instead, we do a surgery on the original graph $X$ and the graph $G_{X}$. We
add an edge between all the excised pairs (excised while obtaining $G_{X}$) to
get graph $X^{\prime}$. Notice that, following the same series of
decomposition gives a new graph $T_{X}$ which is the same as $G_{X}$ except
that the cliques are replaced by star centered at a newly introduced vertex
(component) corresponding to the newly introduced excised edges in
$X^{\prime}$. The newly introduced edges form a 3-connected component
themselves with one virtual edge corresponding to each edge of the clique they
replace.

We list down the properties of the tree $T_{X}$ for further reference. (1) For
every node in $t\in T_{X}$, there is exactly one 3-connected component in
$X^{\prime}$. We denote this by $c_{t}$. (2) For every edge $e=(u,v)\in
T_{X}$, there are exactly two virtual edges, one each in the 3-connected
components $c_{u}$ and $c_{v}$. We call these virtual edges as the twin edges
of each other. (3) For any given graph $X$, $T_{X}$ is unique up to
isomorphism (since $G_{X}$ is unique [HT73]). In addition, $T_{X}$ can be
obtained from $G_{X}$ in polynomial time.

In the following claim, we prove that this surgery in the graphs does not
affect the existence of 2-isomorphisms.

######  Claim 5.5.

$X_{1}\cong_{2}X_{2}\iff X_{1}^{\prime}\cong_{2}X_{2}^{\prime}$.

###### Proof.

Suppose $X_{1}\cong_{2}X_{2}$, via a bijection $\phi:E_{1}\to E_{2}$. This
induces a map $\psi$ between the sets of 3-connected components of $X_{1}$ and
$X_{2}$. By theorem 5.4, for every 3-connected component $c$ of $X_{1}$,
$c\cong\psi(c)$ (via say $\tau_{c}$; when $c$ is clear from the context we
refer to it as $\tau$).

We claim that $\psi$ is an isomorphism between $G_{1}$ and $G_{2}$. To see
this, consider an edge $e=(u,v)\in T_{1}$. This corresponds to two 3-connected
components $c_{u}$ and $c_{v}$ of $X_{1}$ which share a separating pair
$s_{1}$. The 3-connected components $\psi(c_{u})$ and $\psi(c_{v})$ must share
a separating pair say $s_{2}$; otherwise, the cycles spanning across $c_{u}$
and $c_{v}$ will not be preserved by $\phi$ which contradicts the fact that
$\phi$ is a 2-isomorphism. Hence $(\psi(c_{u}),\psi(c_{v}))$ correspond to an
edge in $G_{2}$. Therefore, $\psi$ is an isomorphism between $G_{1}$ and
$G_{2}$. In fact, this also gives an isomorphism between $T_{1}$ and $T_{2}$,
which in turn gives a map between the excised pairs of $X_{1}$ and $X_{2}$. To
define the 2-isomorphism between $X_{1}^{\prime}$ and $X_{2}^{\prime}$, we
extend the map $\psi$ to the excised edges.

To argue the reverse direction, let $X_{1}^{\prime}\cong_{2}X_{2}^{\prime}$
via $\psi$. In a very similar way, this gives an isomorphism between $T_{1}$
and $T_{2}$. The edge map of this isomorphism gives the map between the
excised pairs. Restricting $\psi$ to the edges of $X_{1}$ gives the required
2-isomorphism between $X_{1}$ and $X_{2}$. This is because, the cycles of
$X_{1}$($X_{2}$) are anyway contained in $X_{1}^{\prime}$ ($X_{2}^{\prime}$),
and the excised pairs does not interfere in the mapping. ∎

Thus it is sufficient to give an algorithm to test if
$X_{1}^{\prime}\cong_{2}X_{2}^{\prime}$, which we describe as follows.

Input: 2-connected graphs $X_{1}^{\prime}$ and $X_{2}^{\prime}$ and tree of
3-connected components $T_{1}$ and $T_{2}$.
Output:Yes if $X_{1}^{\prime}\cong_{2}X_{2}^{\prime}$, and No otherwise.
Algorithm:
Notation: $\mbox{\sc code}(T)$ denotes the canonical label333When $T$ is
coloured, $\mbox{\sc code}(T)$ is the code of the tree obtained after
attaching the necessary gadgets to the coloured nodes. Notice that even after
colouring, the graph is still a tree. In addition, for any $T$, $\mbox{\sc
code}(T)$ can be computed in ${\mathsf{L}}$ [Lin92]. for a tree $T$.

  1. 1.

Initialize $T_{1}^{\prime}=T_{1}$, $T_{2}^{\prime}=T_{2}$.

  2. 2.

Repeat

    1. (a)

Set $T_{1}=T_{1}^{\prime}$, $T_{2}=T_{2}^{\prime}$.

    2. (b)

For each edge $e=(u,v)\in T_{i}$, $i\in\\{1,2\\}$:

Let $T_{i}(e,u)$ and $T_{i}(e,v)$ be subtrees of $T_{i}$ obtained by deleting
the edge $e$, containing $u$ and $v$ respectively.

Colour virtual edges corresponding to the separating pairs in the components
$c_{u}$ and $c_{v}$ with the set $\\{\mbox{\sc code}(T_{i}(e,u)),\mbox{\sc
code}(T_{i}(e,v))\\}$. From now on, $c_{t}$ denotes the coloured 3-connected
component corresponding to node $t\in T_{1}\cup T_{2}$.

    3. (c)

Let $S_{1}$ and $S_{2}$ be the set of coloured 3-connected components of
$X_{1}^{\prime}$ and $X_{2}^{\prime}$ and let $S=S_{1}\cup S_{2}$. Using
queries to GI (see observation 5.8) find out the isomorphism classes in $S$.
Let $C_{1},\ldots,C_{q}$ denote the isomorphism classes.

    4. (d)

Colour each node $t\in T_{i}$, $i\in\\{1,2\\}$, with colour $\ell$ if
$c_{t}\in C_{\ell}$. (This gives two coloured trees $T_{1}^{\prime}$ and
$T_{2}^{\prime}$.)

Until ($\mbox{\sc code}(T_{i})\neq\mbox{\sc code}(T_{i}^{\prime})$, $\forall
i\in\\{1,2\\}$)

  3. 3.

Check if $T_{1}^{\prime}\cong T_{2}^{\prime}$ preserving the colours. Answer
Yes if $T_{1}^{\prime}\cong T_{2}^{\prime}$, and No otherwise.

First we prove that the algorithm terminates in linear number of iterations of
the repeat-until loop. Let $q_{i}$ denote the number of isomorphism classes of
the set of the coloured 3-connected components after the $i^{th}$ iteration.
We claim that, if the termination condition is not satisfied, then
$|q_{i}|>|q_{i-1}|$. To see this, suppose the termination is not satisfied.
This means that the coloured tree $T_{1}^{\prime}$ is different from $T_{1}$.
This can happen only when the colour of a 3-connected component $c_{v}$, $v\in
T_{1}\cup T_{2}$ changes. In addition, this can only increase the isomorphism
classes. Thus $|q_{i}|>|q_{i-1}|$. Since $q$ can be at most $2n$, this shows
that the algorithm exits the loop after at most $2n$ steps.

Now we prove the correctness of the algorithm. We follow the notation
described in the algorithm.

######  Lemma 5.6.

$X_{1}^{\prime}\cong_{2}X_{2}^{\prime}$. $\iff$ $T_{1}^{\prime}\cong
T_{2}^{\prime}$.

###### Proof.

($\Rightarrow$) Suppose $X_{1}^{\prime}\cong_{2}X_{2}^{\prime}$, via a
bijection $\phi:E_{1}\to E_{2}$. This induces a map $\psi$ between the sets of
3-connected components of $X_{1}^{\prime}$ and $X_{2}^{\prime}$. By theorem
5.4, for every 3-connected component $c$ of $X_{1}^{\prime}$, $c\cong\psi(c)$
(via say $\tau_{c}$; when $c$ is clear from the context we refer to it as
$\tau$).

We claim that $\psi$ is an isomorphism between $T_{1}$ and $T_{2}$. To see
this, consider an edge $e=(u,v)\in T_{1}$. This corresponds to two 3-connected
components $c_{u}$ and $c_{v}$ of $X_{1}^{\prime}$ which share a separating
pair $s_{1}$. The 3-connected components $\psi(c_{u})$ and $\psi(c_{v})$ must
share a separating pair say $s_{2}$; otherwise, the cycles spanning across
$c_{u}$ and $c_{v}$ will not be preserved by $\phi$ which contradicts the fact
that $\phi$ is a 2-isomorphism. Hence $(\psi(c_{u}),\psi(c_{v}))$ correspond
to an edge in $T_{2}$. Therefore, $\psi$ is an isomorphism between $T_{1}$ and
$T_{2}$. So in what follows, we interchangeably use $\psi$ to be a map between
the set of 3-connected components as well as between the vertices of the tree.
Note that $\psi$ also induces (and hence denotes) a map between the edges of
$T_{1}$ and $T_{2}$.

Now we prove that $\psi$ preserves the colours attached to $T_{1}$ and $T_{2}$
after all iterations of the repeat-until loop in step 2. To simplify the
argument, we do it for the first iteration and the same can be carried forward
for any number of iterations. Let $T_{1}^{\prime}$ and $T_{2}^{\prime}$ be the
coloured trees obtained after the first iteration. We argue that $\psi$ itself
is an isomorphism between $T_{1}^{\prime}$ and $T_{2}^{\prime}$.

To this end, we prove that for any vertex $u$ in $T_{1}$,
$c_{u}\cong\psi(c_{u})$ even after colouring as in step 2b. That is, the map
preserves the colouring of the virtual edges in step 2b.

Consider any virtual edge $f_{1}$ in $c_{u}$, we know that $f_{2}=\tau(f_{1})$
is a virtual edge in $\psi(c_{u})$. Let $e_{1}=(u_{1},v_{1})$ and
$e_{2}=(u_{2},v_{2})$ be the tree edges in $T_{1}$ and $T_{2}$ corresponding
to $f_{1}$ and $f_{2}$ respectively. We know that, $e_{1}=\psi(e_{2})$. Since
$T_{1}\cong T_{2}$ via $\psi$, we have

$\left\\{\mbox{\sc code}(T_{1}(e_{1},u_{1})),\mbox{\sc
code}(T_{1}(e_{1},v_{1}))\right\\}=\left\\{\mbox{\sc
code}(T_{2}(e_{2},u_{2})),\mbox{\sc code}(T_{2}(e_{2},v_{2}))\right\\}.$

Thus, in Step 2b, the virtual edges $f_{1}$ and $f_{2}$ get the same colour.
Therefore, $c_{u}$ and $\psi(c_{u})$ belong to the same colour class after
step 2b. Hence $\psi$ is an isomorphism between $T_{1}^{\prime}$ and
$T_{2}^{\prime}$.

($\Leftarrow$) First, we recall some definitions needed in the proof. A center
of a tree $T$ is defined as a vertex $v$ such that $\max_{u\in T}d(u,v)$ is
minimized at $v$, where $d(u,v)$ is the number of edges in the unique path
from $u$ to $v$. It is known [Har69] that every tree $T$ has a center
consisting of a single vertex or a pair of adjacent vertices. The minimum
achieved at the center is called the height of the tree, denoted by $ht(T)$.

######  Claim 5.7.

Let $\psi$ be a colour preserving isomorphism between $T_{1}^{\prime}$ and
$T_{2}^{\prime}$, and $\chi_{t}$ is an isomorphism between the 3-connected
components $c_{t}$ and $c_{\psi(t)}$. Then,
$X_{1}^{\prime}\cong_{2}X_{2}^{\prime}$ via a map $\sigma$ such that $\forall
t\in T_{1}^{\prime}$, $\forall e\in c_{t}\cap E_{1}:\sigma(e)=\chi_{t}(e)$
where $E_{1}$ is the set of edges in $X_{1}^{\prime}$.

###### Proof.

The proof is by induction on height of the trees
$h=ht(T_{1}^{\prime})=ht(T_{2}^{\prime})$, where the height (and center) is
computed with respect to the underlying tree ignoring colours on the vertices.

Base case is when $h=0$; that is, $T_{1}^{\prime}$ and $T_{2}^{\prime}$ have
just one node (3-connected component) without any virtual edges. Simply define
$\sigma=\chi$. By Theorem 5.4, this gives the required 2-isomorphism.

Suppose that if $h=ht(T_{1}^{\prime})=ht(T_{2}^{\prime})<k$, the above claim
is true. For the induction step, suppose further that $T_{1}^{\prime}\cong
T_{2}^{\prime}$ via $\psi$, and $ht(T_{1}^{\prime})=ht(T_{2}^{\prime})=k$.
Notice that $\psi$ should map the center(s) of $T_{1}$ to that of $T_{2}$. We
consider two cases (we present one case here, and the other in the appendix).

In the first case, $T_{1}^{\prime}$ and $T_{2}^{\prime}$ have unique centers
$\alpha$ and $\beta$. It is clear that $\psi(\alpha)=\beta$. Let $c_{1}$ and
$c_{2}$ be the corresponding coloured (as in step 2b) 3-connected components.
Therefore, there is a colour preserving isomorphism $\chi=\chi_{\alpha}$
between $c_{\alpha}$ and $c_{\beta}$. Let $f_{1},\ldots f_{k}$ be the virtual
edges in $c_{\alpha}$ corresponding to the tree edges
$e_{1}=(\alpha,v_{1}),\ldots,e_{k}=(\alpha,v_{k})$ where $v_{1},\ldots,v_{k}$
are neighbors of $\alpha$ in $T_{1}^{\prime}$. Denote $\psi(e_{i})$ by
$e_{i}^{\prime}$, and $\psi(v_{i})$ by $v_{i}^{\prime}$.

Observe that only virtual edges are coloured in the 3-connected components in
step 2b while determining their isomorphism classes. Therefore, for each $i$,
$\chi(f_{i})$ will be a virtual edge in $c_{\beta}$, and in addition, with the
same colour as $f_{i}$. That is,

$\left\\{\mbox{\sc code}(T_{1}(e_{i},\alpha)),\mbox{\sc
code}(T_{1}(e_{i},v_{i}))\right\\}=\left\\{\mbox{\sc
code}(T_{2}(e_{i}^{\prime},\beta)),\mbox{\sc
code}(T_{2}(e_{i}^{\prime},v_{i}^{\prime})))\right\\}$.

Since $\alpha$ and $\beta$ are the centers of $T_{1}^{\prime}$ and
$T_{2}^{\prime}$, it must be the case that in the above set equality,
$\mbox{\sc code}(T_{1}(e_{i},v_{i}))$ $=$ $\mbox{\sc
code}(T_{2}(e_{i}^{\prime},v_{i}^{\prime}))$. From the termination condition
of the algorithm, this implies that $\mbox{\sc
code}(T_{1}^{\prime}(e_{i},v_{i}))=\mbox{\sc
code}(T_{2}^{\prime}(e_{i}^{\prime},v_{i}^{\prime}))$. Hence,
$T_{1}^{\prime}(e_{i},v_{i})\cong
T_{2}^{\prime}(e_{i}^{\prime},v_{i}^{\prime})$. In addition,
$ht(v_{i})=ht(v_{i}^{\prime})<k$. Let $X_{f_{i}}^{\prime}$ and
$X_{\chi(f_{i})}^{\prime}$ denote the subgraphs of $X_{1}^{\prime}$ and
$X_{2}^{\prime}$ corresponding to $T_{1}^{\prime}(e_{i},v_{i})$ and
$T_{2}^{\prime}(e_{i}^{\prime},v_{i}^{\prime})$ respectively. By induction
hypothesis, the graphs $X_{f_{i}}^{\prime}$ and $X_{\chi(f_{i})}^{\prime}$ are
2-isomorphic via $\sigma_{i}$ which agrees with the corresponding $\chi_{t}$
for $t\in T_{1}^{\prime}(e_{i},v_{i})$. Define $\pi_{i}$ as a map between the
set of all edges, such that it agrees with $\sigma_{i}$ on all edges of
$X_{f(i)}^{\prime}$ and with $\chi_{t}$ (for $t\in
T_{1}^{\prime}(e_{i},v_{i})$) on the coloured virtual edges.

We claim that $\pi_{i}$ must map the twin-edge of $f_{i}$ to twin-edge of
$\tau(f_{i})$. Suppose not. By the property of the colouring, this implies
that there is a subtree of $T_{1}^{\prime}(e_{i},v_{i})$ isomorphic to
$T_{1}^{\prime}\setminus T_{1}^{\prime}(e_{i},v_{i})$. This contradicts the
assumption that $c_{\alpha}$ is the center of $T_{1}^{\prime}$.

For each edge $e\in E_{1}$, define $\sigma(e)$ to be $\chi(e)$ when $e\in
c_{\alpha}$ and to be $\pi_{i}(e)$ when $e\in E_{f_{i}}~{}(\textrm{edges of
$X_{f_{i}}$})$. From the above argument, $\chi=\chi_{\alpha}$ and $\sigma_{i}$
indeed agrees on where it maps $f_{i}$ to. This ensures that every cycle
passing through the separating pairs of $c_{\alpha}$ gets preserved. Thus
$\sigma$ is a 2-isomorphism between $X_{1}^{\prime}$ and $X_{2}^{\prime}$.

For case 2, let $T_{1}^{\prime}$ and $T_{2}^{\prime}$ have two centers
$(\alpha_{1},\alpha_{2})$ and $(\beta_{1},\beta_{2})$ respectively. It is
clear that $\psi(\\{\alpha_{1},\alpha_{2}\\})=\\{\beta_{1},\beta_{2}\\}$.
Without loss of generality, we assume that $\psi(\alpha_{1})=\beta_{1}$,
$\psi(\alpha_{2})=\beta_{2}$. Therefore, there are colour preserving
isomorphisms $\chi_{1}$ from $c_{\alpha_{1}}$ to $c_{\beta_{1}}$ and
$\chi_{2}$ from $c_{\alpha_{2}}$ and $c_{\beta_{2}}$. Define $\chi(e)$ as
follows:

$\chi(e)=\left\\{\begin{array}[]{ll}\chi_{1}(e)&~{}~{}e\in c_{\alpha_{1}}\\\
\chi_{2}(e)&~{}~{}e\in c_{\alpha_{2}}\end{array}\right.$
$c_{\alpha}=\cup_{i}c_{\alpha_{i}},~{}~{}~{}c_{\beta}=\cup_{i}c_{\beta_{i}}$

With this notation, we can appeal to the proof in the case 1, and construct
the 2-isomorphism $\sigma$ between $X_{1}^{\prime}$ and $X_{2}^{\prime}$.

∎

This completes the proof of correctness of the algorithm (Lemma 5.6).

∎

To complete the proof of Theorem 5.3, we need the following observation,

######  Observation 5.8.

Coloured-GMI for 3-connected graphs reduces to GI.

Observing that the above construction does not use non-planar gadgets, we get
the following.

######  Corollary 5.9.

Given two planar matroids, $M(X_{1})$ and $M(X_{2})$, testing if
$M(X_{1})\cong M(X_{2})$ can be performed in ${\mathsf{P}}$.

Now we give a polynomial time many-one reduction from $\mbox{\sc MI}_{b}$ to
GMI. Let $M_{1}$ and $M_{2}$ be two matroids of rank $b$ over the ground set
$S_{1}$ and $S_{2}$. Let ${\mathcal{C}}_{1}$ and ${\mathcal{C}}_{2}$
respectively denote the set of cycles of $M_{1}$ and $M_{2}$. Note that
$|{\mathcal{C}}_{1}|,|{\mathcal{C}}_{2}|\leq m^{b+1}$.

Define graphs $X_{1}=(V_{1},E_{1})$ (respectively for $X_{2}=(V_{2},E_{2})$)
as follows. For each circuit $c=\\{s_{i_{1}},\ldots,s_{i_{\ell}}\\}\subseteq
S_{1}$ in $M_{1}$, $X_{1}$ contains a simple cycle
$\\{e(c,s_{i_{1}}),\ldots,e(c,s_{i_{\ell}})\\}$. Now pairwise interconnect all
the endpoints of the edges corresponding to each of the ground set elements
(these edges form a clique), and colour these edges as red and the remaining
edges as blue. Now we claim the following.

######  Lemma 5.10.

$M_{1}\cong M_{2}$ if and only if $X_{1}\cong_{2}X_{2}$.

###### Proof.

Suppose $M_{1}\cong M_{2}$, via a map $\phi:S_{1}\to S_{2}$. This gives a map
$\psi$ between the blue edges of the graphs $X_{1}$ and $X_{2}$ which
preserves blue cycles. Now we extend this to the red edges. Take a red edge
$r$, there are two blue edges $e_{1}$ and $e_{2}$ which share an endpoint with
$r$. We know that $e_{1}$ and $e_{2}$ are corresponding to the same ground set
element (say $s$). Thus $\psi(e_{1})$ and $\psi(e_{2})$ correspond to the same
ground set element $\phi(s)$, and hence shares a red edge in $X_{2}$. Thus
$\psi$ can be extended to preserve the red edges. Hence $X_{1}\cong_{2}X_{2}$.

Conversely, suppose $X_{1}\cong_{2}X_{2}$ via $\psi:E_{1}\to E_{2}$. Define
$\phi:S_{1}\to S_{2}$ as follows: For $s\in S_{1}$ let $R_{s}$ denote the
clique in $X_{1}$ corresponding to $s$. $R_{s}$ is either a single blue edge
or a clique on at least $4$ vertices (in the latter case it is 3-connected).
Thus $\psi$ should map $R_{s}$ to $R^{\prime}_{s^{\prime}}$ for some
$s^{\prime}$ in $S_{2}$.. Define $\phi(s)=s^{\prime}$. Now we argue that
$\psi$ is an isomorphism between $M_{1}$ and $M_{2}$. Let
$c=\\{s_{1},\ldots,s_{\ell}\\}\subseteq S_{1}$ be a cycle in $M_{1}$.

$\displaystyle c\in{\mathcal{C}}_{1}$ $\displaystyle\iff$
$\displaystyle\bigcap_{i}\psi(R_{s_{i}})\textrm{ is a {\sc blue} cycle in
$X_{1}$}$ $\displaystyle\iff$
$\displaystyle\bigcap_{i}\psi(R^{\prime}_{s^{\prime}_{i}})\textrm{ is a {\sc
blue} cycle in $X_{2}$}$ $\displaystyle\iff$
$\displaystyle\phi(c)\in{\mathcal{C}}_{2}$

∎

From the above construction, we have the following theorem.

######  Theorem 5.11.

$\mbox{\sc MI}_{b}\leq^{p}_{m}\mbox{\sc GMI}$.

Thus we have,

######  Theorem 5.12.

$\mbox{\sc GI}\equiv^{p}_{T}\mbox{\sc GMI}\equiv^{p}_{T}\mbox{\sc
MI}_{b}\equiv^{p}_{T}\mbox{\sc LMI}_{b}$

##  6 Matroid Automorphism Problem

With any isomorphism problem, there is an associated automorphism problem i.e,
to find a generating set for the automorphism group of the underlying object.
Relating the isomorphism problem to the corresponding automorphism problem
gives access to algebraic tools associated with the automorphism groups. In
the case of graphs, studying automorphism problem has been fruitful.(e.g. see
[Luk80, BGM82, AK02].) In this section we turn our attention to Matroid
automorphism problem.

An automorphism of a matroid $M=(S,{\mathcal{C}})$ (where $S$ is the ground
set and ${\mathcal{C}}$ is the set of circuits) is a permutation $\phi$ of
elements of $S$ such that $\forall C\subseteq
S,~{}C\in{\mathcal{C}}\iff\phi(C)\in{\mathcal{C}}$. $Aut(M)$ denotes the group
of automorphisms of the matroid $M$. When the matroid is graphic we denote by
$Aut(X)$ and $Aut(M_{X})$ the automorphism group of the graph and the graphic
matroid respectively.

To begin with, we note that given a graph $X$, and a permutation $\pi\in
S_{m}$, it is not clear apriori how to check if $\pi\in Aut(M_{X})$
efficiently. This is because we need to ensure that $\pi$ preserves all the
simple cycles, and there could be exponentially many of them. Note that such a
membership test (given a $\pi\in S_{n}$) for $Aut(X)$ can be done easily by
testing whether $\pi$ preserves all the edges. We provide an efficient test
for this problem.

We use the notion of a cycle bases of $X$. A cycle basis of a graph $X$ is a
minimal set of cycles $\mathcal{B}$ of $X$ such that every cycle in $X$ can be
written as a linear combination (viewing every cycle as a vector in
$\mbox{$\mathbb{F}$}_{2}^{m}$) of the cycles in ${\mathcal{B}}$. Let
$\mathscr{B}$ denote the set of all cycle basis of the graph $X$.

######  Lemma 6.1.

Let $\pi\in S_{n}$,
$\exists{\mathcal{B}}\in{\mathscr{B}}:\pi({\mathcal{B}})\in{\mathscr{B}}\implies\forall{\mathcal{B}}\in{\mathscr{B}}:\pi({\mathcal{B}})\in{\mathscr{B}}$

###### Proof.

Let ${\mathcal{B}}=\\{b_{1},\ldots b_{\ell}\\}\in{\mathscr{B}}$ such that
$\pi({\mathcal{B}})=\\{\pi(b_{1}),\ldots,\pi(b_{\ell})\\}$ is a cycle basis.
Now consider any other cycle basis
${\mathcal{B}}^{\prime}=\\{b_{1}^{\prime},\ldots,b_{k}^{\prime}\\}\in{\mathscr{B}}$.
Thus, $b_{i}=\sum_{j}\alpha_{j}b_{j}^{\prime}$. This implies,

$\pi(b_{i})=\sum_{j}\alpha_{j}\pi(b_{j}^{\prime}).$

Thus,
$\pi(B^{\prime})=\\{\pi(b_{1}^{\prime}),\ldots,\pi(b_{\ell}^{\prime})\\}$
forms a cycle basis. ∎

######  Lemma 6.2.

Let $\pi\in S_{m}$, and let ${\mathcal{B}}\in{\mathscr{B}}$, then $\pi\in
Aut(M_{X})\iff\pi({\mathcal{B}})\in{\mathscr{B}}$.

###### Proof.

Let ${\mathcal{B}}=\\{b_{1},\ldots,b_{\ell}\\}$ be the given cycle basis.

For the forward direction, suppose $\pi\in Aut(M_{X})$. That is, $C\subseteq
E$ is a cycle in $X$ if and only if $\pi(C)$ is also a cycle in $X$. Let $C$
be any cycle in $X$, and let $D=\pi^{-1}(C)$. Since
${\mathcal{B}}\in{\mathscr{B}}$, we can write, $D=\sum_{i}\alpha_{i}b_{i}$,
and hence $C=\sum_{i}\alpha_{i}\pi(b_{i})$. Hence $\pi({\mathcal{B}})$ forms a
cycle basis for $X$.

For the reverse direction, suppose $\pi({\mathcal{B}})$ is a cycle basis of
$X$. Let $C$ be any cycle in $X$. We can write $C=\sum_{i}\alpha_{i}b_{i}$.
Hence, $\pi(C)=\sum_{i}\alpha_{i}\pi(b_{i})$. As $\pi$ is a bijection, we have
$\pi(b_{i}\cap b_{j})=\pi(b_{i})\cap\pi(b_{j})$. Thus $\pi(C)$ is also a cycle
in $X$. Since $\pi$ extends to a permutation on the set of cycles, we get that
$C$ is a cycle if and only if $\pi(C)$ is a cycle. ∎

Using Lemmas 6.1 and 6.2 it follows that, given a permutation $\pi$, to test
if $\pi\in Aut(M_{X})$ it suffices to check if for a cycle basis
${\mathcal{B}}$ of $X$, $\pi({\mathcal{B}})$ is also a cycle basis. Given a
graph $X$ a cycle basis ${\mathcal{B}}$ can be computed in polynomial time
(see e.g, [Hor87]). Now it suffices to show:

######  Lemma 6.3.

Given a permutation $\pi\in S_{m}$, and a cycle basis
${\mathcal{B}}\in{\mathscr{B}}$, testing whether $\pi({\mathcal{B}})$ is a
cycle basis, can be done in polynomial time.

###### Proof.

To check if $\pi({\mathcal{B}})$ is a cycle basis, it is sufficient to verify
that every cycle in ${\mathcal{B}}=\\{b_{1},\ldots,b_{\ell}\\}$ can be written
as a $\mbox{$\mathbb{F}$}_{2}$-linear combination of the cycles in
${\mathcal{B}}^{\prime}=\\{b_{1}^{\prime},\ldots,b_{\ell}^{\prime}\\}=\pi({\mathcal{B}})$.
This can be done as follows.

For $b_{i}\in{\mathcal{B}}$, let $\pi(b_{i})=b_{i}^{\prime}$. View $b_{i}$ and
$b_{i}^{\prime}$ as vectors in $\mbox{$\mathbb{F}$}_{2}^{m}$. Let $b_{ij}$
(resp. $b_{ij}^{\prime}$) denote the $j^{\mathrm{th}}$ component of $b_{i}$
(resp. $b_{i}^{\prime}$). Construct the set of linear equations,
$b_{ij}^{\prime}=\sum_{b_{k}\in{\mathcal{B}}}x_{ik}b_{kj}$ where $x_{ik}$ are
unknowns. There are exactly $\ell$ $b_{i}^{\prime}$s and each of them gives
rise to exactly $m$ equations like this. This gives a system $I$ of $\ell m$
linear equations in $\ell^{2}$ unknowns such that, $\pi(B)$ is a cycle basis
if and only if $I$ has a non-trivial solution. This test can indeed be done in
polynomial time. ∎

This gives us the following:

######  Theorem 6.4.

Given any $\pi\in S_{m}$, the membership test for $\pi$ in $Aut(M_{X})$ is in
${\mathsf{P}}$.

Notice that similar arguments can also give another proof of Proposition 5.2.
As in the case of graphs, we can define automorphism problems for matroids.

$\mbox{\sc Matroid Automorphism}(\mbox{\sc MA})$: Given a matroid $M$ as
independent set oracle, compute a generating set for $Aut(M)$.

We define GMA and LMA as the corresponding automorphism problems for graphic
and linear matroids, when the input is a graph and matrix respectively. Using
the colouring techniques from Section 4, we prove the following equivalence.

######  Theorem 6.5.

$\mbox{\sc LMI}\equiv_{T}^{p}\mbox{\sc LMA}$, and $\mbox{\sc
GMI}\equiv_{T}^{p}\mbox{\sc GMA}$.

###### Proof.

This proof follows a standard idea due to Luks [Luk93]. We argue the forward
direction as follows. Given two matrices $M_{1}$ and $M_{2}$, form the new
matrix $M$ as,

$M=\begin{bmatrix}M_{1}&0\\\ 0&M_{2}\end{bmatrix}$

Now using queries to LMA construct the generating set of $Aut(M)$. Check if at
least one of the generators map the columns in $M$ corresponding to columns of
$M_{1}$ to those corresponding to the columns of $M_{2}$.

To see the other direction, we use the colouring idea, and the rest of the
details is standard. The idea is to find the orbits of each element of the
ground set as follows: For every element of $e\in S$, for each $f\in S$,
colour $e$ and $f$ by the same colour to obtain coloured matroids $M_{1}$ and
$M_{2}$. Now by querying to LMI we can check if $f$ is in the orbit of $e$.
Thus we can construct the orbit structure of $Aut(M)$ and hence compute a
generating set.

Using similar methods we can prove $\mbox{\sc GMI}\equiv_{T}^{p}\mbox{\sc
GMA}$. ∎

##  7 Conclusion and Open Problems

We studied the matroid isomorphism problem under various input representations
and restriction on the rank of the matroid. We proved that graph isomorphism,
graphic matroid isomorphism and bounded rank version of matroid isomorphism
are all polynomial time equivalent.

In addition, we find it interesting that in the bounded rank case, $\mbox{\sc
MI}_{b}$ and $\mbox{\sc LMI}_{b}$ are equivalent, though there exist matroids
of bounded rank which are not representable over any field. Some of the open
questions that we see are as follows:

  * •

Our results provide new possibilities to attack the graph isomorphism problem.
For example, it will be interesting to prove a ${\mathsf{co}}{\mathsf{NP}}$
upper bound for $\mbox{\sc LMI}_{b}$. Note that this will imply that
$\mbox{\sc GI}\in{\mathsf{NP}}\cap{\mathsf{co}}{\mathsf{NP}}$. Similarly, are
there special cases of GMI (other than what is translated from the bounds for
GI) which can be solved in polynomial time?

  * •

The representations of the matroid in the definition of LMI is over fields of
size at least $m$ and at most ${\mathsf{poly}}(m)$, where $m$ is the size of
the ground set of the matroid. This is critically needed for the observation
of ${\mathsf{co}}{\mathsf{NP}}$-hardness. One could ask if the problem is
easier over fixed finite fields independent on the input. However, we note
that, by our results, it follows that this problem over
$\mbox{$\mathbb{F}$}_{2}$ is already hard for GI. It will still be interesting
to give a better (than the trivial $\Sigma_{2}$) upper bound for linear
matroids represented over fixed finite fields (even for
$\mbox{$\mathbb{F}$}_{2}$).

  * •

Can we use the colouring technique of linear matroid isomorphism to reduce the
general instances of linear matroid isomorphism to isomorphism testing of
“simpler components” of the matroid?

  * •

Can we make the reduction from GMI to GI many-one? Can we improve the
complexity of this reduction in the general case?

##  8 Acknowledgements

We thank V. Arvind and Meena Mahajan for providing us with useful inputs and
many insightful discussions, James Oxley for sharing his thoughts while
responding to our queries about matroid isomorphism. We also thank the
anonymous referees for providing us many useful pointers to the literature.

## References

  * [AK02] Vikraman Arvind and Piyush P. Kurur.  Graph isomorphism is in SPP.  In FOCS, pages 743–750, 2002.
  * [AT05] Vikraman Arvind and Jacobo Torán.  Isomorphism testing: Perspective and open problems.  Bulletin of the EATCS, 86:66–84, 2005.
  * [Bab78] Làszlò Babai.  Vector Representable Matroids of Given Rank with Given Automorphism Group.  Discrete Math., 24:119–125, 1978.
  * [BGM82] László Babai, D. Yu. Grigoryev, and David M. Mount.  Isomorphism of graphs with bounded eigenvalue multiplicity.  In STOC, pages 310–324, 1982.
  * [CE80] William H Cunningham and Jack Edmonds.  A Combinatorial Decomposition Theory.  Canadian Journal of Mathematics, 17:734–765, 1980.
  * [DLN08] Samir Datta, Nutan Limaye, and Prajakta Nimbhorkar.  3-connected planar graph isomorphism is in log-space.  In FSTCS, 2008.  To appear.
  * [Gol08] Oded Goldreich.  Computational Complexity: A Conceptual Perspective.  Cambridge University Press, 2008.
  * [Har69] F. Harary.  Graph theory.  Addison Wesley, 1969.
  * [Hli07] Petr Hlinený.  Some hard problems on matroid spikes.  Theory of Computing Systems, 41(3):551–562, 2007.
  * [Hor87] Joseph Douglas Horton.  A polynomial-time algorithm to find the shortest cycle basis of a graph.  SIAM Journal of Computing, 16(2):358–366, 1987.
  * [HT73] J.E. Hopcroft and R.E. Tarjan.  Dividing a graph into triconnected components.  SIAM Journal of Computing, 2(3):135–158, 1973.
  * [Kha95] Leonid Khachiyan.  On the complexity of approximating extremal determinants in matrices.  Journal of Complexity, 11(1):138–153, 1995.
  * [KST93] Johannes Köbler, Uwe Schöning, and Jacobo Torán.  The graph isomorphism problem: its structural complexity.  Birkhauser Verlag, Basel, Switzerland, Switzerland, 1993.
  * [Lin92] Steven Lindell.  A logspace algorithm for tree canonization (extended abstract).  In STOC, pages 400–404, 1992.
  * [Luk80] Eugene M. Luks.  Isomorphism of graphs of bounded valence can be tested in polynomial time.  In FOCS, pages 42–49, 1980.
  * [Luk93] Eugene.M Luks.  Permutation groups and polynomial-time computation, volume 11 of DIMACS, pages 139–175.  1993\.
  * [May08] Dillon Mayhew.  Matroid complexity and nonsuccinct descriptions.  SIAM Journal of Discrete Mathematics, 22(2):455–466, 2008.
  * [OW02] James Oxley and Dominic Welsh.  Chromatic, flow and reliability polynomials: The complexity of their coefficients.  Combinatorics, Probability and Computing, 11:403–426, 2002.
  * [Oxl92] James G. Oxley.  Matroid theory.  Oxford University Press, New York, 1992.
  * [Sch99] U. Schöning.  Probablistic Complexity Classes and Lowness.  JCSS, 39:84–100, 1999.
  * [Tor04] Jacobo Toran.  On the Hardness of Graph Isomorphism.  SIAM Jl. of Comp., 33(5):1093–1108, 2004.
  * [Tru80] Klaus Truemper.  On Whitney’s 2-isomorphism theorem for graphs.  Jl. of Graph Theory, pages 43–49, 1980.
  * [TW08] Thomas Thierauf and Fabian Wagner.  The isomorphism problem for planar 3-connected graphs is in unambiguous logspace.  In STACS, pages 633–644, 2008.
  * [Whi32] Hassler Whitney.  Congruent graphs and connectivity of graphs.  American Journal of Mathematics, 54(1):150–168, 1932.
  * [Whi33] Hassler Whitney.  2-isomorphic graphs.  American Journal of Mathematics, 55:245–254, 1933.
  * [Whi35] Hassler Whitney.  On the abstract properties of linear dependence.  American Journal of Mathematics, 57(3):509–533, 1935.

##  Appendix A Proof of Claim 3.7

Claim 3.7: [Bab78] For any graph $X$, any hyperplane of $St_{k}(X)$ is a
maximal set edges which share a common vertex (forms a star) in $X$, and these
are the only hyperplanes.

###### Proof.

To see the first part, note that since $k$ is at most the min-degree of the
graph, any maximal set of edges which forms a star is a hyperplane. To argue
that these are the only hyperplanes, suppose $H$ is a hyperplane whose edges
do not share a common vertex in $X$. Since any independent set cannot be a
hyperplane, $H$ has size at least $k$, and the rank of $H$ by definition is
$k-1$. Take any $k$ sized subset $S$ of $H$. It has to be a star (say at
vertex $v$), since otherwise $H$ will have rank $k$. Since $H$ by itself is
not a star, there is an edge $e$ which does not have $v$ as its end point. But
then, $H$ contains a $k$ sized subset which is not a star, and hence
independent. This is a contradiction. ∎

##  Appendix B 3-connected Coloured-GMI

By combining Lemma 4.1 with Theorem 5.4, we prove the following corollary
which we present although we do not need it explicitly in the paper.

######  Corollary B.1.

Let $X_{1}$ and $X_{2}$ be two 3-connected graphs with given edge colourings,
testing if there is a colour preserving 2-isomorphism between $X_{1}$ and
$X_{2}$, can be reduced to GI.

###### Proof.

We follow the notation in the proof of Lemma 4.1. Let $X_{1}^{\prime}$ and
$X_{2}^{\prime}$ be the two graphs obtained from $X_{1}$ and $X_{2}$ by
attaching the colouring gadgets. Now we claim that
$X_{1}^{\prime}\cong_{2}X_{2}^{\prime}\iff X_{1}^{\prime}\cong
X_{2}^{\prime}$.

One direction is easy to see. $X_{1}^{\prime}\cong X_{2}^{\prime}\Rightarrow
X_{1}^{\prime}\cong_{2}X_{2}^{\prime}$. To see the other direction, suppose
$X_{1}^{\prime}\cong_{2}X_{2}^{\prime}$ via $\sigma$. By proof of Lemma 4.1
this induces a 2-isomorphism between $X_{1}$ and $X_{2}$, which in turn
induces an isomorphism $\tau$ between $X_{1}$ and $X_{2}$. Observe that $\tau$
also preserves colours on the edges of $X_{1}$ and $X_{2}$.

Let $\pi$ be the map between the vertices of $X_{1}^{\prime}$ and
$X_{2}^{\prime}$ induced by $\tau$. Note that $\pi$ is not defined on the new
vertices introduced by the colouring gadgets. However, $\pi$ already preserves
all the edges between $X_{1}^{\prime}$ and $X_{2}^{\prime}$ except the newly
introduced edges.

Since $\tau$ preserves edge colours in $X_{1}$, any coloured edge $e\in
X_{1}$, the paths $P_{e}$ and $P_{\tau(e)}$, introduced while constructing
$X_{1}^{\prime}$ and $X_{2}^{\prime}$ are of the same length. Hence the vertex
map $\pi$ can be extended to the vertices in these paths to an edge preserving
vertex map between $X_{1}^{\prime}$ and $X_{2}^{\prime}$. ∎

##  Appendix C A hardness result for GMI

We show that known hardness results of GI ([Tor04]) can be adapted to the case
of GMI. This is subsumed by the many-one reduction from GI to GMI. But we
state this observation here anyway.

######  Theorem C.1.

GMI is ${\mathsf{NL}}$-hard under ${\mathsf{AC}}^{0}$ many one reductions.

The hardness is proved using ideas similar to that in [Tor04]. We include the
details of this modified part of the proof.

Consider the graph $X(k)=(V,E)$ where,

$\displaystyle V$ $\displaystyle=$
$\displaystyle\\{x_{0},\ldots,x_{k-1},y_{0},\ldots,y_{k-1},z_{0},\ldots,z_{k-1}\\}$
$\displaystyle\cup\\{u_{i,j}~{}|~{}0\leq i,j\leq k-1\\}$ $\displaystyle E$
$\displaystyle=$ $\displaystyle\\{(x_{i},u_{i,j})~{}|~{}0\leq i,j\leq k-1\\}$
$\displaystyle\cup\\{(y_{j},u_{i,j})~{}|~{}0\leq i,j\leq k-1\\}$
$\displaystyle\cup\\{(u_{i,j},z_{i\oplus j})~{}|~{}0\leq i,j\leq k-1\\}$

The following is easy to verify for the above graph.

######  Observation C.2.

For $k\geq 3$, the graph $X(k)$ is 3-connected.

Toran [Tor04] argued that for any $a,b\in\\{0,\ldots,k-1\\}$ the graph $X(k)$
has a unique automorphism which maps vertices $x_{i}\to x_{a\oplus i}$ and
$y_{i}\to y_{b\oplus i}$, which also maps $z_{i}\to z_{i\oplus a\oplus b}$.
Combining this with Proposition 5.4, and the above observation, we get the
following lemma.

######  Lemma C.3.

For any $k\geq 3$, given any $a,b\in\\{0,\ldots,k-1\\}$, there exists a unique
automorphism for the matroid $M_{X(k)}$ which maps

$\displaystyle(x_{i},u_{i,j})$ $\displaystyle\to$ $\displaystyle(x_{i\oplus
a},u_{(i\oplus a,j)})$ $\displaystyle(y_{j},u_{i,j})$ $\displaystyle\to$
$\displaystyle(y_{i\oplus b},u_{(i,j\oplus a)})$
$\displaystyle(u_{i,j},z_{i\oplus j})$ $\displaystyle\to$
$\displaystyle(u_{i\oplus a,j\oplus b},z_{i\oplus j\oplus a\oplus b})$

######  Lemma C.4.

For $k\geq 3$, GMI is ${\mathsf{Mod}}_{k}{\mathsf{L}}$-hard under
${\mathsf{AC}}^{0}$ many-one reductions.

###### Proof.

Let $C$ be a circuit with ${\mathsf{Mod}}_{k}$ gates for $k\geq 3$. Without
loss of generality, we assume that each gate is of fan-in 2. We construct a
new graph $X$ as follows : For each gate $g$ in $C$, $X$ contains a copy of
the graph $X(k)$, denoted by $X_{g}$. Colour each edge of $X_{g}$ with colour
$g$ (see Lemma 4.1). If gate $g$ has $h_{1}$ and $h_{2}$ as its inputs
identify $x_{0},\ldots x_{k-1}$ and $y_{0},\ldots,y_{k-1}$ of $X_{g}$ with
$z_{0},\ldots,z_{k-1}$ of $X_{h_{1}}$ and $X_{h_{2}}$ respectively. Let $r$ be
the root gate of $C$, $g_{1},\ldots g_{m}$ be the gates which receive the
inputs directly, then the following claim can be verified by induction on the
circuit structure.

######  Claim C.5.

$C$ evaluates to $\ell\in\\{0,\ldots,k-1\\}$ on input $a_{1},\ldots,a_{n}$ if
and only if $M_{X}$ has an automorphism which maps, for the gate $g_{i}$
receiving the input $a_{j}$ as its ’x’ input, in $X_{g_{i}}$

$(x_{i},u_{i,t})\to(x_{i\oplus a_{j}},u_{(i\oplus a_{j},t)})$

for all $0\leq t\leq k-1$, and in $X_{r}$, for all $a\oplus b=\ell$, $j\oplus
t=i$,

$(u_{t,j},z_{i})\to(u_{t\oplus a,j\oplus b},z_{i\oplus\ell})$

∎

###### Proof.

(of theorem C.1) Using ideas from [Tor04], it is easy to see that we can write
an ${\mathsf{NL}}$ computation as a series ${\mathsf{Mod}}_{k}{\mathsf{L}}$
computations, for $3\leq k\leq 2n$. Thus, the theorem follows. ∎

The following corollary is immediate as in (Theorem 4.4, [Tor04]), using
Chinese remaindering, and the above reduction.

######  Corollary C.6.

Every ${\mathsf{Gap}}{\mathsf{L}}$-function is ${\mathsf{AC}}^{0}$ many-one
reducible to GMI.

##  Appendix D Testing Uniformity of Matroids

A problem of testing if a given matroid is uniform, is clearly as a special
case of the matroid isomorphism problem, where one of the matroid is uniform.
The problem is known to be ${\mathsf{co}}{\mathsf{NP}}$-complete as shown
below.

######  Proposition D.1.

Given a representable matroid of rank $k$ (input is a $k\times n$ matrix $A$),
the problem of checking if the matroid is uniform is
${\mathsf{co}}{\mathsf{NP}}$-complete. In other words, testing if the matroid
$M$ represented by columns of $A$ is isomorphic to $U_{k,n}$ is
${\mathsf{co}}{\mathsf{NP}}$-complete.

###### Proof.

This proof is due to Oxley and Welsh [OW02]. We make it more explicit. A set
of $n$ points in $d$ dimensions is linearly degenerate if there is a set of
$d$ points which is linearly dependent. In other words, the set of $n$ points
is said to be in general position if all subsets of size $d$ are linearly
independent. Khanchiyan [Kha95] proved that given $n$ points testing if they
are in general position is ${\mathsf{NP}}$-hard. Now notice that this exactly
answers the question of testing if the matroid is uniform. ∎