Maximum Cardinality Matching in Bipartite Graphs

Maximum Cardinality Matchings and Node 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.

A node cover is a set of nodes NC of G such that every edge of G has at least one node in NC.

Matching and node cover are in some sense opposites of each other. A matching covers the nodes of G with edges such that each node is covered by at most one edge. A node cover covers the edges of G by nodes such that each edge is covered by at least one node.

Interesting Fact: The maximum cardinality of a matching is at most the minimum cardinality of a node cover, that is, the maximum number of edges in a matching of G is always less than or equal the minimum number of nodes in a node cover of G.

Maximum Cardinality Matching in Bipartite Graphs

A graph is bipartite if it has two kinds of nodes and the edges are only allowed between nodes of different kind. We write G=(A,B,E) where A and B are the two sets of nodes and E are the edges of G.

A matching in a bipartite graph assigns nodes of A to nodes of B. Matchings in bipartite graphs can be computed more efficiently than matchings in general (=non-bipartite) graphs.

Interesting Fact: In a bipartite graph the maximum cardinality of a matching and the minimum cardinality of a node cover are equal.

Intuition Bipartite Matching: Suppose we have a set of workers and a set of machines. These are the two kinds of nodes in our bipartite graph. We know which worker can handle which machines. This defines the edges of our bipartite graph. Our task in the maximum cardinality matching problem is assigning workers to machines in such a way that as many machines as possible are operated by a worker that can handle it. One worker can be assigned to at most one machine and we can assign at most one worker to one machine.

LEDA Functions for Maximum Cardinality Matching in Bipartite Graphs

MAX_CARD_BIPARTITE_MATCHING() computes a maximum cardinality matching in a bipartite graph.

Remark: Additionally, LEDA provides several specialized implementations for maximum cardinality matching in bipartite graphs. These functions are mainly intended for specialists. More details can be found on the Manual Page of Maximum Cardinality Matching in Bipartite Graphs.

CHECK_MCB() checks if the result of MAX_CARD_BIPARTITE_MATCHING(), a list<edge> M and a node_array<bool> NC, is maximum cardinality matching and node cover of a bipartite graph G.

Example MAX_CARD_BIPARTITE_MATCHING() and CHECK_MCB()

Running times

For a bipartite graph G=(V,E), the running time of MAX_CARD_BIPARTITE_MATCHING() is O(|E|*sqrt(|V|)) and the running time of CHECK_MCB() is linear in the size of the graph.

Tips

Checking the result is much easier than computing a maximum cardinality matching in a bipartite graph. Therefore, CHECK_MCB() 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_MCB() to ensure the correctness of your result.

See also:

Matching Algorithms

Linear Lists

Node Arrays

Bipartite Maximum Weighted Matching

Bipartite Weighted Assignment

Bipartite Maximum Weighted Maximum Cardinality Matching

Maximum Cardinality Matching in General Graphs

Maximum Weighted Matching in General Graphs

Weighted Perfect Matching in General Graphs

Graphs and Related Data Types

Graph Algorithms

Manual Entries: