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. The most commonly used oracle of this type is an independence oracle, a subroutine for testing whether a set of matroid elements is independent. Several other types of oracle have also been used; some of them have been shown to be weaker than independence oracles, some stronger, and some equivalent in computational power. Many algorithms that perform computations on matroids have been designed to take an oracle as input, allowing them to run efficiently without change on many different kinds of matroids, and without additional assumptions about what kind of matroid they are using. 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. 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. Problems that have been shown to be hard in this way include testing whether a matroid is binary or uniform, or testing whether it contains certain fixed minors.
Use of oracles Although some authors have experimented with computer representations of matroids that explicitly list all independent sets or all basis sets of the matroid, these representations are not succinct: a matroid with n {\displaystyle n} elements may expand into a representation that takes space exponential in n {\displaystyle n} . Indeed, the number of distinct matroids on n {\displaystyle n} elements grows doubly exponentially as
2 2 n n − 3 / 2 + o ( 1 ) {\displaystyle 2^{2^{n}n^{-3/2+o(1)}}}
from which it follows that any explicit representation capable of handling all possible matroids would necessarily use exponential space. Instead, different types of matroids may be represented more efficiently from the other structures from which they are defined: uniform matroids from their two numeric parameters, graphic matroids, bicircular matroids, and gammoids from graphs, linear matroids from matrices, etc. However, an algorithm for performing computations on arbitrary matroids needs a uniform method of accessing its argument, rather than having to be redesigned for each of these matroid classes. The oracle model provides a convenient way of codifying and classifying the kinds of access that an algorithm might need.
History Starting with Rado (1942), "independence functions" or " I {\displaystyle I} -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 1 {\displaystyle 1} if the set is independent or 0 {\displaystyle 0} if it is dependent; that is, it is the indicator function of the family of independent sets, essentially the same thing as an independence oracle. Matroid oracles have also been part of the earliest algorithmic work on matroids. 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 I {\displaystyle I} and an element x {\displaystyle x} , and either returns a circuit in I ∪ { x } {\displaystyle I\cup \{x\}} (necessarily unique and containing x {\displaystyle x} , if it exists) or determines that no such circuit exists. 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 and comparing the power of different kinds of matroid oracles. Since that time, the independence oracle has become standard for most research on matroid algorithms. There has also been continued research on lower bounds, and comparisons of different types of oracle.
Types of oracles The following types of matroid oracles have been considered.
… excerpt ends here. Continue reading the full article.
