# Searching for equal subsets in a bipartite graph

Let $(U,V)$ be a finite bipartite graph of two parts $U$ and $V$. For any subset $u\subset U$ define the image $Im(u)$ in $V$ consisting of all vertices of $V$ connected to at least one vertex of $u$.

Assume that $|u|\le |Im(u)|$ for any $u\subset U$, where $|S|$ denotes the number of elements of a set $S$, and $|U|=|Im(U)|$.

Is there any effective algorithm to find a proper subset $u$ such that $|u|= |Im(u)|$, if it exists?

Update. Assume that we have a perfect matching $\phi\colon U\to Im(U)$, e.g. by Edmonds' algorithm. Then we can construct $u$ in the following way.

Take a subset $M\subset U$ consisting of a single element. Expand it by taking $\phi^{-1}(Im(M))$. The sequence of expansions stabilizes, and the limit is the minimal subset $u$ containing $x$ such that $u=Im(u)$.

I guess the question is closed now.

-

I suppose that $Im(U) = V$ if your bipartite graph is connected. If it is not, then the graph can be "reduced" by considering $(U,Im(U))$ only. I guess you can check this out

http://en.wikipedia.org/wiki/Hall%27s_marriage_theorem#Graph_theoretic_formulation

In fact, I think your problem is equivalent to finding a perfect matching in $(U,Im(U))$. By Hall's Theorem you can find a perfect matching for $U$. As such, you can find a matching for any $u \subset U$ (one way of doing this is you can find perfect matching for $U$ then reduced to $u$)

So, to answer your question, I think any effective algorithm to find a perfect matching in bipartite graph will do? I'm not sure whether you can find effective algorithm to find a perfect matching though, I suspect there is no (I'm not an expert in this area). But there are some algorithms for you to find a perfect matching in bipartite. For instance:

Step 1: Start with an arbitrary matching $M$ (you may begin with a single edge). Let $S$ be the set of single vertices in $U$.

Step 2: If $S = \emptyset$, stop, the current matching is maximum. If not, let $x \in S$.

Step 3: Construct an alternating tree rooted at $x$.

From the alternating tree, $T$ define the vertex $L_0 :=${ x }, $L_i =$ {$y | y \in N_T(z) \text{ where } z \in L_{i-1}$ }. In other words, $L_1 = N_T(x)$, neighbors of $x$ in $T$.

Step 4: If there is single vertex $y \in L_i$, $i$ odd, then there is an augmenting $x$-$y$ path. Use it to augment $M$. Otherwise, there is no augmenting paths.

Step 5: Remove $x$ from $S$ and go to Step 2.

Perhaps the algorithm is not so 'effective' as you observe Step 3 and Step 4. I ain't sure this answers to your question or not. Hope it helps.

-
Thank you for the link to the marriage theorem, I couldn't find it. I guess that similar problems should have been widely studied, so something should be known. I didn't understand what is a set $S$ of single vertices. As well as $L_i$. – perepechko Mar 8 '13 at 11:28
Actually, the question was not to find a perfect matching, but to find a proper subset with an equality above. – perepechko Mar 8 '13 at 11:45
from what I mentioned above, by Hall's Theorem you can find a perfect matching for $U$. If you can find it for $U$, it means that you can find any proper subset with equality achieved. I wanted to point out that finding a perfect matching is the stronger version of your question. I apologize for the inconsistency in algorithm. $v$ if a single vertex if it is no incident to any edge in $M$. I have made appropriate edition regarding $L_i$ above. Please check. – terrylsc Mar 8 '13 at 18:27
I don't believe this is true, terryslc. E.g., consider the complete bipartite graph $K_{n,n}$ which obviously has a perfect matching, yet every proper subset $U$ of one side has $|U|<|Im(U)|=n$. PS, actually, polynomial time algorithms to find maximum matchings in arbitrary graphs exist. Edmond's Blossom Algorithm, for example. – Casteels Mar 8 '13 at 18:44
I've never met a name I didn't misspell. That should be Edmonds' and terrylsc of course. And I guess my $U$ should be a $u$ in perepechko's notation. – Casteels Mar 8 '13 at 21:43