Question

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.

Answer 1

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.