Constrained weighted matchings and edge coverings in graphs Original Research Article

We introduce the problem of finding a maximum weight matching in a graph such that the number of matched vertices lies in a prescribed interval and certain vertices will be matched. In the case of bipartite graphs, this generalizes the k-cardinality assignment problem which was recently studied by DellʹAmico and Martello (Discrete Appl. Math. 76 (1997) 103–121). Similarly defined a minimum weight constrained edge covering problem is shown to be NP-hard even for bipartite graphs. We present a simple polynomial transformations of such matching and simplified covering problems to classical unconstrained problems. In the case of bipartite graphs also min-cost flow formulations are given.