TY - JOUR

T1 - Independence and port oracles for matroids, with an application to computational learning theory

AU - Coullard, Collette R.

AU - Hellerstein, Lisa

PY - 1996

Y1 - 1996

N2 - Given a matroid M with distinguished element e, a port oracle with respect to e reports whether or not a given subset contains a circuit that contains e. The first main result of this paper is an algorithm for computing an e-based ear decomposition (that is, an ear decomposition every circuit of which contains element e) of a matroid using only a polynomial number of elementary operations and port oracle calls. In the case that M is binary, the incidence vectors of the circuits in the ear decomposition form a matrix representation for M. Thus, this algorithm solves a problem in computational learning theory; it learns the class of binary matroid port (BMP) functions with membership queries in polynomial time. In this context, the algorithm generalizes results of Angluin, Hellerstein, and Karpinski [1], and Raghavan and Schach [17], who showed that certain subclasses of the BMP functions are learnable in polynomial time using membership queries. The second main result of this paper is an algorithm for testing independence of a given input set of the matroid M. This algorithm, which uses the ear decomposition algorithm as a subroutine, uses only a polynomial number of elementary operations and port oracle calls. The algorithm proves a constructive version of an early theorem of Lehman [13], which states that the port of a connected matroid uniquely determines the matroid.

AB - Given a matroid M with distinguished element e, a port oracle with respect to e reports whether or not a given subset contains a circuit that contains e. The first main result of this paper is an algorithm for computing an e-based ear decomposition (that is, an ear decomposition every circuit of which contains element e) of a matroid using only a polynomial number of elementary operations and port oracle calls. In the case that M is binary, the incidence vectors of the circuits in the ear decomposition form a matrix representation for M. Thus, this algorithm solves a problem in computational learning theory; it learns the class of binary matroid port (BMP) functions with membership queries in polynomial time. In this context, the algorithm generalizes results of Angluin, Hellerstein, and Karpinski [1], and Raghavan and Schach [17], who showed that certain subclasses of the BMP functions are learnable in polynomial time using membership queries. The second main result of this paper is an algorithm for testing independence of a given input set of the matroid M. This algorithm, which uses the ear decomposition algorithm as a subroutine, uses only a polynomial number of elementary operations and port oracle calls. The algorithm proves a constructive version of an early theorem of Lehman [13], which states that the port of a connected matroid uniquely determines the matroid.

UR - http://www.scopus.com/inward/record.url?scp=0040521673&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0040521673&partnerID=8YFLogxK

U2 - 10.1007/BF01844845

DO - 10.1007/BF01844845

M3 - Article

AN - SCOPUS:0040521673

VL - 16

SP - 189

EP - 208

JO - Combinatorica

JF - Combinatorica

SN - 0209-9683

IS - 2

ER -