A combinatorial search problem on matroids

In this paper we consider the worst-case adaptive complexity of the search problem , where is also the set of independent sets of a matroid over S. We give a formula for the number of questions needed and an algorithm to find the optimal search algorithm for any matroid. This algorithm uses only O(|S|³) steps (i.e. questions to the independence oracle). This is also the length of Edmonds’ partitioning algorithm for matroids, which does not seem to be avoidable.