Matroid girth
In matroid theory, a mathematical discipline, the girth of a matroid is the size of its smallest circuit or dependent set. The cogirth of a matroid is the girth of its dual matroid. Matroid girth generalizes the notion of the shortest cycle in a graph, the edge connectivity of a graph, Hall sets in bipartite graphs, even sets in families of sets, and general position of point sets. It is hard to compute, but fixed-parameter tractable for linear matroids when parameterized both by the matroid rank and the field size of a linear representation.
Examples
[edit]The "girth" terminology generalizes the use of girth in graph theory, meaning the length of the shortest cycle in a graph: the girth of a graphic matroid is the same as the girth of its underlying graph.[1]
The girth of other classes of matroids also corresponds to important combinatorial problems. For instance, the girth of a co-graphic matroid (or the cogirth of a graphic matroid) equals the edge connectivity of the underlying graph, the number of edges in a minimum cut of the graph.[1] The girth of a transversal matroid gives the cardinality of a minimum Hall set in a bipartite graph: this is a set of vertices on one side of the bipartition that does not form the set of endpoints of a matching in the graph.[2]
Any set of points in Euclidean space gives rise to a real linear matroid by interpreting the Cartesian coordinates of the points as the vectors of a matroid representation. The girth of the resulting matroid equals one plus the dimension of the space when the underlying set of point is in general position, and is smaller otherwise. Girths of real linear matroids also arise in compressed sensing, where the same concept is referred to as the spark of a matrix.[3]
The girth of a binary matroid gives the cardinality of a minimum even set, a subcollection of a family of sets that includes an even number of copies of each set element.[2]
Computational complexity
[edit]Determining the girth of a binary matroid is NP-hard.[4]
Additionally, determining the girth of a linear matroid given by a matrix representing the matroid is W[1]-hard when parameterized by the girth or by the rank of the matroid, but fixed-parameter tractable when parameterized by a combination of the rank and the size of the underlying field.[2]
For an arbitrary matroid, given by an independence oracle, it is impossible to find the girth using a subexponential number of matroid queries.[5] Similarly, for a real linear matroid of rank r, with n elements, described by an oracle that gives the orientation of any r-tuple of elements, it requires oracle queries to determine the girth.[6]
Computations using a girth oracle (an oracle that reports the smallest dependent subset of a given set of elements) have also been considered.[7]
References
[edit]- ^ a b Cho, Jung Jin; Chen, Yong; Ding, Yu (2007), "On the (co)girth of a connected matroid", Discrete Applied Mathematics, 155 (18): 2456–2470, doi:10.1016/j.dam.2007.06.015, MR 2365057.
- ^ a b c Panolan, Fahad; Ramanujan, M. S.; Saurabh, Saket (2015), "On the parameterized complexity of girth and connectivity problems on linear matroids" (PDF), in Dehne, Frank; Sack, Jörg-Rüdiger; Stege, Ulrike (eds.), Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015, Proceedings, Lecture Notes in Computer Science, vol. 9214, Springer, pp. 566–577, doi:10.1007/978-3-319-21840-3_47, ISBN 978-3-319-21839-7.
- ^ Donoho, David L.; Elad, Michael (2003), "Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ1 minimization", Proceedings of the National Academy of Sciences of the United States of America, 100 (5): 2197–2202, Bibcode:2003PNAS..100.2197D, doi:10.1073/pnas.0437847100, PMC 153464, PMID 16576749.
- ^ Cho, Chen & Ding (2007) observe that this is a corollary of a result of Alexander Vardy in coding theory: Vardy, Alexander (1997), "The intractability of computing the minimum distance of a code", IEEE Transactions on Information Theory, 43 (6): 1757–1766, doi:10.1109/18.641542, MR 1481035.
- ^ Jensen, Per M.; Korte, Bernhard (1982), "Complexity of matroid property algorithms", SIAM Journal on Computing, 11 (1): 184–190, doi:10.1137/0211014, MR 0646772.
- ^ Erickson, J.; Seidel, R. (1995), "Better lower bounds on detecting affine and spherical degeneracies", Discrete and Computational Geometry, 13 (1): 41–57, doi:10.1007/BF02574027, MR 1300508.
- ^ Hausmann, D.; Korte, B. (1981), "Algorithmic versus axiomatic definitions of matroids", Mathematical programming at Oberwolfach (Proc. Conf., Math. Forschungsinstitut, Oberwolfach, 1979), Mathematical Programming Studies, vol. 14, pp. 98–111, doi:10.1007/BFb0120924, ISBN 978-3-642-00805-4, MR 0600125.