Maximum Cardinality Matching in General Graphs

Maximum Cardinality Matchings and Odd Set Covers in Graphs

A matching in a graph G=(V,E) is a subset M of the edges E such that no two edges in M share a common end node. A maximum cardinality matching is matching with a maximum number of edges.

An odd set cover OSC of G is a labeling of the nodes with non-negative integers such that every edge of G is either incident to a node labeled 1 or connects two nodes labeled with the same i, i>=2. Odd set covers correspond to node covers in the bipartite case. More details can be found on the Manual Page Maximum Cardinality Matching in General Graphs.

Interesting Fact: Odd set covers can be used to prove the optimality of maximum cardinality matchings.

Remark: We use the term general graph to indicate that the graph is not bipartite. Matchings in bipartite graphs can be computed more efficiently than matchings in general graphs.

Intuition Maximum Cardinality Matching in General Graphs: Suppose we have a set of workers. These are the nodes in our graph. We want to build pairs of workers that work together. For each worker we know which worker he likes to work with. This defines the edges of the graph. In the maximum cardinality matching problem we want to find a maximum number of pairs such that each worker has a mate he likes to work with.

LEDA Functions for Maximum Cardinality Matching in General Graphs

MAX_CARD_MATCHING() computes a maximum cardinality matching in a general graph.

CHECK_MAX_CARD_MATCHING() checks if the result of MAX_CARD_MATCHING(), a list<edge> M and a node_array<int> OSC, is a maximum cardinality matching and a corresponding odd set cover of a graph G.

Example MAX_CARD_MATCHING() and CHECK_MAX_CARD_MATCHING()

Running times

For a graph G=(V,E), the running time of MAX_CARD_MATCHING() is (almost) O(|E|*|V|) and the running time of CHECK_MAX_CARD_MATCHING() is linear in the size of the graph.

Tips

Checking the result is much easier than computing a maximum cardinality matching in a general graph. Therefore, CHECK_MAX_CARD_MATCHING() is less complicated and less error prone. Moreover, checking is only linear in the size of the graph. So, the overhead is quite small. Use CHECK_MAX_CARD_MATCHING() to ensure the correctness of your result.

See also:

Matching Algorithms

Linear Lists

Node Arrays

Maximum Weighted Matching in General Graphs

Weighted Perfect Matching in General Graphs

Maximum Cardinality Matching in Bipartite Graphs

Bipartite Maximum Weighted Matching

Bipartite Weighted Assignment

Bipartite Maximum Weighted Maximum Cardinality Matching

Graphs and Related Data Types

Graph Algorithms

Manual Entries: