Boris Klemz and Günter Rote:

Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs

Manuscript, July 2017, 13 pages, submitted for publication.


A bipartite graph G=(U,V,E) is convex if the vertices in V can be linearly ordered such that for each vertex u in U, the neighbors of u are consecutive in the ordering of V. An induced matching H of G is a matching such that no edge of E connects endpoints of two different edges of H.

We show that in a convex bipartite graph with n vertices and m weighted edges, an induced matching of maximum total weight can be computed in optimal O(n+m) time.

An unweighted convex bipartite graph has a representation of size O(n) that records for each vertex u in U the first and last neighbor in the ordering of V. Given such a compact representation, we compute an induced matching of maximum cardinality in O(n) time.

In convex bipartite graphs, maximum-cardinality induced matchings are dual to minimum chain covers. A chain cover is a covering of the edge set by chain subgraphs, that is, subgraphs that do not contain induced matchings of more than one edge. Given a compact representation, we compute a representation of a minimum chain cover in O(n) time. If no compact representation is given, the cover can be computed in O(n+m) time.

The best previous algorithms for computing a maximum-cardinality induced matching or a minimum chain cover had a running time of O(n2).

other papers about this subject
Last update: July 27, 2017.