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 elements may expand into a representation that takes space exponential in. Indeed, the number of distinct matroids on 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 "-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 if the set is independent or 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 and an element, and either returns a circuit in or determines that no such circuit exists. used a subroutine that tests whether a given set is independent, 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 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.
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 is said to be polynomially reducible to another oracle if any call to may be simulated by an algorithm that accesses the matroid using only oracle 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 and are polynomially equivalent, then every result that proves the existence or nonexistence of a polynomial time algorithm for a matroid problem using oracle also proves the same thing for oracle.
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 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 may be found using at most calls to the oracle by testing, for each element, whether 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 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 time steps, and there is a lower bound of 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:
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 and on which the answer to the problem differs and which are difficult for an algorithm to tell apart. In particular, if has a high degree of symmetry, and differs from 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 from an input formed by using one of the symmetries of to permute.
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 be even, let be the uniform matroid, and let be a matroid formed from by making a single one of the -element basis sets of dependent instead of independent. In order for an algorithm to correctly test whether its input is uniform, it must be able to distinguish from every possible permutation of. But in order for a deterministic algorithm to do so, it must test every one of the -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.
formalize this approach by proving that, whenever there exist two matroids and 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
queries, where denotes the automorphism group of, denotes the family of sets whose independence differs from to, and denotes the subgroup of automorphisms that maps to itself. For instance, the automorphism group of the uniform matroid is just the symmetric group, with size, and in the problem of testing uniform matroids there was only one set with, smaller by an exponential factor than.
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 goes to infinity.