Induced matchings (Q1262877)

An induced matching of a graph G is a vertex induced subgraph of G that is a matching. The author shows that the following decision problem is NP-complete: For a given bipartite graph G and positive integer k, is there an induced matching of size at least k? So the problem of finding a largest induced matching for bipartite graphs is Np-hard. It is, however, shown that there is an efficient parallel algorithm for finding largest induced matchings in chordal graphs.