On the sets of perfect matchings for two bipartite graphs

This short note discusses the complexity of determining containment for the set of witnesses for some NP problems. For matching we settle an open prob lem by describing a simple algorithm to determine whether the set of perfec t matchings of one bipartite graph is contained in the set of perfect match ings of another bipartite graph. As a consequence we arrive at a simple alg orithm to determine whether the set of perfect matchings of two bipartite g raphs is identical. (C) 1999 Published by Elsevier Science B.V. All rights reserved.