Matroid girth

Last updated

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.

Contents

Examples

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

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]

Related Research Articles

In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles, its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free.

In combinatorics, a greedoid is a type of set system. It arises from the notion of the matroid, which was originally introduced by Whitney in 1935 to study planar graphs and was later used by Edmonds to characterize a class of optimization problems that can be solved by greedy algorithms. Around 1980, Korte and Lovász introduced the greedoid to further generalize this characterization of greedy algorithms; hence the name greedoid. Besides mathematical optimization, greedoids have also been connected to graph theory, language theory, order theory, and other areas of mathematics.

In the mathematical theory of matroids, a graphic matroid is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is sometimes called a planar matroid ; these are exactly the graphic matroids formed from planar graphs.

Circuit rank Fewest graph edges whose removal breaks all cycles

In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest. It is equal to the number of independent cycles in the graph. Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank r is easily computed using the formula

In graph theory, the metric dimension of a graph G is the minimum cardinality of a subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.

Dual graph Graph representing faces of another graph

In the mathematical discipline of graph theory, the dual graph of a plane graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

In graph theory, a connected graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.

Branch-decomposition Hierarchical clustering of graph edges

In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves. Removing any edge from T partitions the edges of G into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The branchwidth of G is the minimum width of any branch-decomposition of G.

In combinatorial optimization, the matroid intersection problem is to find a largest common independent set in two matroids over the same ground set. If the elements of the matroid are assigned real weights, the weighted matroid intersection problem is to find a common independent set with the maximum possible weight. These problems generalize many problems in combinatorial optimization including finding maximum matchings and maximum weight matchings in bipartite graphs and finding arborescences in directed graphs.

In matroid theory, the dual of a matroid is another matroid that has the same elements as , and in which a set is independent if and only if has a basis set disjoint from it.

In the mathematical theory of matroids, a minor of a matroid M is another matroid N that is obtained from M by a sequence of restriction and contraction operations. Matroid minors are closely related to graph minors, and the restriction and contraction operations by which they are formed correspond to edge deletion and edge contraction operations in graphs. The theory of matroid minors leads to structural decompositions of matroids, and characterizations of matroid families by forbidden minors, analogous to the corresponding theory in graphs.

In matroid theory, a binary matroid is a matroid that can be represented over the finite field GF(2). That is, up to isomorphism, they are the matroids whose elements are the columns of a (0,1)-matrix and whose sets of elements are independent if and only if the corresponding columns are linearly independent in GF(2).

In matroid theory, an Eulerian matroid is a matroid whose elements can be partitioned into a collection of disjoint circuits.

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.

In mathematics, a bipartite matroid is a matroid all of whose circuits have even size.

In the mathematical theory of matroids, the rank of a matroid is the maximum size of an independent set in the matroid. The rank of a subset S of elements of the matroid is, similarly, the maximum size of an independent subset of S, and the rank function of the matroid maps sets of elements to their ranks.

Matroid parity problem Largest independent set of paired elements

In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem.

Odd cycle transversal

In graph theory, an odd cycle transversal of an undirected graph is a set of vertices of the graph that has a nonempty intersection with every odd cycle in the graph. Removing the vertices of an odd cycle transversal from a graph leaves a bipartite graph as the remaining induced subgraph.

Strong connectivity augmentation is a computational problem in the mathematical study of graph algorithms, in which the input is a directed graph and the goal of the problem is to add a small number of edges, or a set of edges with small total weight, so that the added edges make the graph into a strongly connected graph.

Independence Theory in Combinatorics: An Introductory Account with Applications to Graphs and Transversals is an undergraduate-level mathematics textbook on the theory of matroids. It was written by Victor Bryant and Hazel Perfect, and published in 1980 by Chapman & Hall.

References

  1. 1 2 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 .
  2. 1 2 3 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 .
  3. ↑ 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, doi: 10.1073/pnas.0437847100 , PMC   153464 , PMID   16576749 .
  4. ↑ 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 .
  5. ↑ 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 .
  6. ↑ 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 .
  7. ↑ 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, MR   0600125 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.