Matroid oracle
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. Why 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 formula_1 elements may expand into a representation that takes  space exponential in formula_1. Indeed, the number of distinct matroids on formula_1 elements grows doubly exponentially as 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 , "independence functions" or "formula_5-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 formula_6 if the set is independent or formula_7 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, , in studying matroid partition problems, assumed that the access to the given matroid was through a subroutine that takes as input an independent set formula_5 and an element formula_9, and either returns a circuit in formula_10 (necessarily unique and containing formula_9, if it exists) or determines that no such circuit exists. 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 , 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. Relative power of different oracles. 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. An oracle formula_15 is said to be "polynomially reducible" to another oracle formula_16 if any call to formula_15 may be simulated by an algorithm that accesses the matroid using only oracle formula_16 and  takes polynomial time as measured in terms of the number of elements of the matroid; in complexity-theoretic terms, this is a Turing reduction. Two oracles are said to be "polynomially equivalent" if they are polynomially reducible to each other. If formula_15 and formula_16 are polynomially equivalent, then every result that proves the existence or nonexistence of a polynomial time algorithm for a matroid problem using oracle formula_15 also proves the same thing for oracle formula_16. For instance, the independence oracle is polynomially equivalent to the circuit-finding oracle of . If a circuit-finding oracle is available, a set may  be tested for independence using at most formula_1 calls to the oracle by starting from an empty set, adding elements of the given set one element at a time, and using the circuit-finding oracle to test whether each addition preserves the independence of the set that has been constructed so far. In the other direction, if an independence oracle is available, the circuit in a set formula_10 may be found using at most formula_1 calls to the oracle by testing, for each element formula_26, whether formula_27 is independent and returning the elements for which the answer is no. The  independence oracle is also polynomially equivalent to the rank oracle, the spanning oracle, the first two types of closure oracle, and the port oracle. The basis oracle, the circuit oracle, and the oracle that tests whether a given set is closed are all weaker than the independence oracle: they can be simulated in polynomial time by an algorithm that accesses the matroid using an independence oracle, but not vice versa. Additionally, none of these three oracles can simulate each other within polynomial time. The girth oracle is stronger than the independence oracle, in the same sense. As well as polynomial  time Turing reductions, other types of reducibility have been considered as well. In particular, 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 formula_1 simultaneous queries, of the prefixes of the sorted order of the matroid elements: an element belongs to the optimal basis if and only if the rank of its prefix differs from the rank of the previous prefix. In contrast, finding a minimum basis with an independence oracle is much slower: it can be solved deterministically in formula_29  time steps, and there is a lower bound of formula_30 even for randomized parallel algorithms. Algorithms. Many problems on matroids are known to be solvable in polynomial time, by algorithms that access the matroid only through an independence oracle or another oracle of equivalent power, without need of any additional assumptions about what kind of matroid has been given to them. These polynomially-solvable problems include: Impossibility proofs. For many matroid problems, it is possible to show that an independence oracle does not provide enough power to allow the problem to be solved in polynomial time. The main idea of  these proofs is to find two matroids formula_36 and formula_37 on which the answer to the problem differs and which are difficult for an algorithm to tell apart. In particular, if formula_36 has a high degree of symmetry, and differs from formula_37 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 formula_36 from an input formed by using one of the symmetries of formula_36 to permute formula_37. A simple example of this approach can be used to  show that it is difficult to test whether a matroid is uniform. For simplicity of exposition, let formula_1 be even, let formula_36 be the uniform matroid formula_45, and let formula_37 be a matroid formed from formula_36 by making a single one of the formula_48-element basis sets of formula_36 dependent instead of independent. In order for an algorithm to correctly test whether its input is uniform, it must be able to distinguish formula_36 from every possible permutation of formula_37. But in order for a deterministic algorithm to do so, it must test every one of the formula_48-element subsets of  the elements: if it missed one set, it could be fooled by an oracle that chose that same set as the one to make dependent. 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. queries, where formula_57 denotes the automorphism group of formula_36, formula_59 denotes the family of sets whose independence differs from formula_36 to formula_37, and formula_62 denotes the subgroup of automorphisms that maps formula_59 to itself. For instance, the automorphism group  of the uniform matroid is just the symmetric group, with size formula_64, and in the problem of testing uniform matroids there was only one set formula_59 with formula_66, smaller by an exponential factor than formula_64. 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 formula_1-element matroids, the fraction of the properties that do not require exponential time to test goes to zero, in the limit, as formula_1 goes to infinity.