# Finding edges that are not part of any perfect matching

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?

-

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

-

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.

-