Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a balanced bipartite graph, what is, or is there, an efficient algorithm for finding all edges which are not part of any perfect matching in the graph?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

Your task can be solved in almost the same time as finding just one perfect matching.

Let G=(V, W; E) be a bipartite graph with |V|=|W|. First, find one perfect matching. As Henning Makholm noted, if there is no perfect matching, all edges satisfy the condition.

If there is a perfect matching ME, then consider a directed graph by giving the orientation to each edge of G from the endpoint in V to the endpoing in W. Also add the edge in the opposite direction for each edge in M. Call this directed graph G′. Decompose G′ into strongly connected components. Now we can prove the following claim (whose proof is left as a fun exercise):

Claim. An edge vwE is used in some perfect matching in G if and only if v and w belong to the same strongly connected component of G′.

By using this, we can list all the edges that are not part of any perfect matchings in G by finding one perfect matching and performing the strongly connected component decomposition. The latter takes time O(|V|+|E|). The former takes time $\mathrm{O}(\sqrt{|V|}\,|E|)$ if we use the Hopcroft–Karp algorithm, as noted by Henning Makholm. In total, it takes time $\mathrm{O}(\sqrt{|V|}\,|E|)$, assuming that |E|≥|V|.

share|improve this answer

You can test for the existence of a perfect matching in the original graph $O(E\sqrt{V})$ time. If there is none, all edges qualify.

Then, for each edge you can test whether there is a perfect matching that includes that edge simply by removing both endpoints (and adjacent edges) and see whether the remaining graph has a perfect matching.

These combine to an $O(E^2\sqrt{V})$ algorithm. Whether you consider that efficient is up to temperament, I suppose.

share|improve this answer

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.