期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2014
卷号：2014
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：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 $\mathrm{L}$-complete. 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}$). 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
