On maximum induced matchings in bipartite graphs
The problem of finding a maximum induced matching is known to be NP-hard in general bipartite graphs. We strengthen this result by reducing the problem to some special classes of bipartite graphs such as bipartite graphs with maximum degree 3 or C-4-free bipartite graphs. On the other hand, we describe a new polynomially solvable case for the problem in bipartite graphs which deals with a generalization of bi-complement reducible graphs. (C) 2002 Elsevier Science B.V. All rights reserved.
maximum induced matching bipartite graphs graph algorithms computational complexity