Some recent results in matroid theory
All the matroid algorithms presented so far (in Sections 7.4 and 13.1) were polynomial in the sense that the total number of operations was proportional to a polynomial of the size n of the input (usually n was the cardinality of the underlying set S of t
- PDF / 1,591,753 Bytes
- 14 Pages / 481.89 x 691.65 pts Page_size
- 51 Downloads / 176 Views
Some recent results in matroid theory
Section 17.1 Matroid theory algorithms II: Oracles All the matroid algorithms presented so far (in Sections 7.4 and 13.1) were polynomial in the sense that the total number of operations was proportional to a polynomial of the size n of the input (usually n was the cardinality of the underlying set 8 of the matroids M 1 ,M 2 , .•• in question), supposing that questions like "Is X ~ 8 independent in Mi?" could be answered by just one step. That means, these matroids M 1 , M 2 , ••• were given by some "subroutines" Rb R2 , .•• , respectively, and when speaking about operations in the algorithm, any call of these subroutines was considered as a single operation. Since our applications usually require graphic or representable matroids, which can be given by a graph or by a matrix, in both cases with storage requirement proportional to n 2 at most; and since checking independence in such matroids can be realized by at most about n 3 steps; the above assumption leads to "really" polynomial algorithms. But what is the case in general? As we have mentioned in the solution of Problem 7.1.9, the number of nonisomorphic matroidf f'll the n-element set 8 is nearly 22 ". Even if we wish to write down this numbt. '~ay, in binary representation), it requires a storage, proportional to 2n. Hence t. ~ storage of a "general" matroid requires exponential space (as function of n). Thus, it has not much sense to require that an algorithm be polynomial in the size of such an input (namely the description of the matroid M = (8, F)) since this input itself is already an exponential function of n = 181. That is the reason why we require the algorithms to be polynomial in n instead. Of course, in this case M is not really described; all we have is a subroutine R which answers the question "Is X ~ 8 independent in M?" in one step. For certain decision problems (like "Is the matroid loopless?") we need then only a few steps (a few call of this subroutine R) to obtain the answer, but we cannot "identify" the matroid by these questions. Hence we can be sure that such a subroutine R for a "general" matroid cannot be realized so that its number of operations is polynomial in n. Rather, we imagine this subroutine like an "oracle" (a medium by which god reveals hidden knowledge). We could have chosen another subroutine as well, which answers the question "Is X ~ 8 a circuit in M?" Therefore our above subroutine will be called A. Recski, Matroid Theory and its Applications in Electric Network Theory and in Statics © Springer-Verlag Berlin Heidelberg 1989
294
Chapter 17 Some recent results in matroid theory
independence oracle and this one circuit oracle. Similarly, we can define rank oracle, base oracle and girth oracle. For all these subroutines, the input is a subset X of 5. In case of the independence, base and circuit oracles, the output is yes or no (whether X is independent (base, circuit, respectively) or not). In case of the rank oracle, the output is r(X). In case of the girth oracle, the output is
Data Loading...
