In mathematics and computer science, a matroid oracle is a subroutine through which an algorithm may access a matroid, an abstract combinatorial structure that can be used to describe the linear dependencies between vectors in a vector space or the spanning trees of a graph, among other applications.
For instance, given an independence oracle for any matroid, it is possible to find the minimum weight basis of the matroid by applying a greedy algorithm that adds elements to the basis in sorted order by weight, using the independence oracle to test whether each element can be added.
[2] In computational complexity theory, the oracle model has led to unconditional lower bounds proving that certain matroid problems cannot be solved in polynomial time, without invoking unproved assumptions such as the assumption that P ≠ NP.
elements may expand into a representation that takes space exponential in
The oracle model provides a convenient way of codifying and classifying the kinds of access that an algorithm might need.
-functions" have been studied as one of many equivalent ways of axiomatizing matroids.
An independence function maps a set of matroid elements to the number
Thus, Edmonds (1965), in studying matroid partition problems, assumed that the access to the given matroid was through a subroutine that takes as input an independent set
Edmonds (1971) used a subroutine that tests whether a given set is independent (that is, in more modern terminology, an independence oracle), and observed that the information it provides is sufficient to find the minimum weight basis in polynomial time.
Beginning from the work of Korte & Hausmann (1978) and Hausmann & Korte (1978), researchers began studying oracles from the point of view of proving lower bounds on algorithms for matroids and related structures.
These two papers by Hausmann and Korte both concerned the problem of finding a maximum cardinality independent set, which is easy for matroids but (as they showed) harder to approximate or compute exactly for more general independence systems represented by an independence oracle.
This work kicked off a flurry of papers in the late 1970s and early 1980s showing similar hardness results for problems on matroids[8] and comparing the power of different kinds of matroid oracles.
[9] Since that time, the independence oracle has become standard for most research on matroid algorithms.
[10] There has also been continued research on lower bounds,[11] and comparisons of different types of oracle.
Although there are many known types of oracles, the choice of which to use can be simplified, because many of them are equivalent in computational power.
may be simulated by an algorithm that accesses the matroid using only oracle
[9] As well as polynomial time Turing reductions, other types of reducibility have been considered as well.
In particular, Karp, Upfal & Wigderson (1988) showed that, in parallel algorithms, the rank and independence oracles are significantly different in computational power.
The rank oracle allows the construction of a minimum weight basis by
In contrast, finding a minimum basis with an independence oracle is much slower: it can be solved deterministically in
only in the answers to a small number of queries, then it may take a very large number of queries for an algorithm to be sure of distinguishing an input of type
[3] A simple example of this approach can be used to show that it is difficult to test whether a matroid is uniform.
In order for an algorithm to correctly test whether its input is uniform, it must be able to distinguish
Therefore, testing for whether a matroid is uniform may require independence queries, much higher than polynomial.
Even a randomized algorithm must make nearly as many queries in order to be confident of distinguishing these two matroids.
[23] Jensen & Korte (1982) formalize this approach by proving that, whenever there exist two matroids
denotes the family of sets whose independence differs from
, and in the problem of testing uniform matroids there was only one set
[24] Problems that have been proven to be impossible for a matroid oracle algorithm to compute in polynomial time include: Among the set of all properties of
-element matroids, the fraction of the properties that do not require exponential time to test goes to zero, in the limit, as