Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 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.

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.