Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

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 L-complete.
  2. For transversal matroids, when a basis of M is also given at the input, the problem can be shown to be NL-complete. A general upper bound for this case is the complexity of constructing a matching (RNC2P).
  3. For linear matroids representable over Q and Zp, we show that the problem characterizes LC=L and ModpL 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


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

This document last modified on: 10/14/2014 20:41:45