Complexity of Testing Reachability in Matroids
B. V. Raghavendra Rao, Jayalal Sarma · Chicago Journal of Theoretical Computer Science · 2014
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 (RNC 2 \P). (3) For linear matroids representable over Q and Zp, we show that the problem characterizes L C=L and ModpL respectively, which provides the first characterizations of these classes in terms of reachability problems.