2
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Dec 15, 2020 at 9:06
  • $\begingroup$ 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. $\endgroup$
    – giuper
    Dec 15, 2020 at 9:44
  • 1
    $\begingroup$ It doesn’t necessarily exist. Consider a complete bipartite graph. $\endgroup$
    – Yuval Filmus
    Dec 15, 2020 at 9:51
  • $\begingroup$ Indeed. It doesn't have to. I am looking for an algorithm that finds one, in case it exists. $\endgroup$
    – giuper
    Dec 15, 2020 at 9:54
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Dec 15, 2020 at 10:08

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.