#

### Volume 2014

#### Article 5

Published by the Department of Computer Science, The University of Chicago.

#### Complexity of Testing Reachability in Matroids

B. V. Raghavendra Rao

Department of Computer Science and Engineering

Indian Institute of Technology, Madras

Chennai, 600 0636

India

`bvrr AT cse DOT iitm DOT ac DOT in`

and

Jayalal Sarma

Department of Computer Science and Engineering

Indian Institute of Technology, Madras

Chennai, 600 0636

India

`jayalal AT cse DOT iitm DOT ac DOT in`

*July 11, 2014*
#### Abstract

We extend the complexity theoretic framework of reachability
problems in graphs to the case of matroids. Given a matroid $M$ and
two elements $s$ and $t$ of the ground set, the reachability problem
is to test if there is a circuit in $M$ containing both $s$ and
$t$.
We show complexity characterizations for several important classes of
matroids. In particular, we show:
- For two important classes of matroids associated with
graphs, namely, graphic and bi-circular matroids we show that
the reachability problem is $\mathrm{L}$-complete.
- For transversal matroids, when a basis of $M$ is also given
at the input, the problem can be shown to be $\mathrm{NL}$-complete. A
general upper bound for this case is the complexity of
constructing a matching ($\mathrm{RNC^2} \cap \mathrm{P}$).
- For linear matroids representable over $\mathbb{Q}$ and $\mathbb{Z}_\mathrm{p}$, we show that
the problem characterizes $\mathrm{L}^{\mathrm{C = L}}$ and $\mathrm{Mod_p}\mathrm{L}$
respectively, which provides the first characterizations of
these classes in terms of reachability problems.

- The article:
**PDF** (397 KB)
- Source material: ZIP (259 KB)
**BibTeX** entry for this article (284 bytes)

Submitted January 22, 2012, revised June 7, 2014, published July 9, 2014.

Article 4
Article 6

Volume 2014
Published articles