The Feasible Matching Problem

Let G = (V, E) be a graph and ${R\subseteq E}$ . A matching M in G is called R-feasible if the subgraph induced by the M-saturated vertices does not have an edge of R. We show that the general problem of finding a maximum size R-feasible matching in G is NP-hard and identify several natural applications of this new concept. In particular, we use R-feasible matchings to give a necessary and sufficient condition for the existence of a systems of disjoint representatives in a family of hypergraphs. This provides another Hall-type theorem for hypergraphs. We also introduce the concept of R-feasible (vertex) cover and combine it with the concept of R-feasible matching to provide a new formulation and approach to Ryser’s conjecture.