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.^[1]

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.^[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. 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.^[3]

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,^[4] these representations are not succinct: a matroid with $\scriptstyle n$ elements may expand into a representation that takes space exponential in $\scriptstyle n$ . Indeed, the number of distinct matroids on $\scriptstyle n$ elements grows doubly exponentially as

2^{2^n n^{-3/2+o(1)}}

^[5]

from which it follows that any explicit representation capable of handling all possible matroids would necessarily use exponential space.^[6]

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 " $\scriptstyle 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 $\scriptstyle 1$ if the set is independent or $\scriptstyle 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.^[7]

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 $\scriptstyle I$ and an element $\scriptstyle x$ , and either returns a circuit in $\scriptstyle I\cup\{x\}$ (necessarily unique and containing $\scriptstyle 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^[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.^[12]

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.^[13] 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.^[3]
The oracle from Edmonds (1965) takes as input an independent set and an additional element, and either determines that their union is independent or finds a circuit in the union and returns it.
A rank oracle takes as its input a set of matroid elements, and returns as its output a numerical value, the rank of the given set.^[9]
A basis oracle takes as its input a set of matroid elements, and returns as output a Boolean value, true if the given set is a basis and false otherwise.^[9]
A circuit oracle takes as its input a set of matroid elements, and returns as output a Boolean value, true if the given set is a circuit and false otherwise.^[9]
Three types of closure oracle have been considered: one that tests if a given element belongs to the closure of a given set, a second one that returns the closure of the set, and a third one that tests whether a given set is closed.^[9]
A spanning oracle takes as its input a set of matroid elements, and returns as output a Boolean value, true if the given set is spanning (i.e. contains a basis and has the same rank as the whole matroid) and false otherwise.^[14]
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 $\scriptstyle +\infty$ if the given set is independent).^[14]
A port oracle for a fixed element $\scriptstyle x$ of the matroid takes as its input a set of matroid elements, and returns as output a Boolean value, true if the given set contains a circuit that includes $\scriptstyle x$ and false otherwise.^[15]

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 $\scriptstyle X$ is said to be polynomially reducible to another oracle $\scriptstyle Y$ if any call to $\scriptstyle X$ may be simulated by an algorithm that accesses the matroid using only oracle $\scriptstyle 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 $\scriptstyle X$ and $\scriptstyle Y$ are polynomially equivalent, then every result that proves the existence or nonexistence of a polynomial time algorithm for a matroid problem using oracle $\scriptstyle X$ also proves the same thing for oracle $\scriptstyle Y$ .

For instance, the independence oracle is polynomially equivalent to the circuit-finding oracle of Edmonds (1965). If a circuit-finding oracle is available, a set may be tested for independence using at most $\scriptstyle 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 $\scriptstyle I\cup\{x\}$ may be found using at most $\scriptstyle n$ calls to the oracle by testing, for each element $\scriptstyle y\in I$ , whether $\scriptstyle 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.^[1]

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.^[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 $\scriptstyle 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 $\scriptstyle O(\sqrt n)$ time steps, and there is a lower bound of $\scriptstyle \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.^[2]
Partitioning the elements of a matroid into a minimum number of independent sets, and finding the largest set that is simultaneously independent in two given matroids. The latter problem is called matroid intersection, and the solutions to both problems are closely related to each other.^[16]
Testing whether a matroid is $\scriptstyle k$ -connected (in the sense of Tutte 1966) for $\scriptstyle k\le 3$ .^[17]
Testing whether a given matroid is graphic^[18] or regular.^[19]
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.^[15]
Finding a branch-decomposition of a given matroid, whenever its branch-width is no more than a fixed constant.^[20]
Listing all of the bases, flats, or circuits of a matroid, in polynomial time per output set.^[21]
Approximating the number of bases by a fully polynomial-time randomized approximation scheme, for a matroid with $\scriptstyle n$ elements and rank $\scriptstyle r$ , with the additional assumption that the number of bases is within a polynomial factor of the number of $\scriptstyle r$ -element sets.^[22]

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 $\scriptstyle M$ and $\scriptstyle M'$ on which the answer to the problem differs and which are difficult for an algorithm to tell apart. In particular, if $\scriptstyle M$ has a high degree of symmetry, and differs from $\scriptstyle 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 $\scriptstyle M$ from an input formed by using one of the symmetries of $\scriptstyle M$ to permute $\scriptstyle M'$ .^[3]

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 $\scriptstyle n$ be even, let $\scriptstyle M$ be the uniform matroid $\scriptstyle U{}^{n/2}_n$ , and let $\scriptstyle M'$ be a matroid formed from $\scriptstyle M$ by making a single one of the $\scriptstyle n/2$ -element basis sets of $\scriptstyle M$ dependent instead of independent. In order for an algorithm to correctly test whether its input is uniform, it must be able to distinguish $\scriptstyle M$ from every possible permutation of $\scriptstyle M'$ . But in order for a deterministic algorithm to do so, it must test every one of the $\scriptstyle n/2$ -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

\binom{n}{n/2}=\Omega\left(\frac{2^n}{\sqrt n}\right)

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 $\scriptstyle M$ and $\scriptstyle 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{|\operatorname{aut}(M)|}{\sum_i|\operatorname{fix}(M,Q_i)|}

queries, where $\scriptstyle \operatorname{aut}(M)$ denotes the automorphism group of $\scriptstyle M$ , $\scriptstyle Q_i$ denotes the family of sets whose independence differs from $\scriptstyle M$ to $\scriptstyle M'$ , and $\scriptstyle \operatorname{fix}(M,Q_i)$ denotes the subgroup of automorphisms that maps $\scriptstyle Q_i$ to itself. For instance, the automorphism group of the uniform matroid is just the symmetric group, with size $\scriptstyle n!$ , and in the problem of testing uniform matroids there was only one set $\scriptstyle Q_i$ with $\scriptstyle |\operatorname{fix}(M,Q_i)|=(n/2)!^2$ , smaller by an exponential factor than $\scriptstyle n!$ .^[24]

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.^[23]
Testing whether a given matroid contains a fixed matroid $\scriptstyle H$ as a minor, except in the special cases that $\scriptstyle H$ is uniform with rank or corank at most one. More generally, if $\scriptstyle\mathcal{H}$ is a fixed finite set of matroids, and there is no uniform matroid in $\scriptstyle\mathcal{H}$ , then it is not possible to test in polynomial time whether a given matroid contains one or more of the matroids in $\scriptstyle\mathcal{H}$ as a minor.^[25]
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.^[26]
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.^[27]
Testing whether a given matroid is self-dual, transversal, bipartite, Eulerian, or orientable.^[3]
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.^[3]

Among the set of all properties of $\scriptstyle n$ -element matroids, the fraction of the properties that do not require exponential time to test goes to zero, in the limit, as $\scriptstyle n$ goes to infinity.^[6]

Notes

1 2 Robinson & Welsh (1980); Hausmann & Korte (1981); Coullard & Hellerstein (1996).
1 2 Edmonds (1971).
1 2 3 4 5 Jensen & Korte (1982).
↑ Mayhew (2008).
↑ Piff & Welsh (1971); Piff (1973); Knuth (1974); Bansal, Pendavingh & van der Pol (2012).
1 2 Robinson & Welsh (1980).
↑ For additional research on matroids based on the independence function axiomatization, see e.g. Rado (1957), Lazarson (1958), and Ingleton (1959).
↑ Lovász (1981); Seymour (1981); Seymour & Walton (1981); Jensen & Korte (1982); Truemper (1982).
1 2 3 4 5 6 Robinson & Welsh (1980); Hausmann & Korte (1981).
↑ E.g. see Cunningham (1986), Kelmans & Polesskiĭ (1994) Fujishige & Zhang (1995), Chávez Lomelí & Welsh (1996), Khachiyan et al. (2005), and Oum & Seymour (2007).
↑ Azar, Broder & Frieze (1994).
↑ Karp, Upfal & Wigderson (1988); Coullard & Hellerstein (1996).
↑ Edmonds (1971); Robinson & Welsh (1980); Hausmann & Korte (1981).
1 2 Hausmann & Korte (1981).
1 2 Coullard & Hellerstein (1996).
↑ Edmonds (1965); Cunningham (1986).
↑ Bixby & Cunningham (1979). A paper claiming a similar result for any fixed constant $\scriptstyle k$ was announced by Cunningham and Edmonds at roughly the same time, but appears not to have been published. Truemper (1998), pp. 186–187, writes "Locating $\scriptstyle k$ -sums for general $\scriptstyle k\ge 4$ is much more diﬃcult ... We do not know how this can be eﬃciently accomplished for binary matroids, let alone for general matroids."
↑ Seymour (1981).
↑ Truemper (1982).
↑ Oum & Seymour (2007).
↑ Khachiyan et al. (2005).
↑ Chávez Lomelí & Welsh (1996). In contrast, it is not possible for deterministic algorithms to approximate the number of bases of a matroid accurately in polynomial time (Azar, Broder & Frieze 1994).
1 2 Robinson & Welsh (1980); Jensen & Korte (1982).
↑ As well as being in Jensen & Korte (1982), this formalization is surveyed in Korte & Schrader (1981). In most of the applications of this technique in Jensen & Korte (1982), $\scriptstyle M$ is uniform, but Seymour (1981) applies the same idea to a non-uniform but highly symmetric matroid.
↑ Seymour & Walton (1981). Results of Seymour (1981) and Jensen & Korte (1982) give special cases of this for the problems of finding a $\scriptstyle U{}^2_4$ minor and a Vamos matroid minor, respectively. Testing whether a matroid is graphic or regular may be expressed in terms of a finite set of forbidden minors, and may be solved in polynomial time, but the forbidden minors for these problems include the uniform matroid $\scriptstyle U{}^2_4$ , so they do not contradict this impossibility result.
↑ Seymour (1981) showed this for binary matroids, Seymour & Walton (1981) for finite fields, Truemper (1982) for arbitrary fields, and Jensen & Korte (1982) for the existence of a field over which the matroid is representable.
↑ Lovász (1981); Jensen & Korte (1982). However, the special case of this problem for bipartite graphs can be solved in polynomial time as a matroid intersection problem.

References

Azar, Y.; Broder, A. Z.; Frieze, A. M. (1994), "On the problem of approximating the number of bases of a matroid", Information Processing Letters, 50 (1): 9–11, doi:10.1016/0020-0190(94)90037-X, MR 1279491 .
Bansal, N.; Pendavingh, R.; van der Pol, J. (2012), On the number of matroids, arXiv:1206.6270 .
Bixby, Robert E.; Cunningham, William H. (1979), "Matroids, graphs, and 3-connectivity", Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977), New York: Academic Press, pp. 91–103, MR 538038 .
Chávez Lomelí, Laura; Welsh, Dominic (1996), "Randomised approximation of the number of bases", Matroid Theory (Seattle, WA, 1995), Contemporary Mathematics, 197, Providence, RI: American Mathematical Society, pp. 371–376, doi:10.1090/conm/197/02534, MR 1411698 .
Coullard, Collette R.; Hellerstein, Lisa (1996), "Independence and port oracles for matroids, with an application to computational learning theory", Combinatorica, 16 (2): 189–208, doi:10.1007/BF01844845, MR 1401892 .
Cunningham, William H. (1986), "Improved bounds for matroid partition and intersection algorithms", SIAM Journal on Computing, 15 (4): 948–957, doi:10.1137/0215066, MR 861361 .
Edmonds, Jack (1965), "Minimum partition of a matroid into independent subsets", Journal of Research of the National Bureau of Standards, 69B: 67–72, doi:10.6028/jres.069b.004, MR 0190025 .
Edmonds, Jack (1971), "Matroids and the greedy algorithm", Mathematical Programming, 1: 127–136, doi:10.1007/BF01584082, MR 0297357 .
Fujishige, Satoru; Zhang, Xiaodong (1995), "An efficient cost scaling algorithm for the independent assignment problem", Journal of the Operations Research Society of Japan, 38 (1): 124–136, MR 1337446 .
Hausmann, Dirk; Korte, Bernhard (1978), "Lower bounds on the worst-case complexity of some oracle algorithms", Discrete Mathematics, 24 (3): 261–276, doi:10.1016/0012-365X(78)90097-3, MR 523316 .
Hausmann, D.; Korte, B. (1981), "Algorithmic versus axiomatic definitions of matroids", Mathematical programming at Oberwolfach (Proc. Conf., Math. Forschungsinstitut, Oberwolfach, 1979), Mathematical Programming Studies, 14, pp. 98–111, doi:10.1007/BFb0120924, MR 600125 .
Ingleton, A. W. (1959), "A note on independence functions and rank", Journal of the London Mathematical Society, Second Series, 34: 49–56, doi:10.1112/jlms/s1-34.1.49, MR 0101848 .
Jensen, Per M.; Korte, Bernhard (1982), "Complexity of matroid property algorithms", SIAM Journal on Computing, 11 (1): 184–190, doi:10.1137/0211014, MR 646772 .
Karp, Richard M.; Upfal, Eli; Wigderson, Avi (1988), "The complexity of parallel search", Journal of Computer and System Sciences, 36 (2): 225–253, doi:10.1016/0022-0000(88)90027-X, MR 950432 .
Kelmans, A. K.; Polesskiĭ, V. P. (1994), "Extremal sets and covering and packing problems in matroids", Selected topics in discrete mathematics (Moscow, 1972–1990), Amer. Math. Soc. Transl. Ser. 2, 158, Providence, RI: Amer. Math. Soc., pp. 149–174, MR 1269136 .
Khachiyan, L.; Boros, E.; Elbassioni, K.; Gurvich, V.; Makino, K. (2005), "On the complexity of some enumeration problems for matroids", SIAM Journal on Discrete Mathematics, 19 (4): 966–984, doi:10.1137/S0895480103428338, MR 2206374 .
Knuth, Donald E. (1974), "The asymptotic number of geometries", Journal of Combinatorial Theory, Series A, 16: 398–400, doi:10.1016/0097-3165(74)90063-6, MR 0335312 .
Korte, Bernhard; Hausmann, Dirk (1978), "An analysis of the greedy heuristic for independence systems", Algorithmic Aspects of Combinatorics (Conf., Vancouver Island, B.C., 1976), Annals of Discrete Mathematics, 2, pp. 65–74, doi:10.1016/S0167-5060(08)70322-4, MR 500689 .
Korte, B.; Schrader, R. (1981), "A survey on oracle techniques", in Gruska, Jozef; Chytil, Michal, Mathematical Foundations of Computer Science 1981, Proceedings, 10th Symposium Štrbské Pleso, Czechoslovakia August 31 – September 4, 1981, Lecture Notes in Computer Science, 118, Berlin: Springer, pp. 61–77, doi:10.1007/3-540-10856-4_74, MR 652740 .
Lazarson, T. (1958), "The representation problem for independence functions", Journal of the London Mathematical Society, Second Series, 33: 21–25, doi:10.1112/jlms/s1-33.1.21, MR 0098701 .
Lovász, L. (1981), "The matroid matching problem", Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), Colloq. Math. Soc. János Bolyai, 25, Amsterdam: North-Holland, pp. 495–517, MR 642059 .
Mayhew, Dillon (2008), "Matroid complexity and nonsuccinct descriptions", SIAM Journal on Discrete Mathematics, 22 (2): 455–466, arXiv:math/0702567, doi:10.1137/050640576, MR 2399359 .
Oum, Sang-il; Seymour, Paul (2007), "Testing branch-width", Journal of Combinatorial Theory, Series B, 97 (3): 385–393, doi:10.1016/j.jctb.2006.06.006, MR 2305892 .
Piff, M. J. (1973), "An upper bound for the number of matroids", Journal of Combinatorial Theory, Series B, 14: 241–245, doi:10.1016/0095-8956(73)90006-3, MR 0316282 .
Piff, M. J.; Welsh, D. J. A. (1971), "The number of combinatorial geometries", The Bulletin of the London Mathematical Society, 3: 55–56, doi:10.1112/blms/3.1.55, MR 0282867 .
Rado, R. (1942), "A theorem on independence relations", The Quarterly Journal of Mathematics, Second Series, 13: 83–89, doi:10.1093/qmath/os-13.1.83, MR 0008250 .
Rado, R. (1957), "Note on independence functions", Proceedings of the London Mathematical Society, Third Series, 7: 300–320, doi:10.1112/plms/s3-7.1.300, MR 0088459 .
Robinson, G. C.; Welsh, D. J. A. (1980), "The computational complexity of matroid properties", Mathematical Proceedings of the Cambridge Philosophical Society, 87 (1): 29–45, doi:10.1017/S0305004100056498, MR 549295 .
Seymour, P. D. (1981), "Recognizing graphic matroids", Combinatorica, 1 (1): 75–78, doi:10.1007/BF02579179, MR 602418 .
Seymour, P. D.; Walton, P. N. (1981), "Detecting matroid minors", Journal of the London Mathematical Society, Second Series, 23 (2): 193–203, doi:10.1112/jlms/s2-23.2.193, MR 609098 .
Truemper, K. (1982), "On the efficiency of representability tests for matroids", European Journal of Combinatorics, 3 (3): 275–291, doi:10.1016/s0195-6698(82)80039-5, MR 679212 .
Truemper, K. (1998), Matroid Decomposition (PDF) (revised ed.) .
Tutte, W. T. (1966), "Connectivity in matroids", Canadian Journal of Mathematics, 18: 1301–1324, doi:10.4153/CJM-1966-129-2, MR 0205880 .

This article is issued from Wikipedia - version of the 8/9/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.