Chicago Journal of Theoretical Computer Science

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.


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

DOI: 10.4086/cjtcs.2014.005
© 2014 Raghavendra Rao B. V. and Jayalal Sarma
Creative Commons License Licensed under a Creative Commons Attribution License

[] Article 4 [] Article 6
[back] Volume 2014 [back] Published articles
[CJCTS home]