Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
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 L-complete.
- 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 (RNC2∩P).
- 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.
- 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
This document last modified on: 10/14/2014 20:41:45