# Complexity of Independence Oracle for Matroids

I am interested in the computational complexity of an independence Oracle for Matroids. In particular, I would like to know how efficiently such an Oracle can be implemented for Matroids with different structures.

This Wikipedia article claims the following: "An independence Oracle [...] may be implemented easily based on the underlying structure from which the matroid was defined for graphic matroids, transversal matroids, gammoids, and linear matroids".

Here, I am assuming easily means efficiently. Unfortunately, I am unable to find a good reference that supports the article's claim. Is there a good reference out there that mentions the Oracle complexities for the Matroid structures mentioned in the Wikipedia article?

• Most likely, there are no good references for such tiny observations. Do you see how to implement the independence test for graphic matroids? Sep 19 at 15:30