Matroid oracle

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 elements may expand into a representation that takes space exponential in n. Indeed, the number of distinct matroids on n elements grows doubly exponentially as :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 , "independence functions" or " 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 if the set is independent or 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, , 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 and an element x, and either returns a circuit in I\cup\{x\} (necessarily unique and containing x, 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 and , 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. • An independence oracle takes as its input a set of matroid elements, and returns as output a Boolean value, true if the given set is independent and false otherwise. It may be implemented easily based on the underlying structure from which the matroid was defined for graphic matroids, transversal matroids, gammoids, and linear matroids, and for matroids formed from these by standard operations such as direct sums. • A girth oracle takes as its input a set of matroid elements, and returns as its output a numerical value, the size of the smallest circuit within that set (or +\infty if the given set is independent). ==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 X is said to be polynomially reducible to another oracle Y if any call to X may be simulated by an algorithm that accesses the matroid using only oracle Y 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 X and Y are polynomially equivalent, then every result that proves the existence or nonexistence of a polynomial time algorithm for a matroid problem using oracle X also proves the same thing for oracle Y. 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 n 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 I\cup\{x\} may be found using at most n calls to the oracle by testing, for each element y\in I, whether I\setminus\{y\}\cup\{x\} 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 n 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 O(\sqrt n) time steps, and there is a lower bound of \Omega((n/\log n)^{1/3}) 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: • Finding a minimum or maximum weight basis of a weighted matroid, using a greedy algorithm. • Testing whether a matroid is k-connected (in the sense of ) for k\le 3. • Testing whether a given matroid is graphic or regular. • Finding an ear decomposition of a given matroid, a sequence of circuits whose union is the matroid and in which each circuit remains a circuit after all previous circuits in the sequence are contracted. Such a decomposition may also be found with the additional property that a chosen matroid element belongs to every circuit. • Listing all of the bases, flats, or circuits of a matroid, in polynomial time per output set. • Approximating the number of bases by a fully polynomial-time randomized approximation scheme, for a matroid with n elements and rank r, with the additional assumption that the number of bases is within a polynomial factor of the number of r-element sets. ==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 M and M' on which the answer to the problem differs and which are difficult for an algorithm to tell apart. In particular, if M has a high degree of symmetry, and differs from M' 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 M from an input formed by using one of the symmetries of M to permute M'. formalize this approach by proving that, whenever there exist two matroids M and M' on the same set of elements but with differing problem answers, an algorithm that correctly solves the given problem on those elements must use at least :\frac{\sum_i|\operatorname{fix}(M,Q_i)|} queries, where \operatorname{aut}(M) denotes the automorphism group of M, Q_i denotes the family of sets whose independence differs from M to M', and \operatorname{fix}(M,Q_i) denotes the subgroup of automorphisms that maps Q_i to itself. For instance, the automorphism group of the uniform matroid is just the symmetric group, with size n!, and in the problem of testing uniform matroids there was only one set Q_i with |\operatorname{fix}(M,Q_i)|=(n/2)!^2, smaller by an exponential factor than n!. Problems that have been proven to be impossible for a matroid oracle algorithm to compute in polynomial time include: • Testing whether a given matroid is uniform. • Testing whether a given matroid is binary, is representable over any particular fixed field, or whether there exists a field over which it is representable. • Solving the matroid matching problem, in which the input is a graph and a matroid on its vertices, and the goal is to find a matching in the graph that is as large as possible, subject to the constraint that the matched vertices form an independent set. • Testing whether a given matroid is self-dual, transversal, bipartite, Eulerian, or orientable. • Computing the girth (size of the smallest circuit), size of the largest circuit, number of circuits, number of bases, number of flats, number of maximum-rank flats, size of the largest flat, Tutte polynomial, or connectivity of a given matroid. Among the set of all properties of n-element matroids, the fraction of the properties that do not require exponential time to test goes to zero, in the limit, as n goes to infinity. ==See also==