# Tight sets w.r.t. Hall's condition

Consider a bipartite graph G=(U+V,E) and suppose |U|=|V| and that G has a perfect matching. Therefore by P. Hall's condition, for every subsets A of U, the neighborhood N(A) of A has size at least |A|. I am interested in subsets A for which N(A) has the same cardinality as A. Do they have a name?

It seems that any perfect matching must contain a sub-matching between A and N(A). Is there an algorithm to identify the largest proper subset of U that has this property?

• These sets are sometimes known as critical sets. If $|U| = |V|$, then $U$ itself is a critical set. If $|U| < |V|$, then a critical set need not exist – consider for example the complete bipartite graph. Dec 15, 2020 at 9:06
• Thanks. Indeed considering the largest critical set does not make sense if the two sides have the same cardinality (which is what I had in mind). So, I guess, I am looking for the largest critical proper subset. Dec 15, 2020 at 9:44
• It doesn’t necessarily exist. Consider a complete bipartite graph. Dec 15, 2020 at 9:51
• Indeed. It doesn't have to. I am looking for an algorithm that finds one, in case it exists. Dec 15, 2020 at 9:54
• If you want to find any proper set satisfying $|A| = |N(A)|$, just go over all ways of removing one vertex for each side, and look for a Hall violator. Dec 15, 2020 at 10:08