## 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.
### Abstract

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`(`n`^{2}).

Last update: July 27, 2017.