### 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:
1. 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.
2. 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}$).
3. 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