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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.