Maximum Independent Edge Set

An independent edge set, also called a matching, of a graph  is a subset of the edges such that no two edges in the subset share a vertex in . A maximum independent edge set an independent edge set containing the largest possible number of edges among all independent edge sets for a given graph.

A maximum independent edge set, also called a maximum matching, of a graph can be computed in the Wolfram Language with FindIndependentEdgeSet[g].

The size of a maximum independent edge set is known as the matching number or edge independence number.

A maximum independent edge set is not equivalent to a maximal independent edge set, which is simply an independent edge set that cannot be extended to a larger independent edge set. Every maximum independent edge set is also a maximal independent edge set, but the converse is not true.

Given an edge cover of a graph, all edges not in the cover define an independent set (Skiena 1990, p. 218). Gallai (1959) showed that the size of the minimum edge cover plus the size of the maximum independent edge set equals the number of vertices of a graph.

The blossom algorithm can be used to find a maximum independent edge set in a general graph, while the simpler Hungarian maximum matching algorithm can be used for bipartite graphs.

REFERENCES

Brualdi, R. A. Introductory Combinatorics, 4th ed. New York: Elsevier, 1997.

Cook, W. J.; Cunningham, W. H.; Pulleyblank, W. R.; and Schrijver, A. Combinatorial Optimization. New York: Wiley, 1998.

Hopcroft, J. and Karp, R. "An  Algorithm for Maximum Matching in Bipartite Graphs." SIAM J. Comput. 2, 225-231, 1975.

Pemmaraju, S. and Skiena, S. "Maximum Independent Set." §7.5.3 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. 

Cambridge, England: Cambridge University Press, p. 318, 2003.

Skiena, S. "Maximum Independent Set." §5.6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 218-219, 1990.

Zwick, U. "Lecture Notes on: Maximum Matching in Bipartite and Non-Bipartite Graphs." http://www.cs.tau.ac.il/~zwick/grad-algo-0910/match.pdf. 2009.