Finding all maximally-matchable edges in a bipartite graph

We consider the problem of finding all maximally-matchable edges in a bipartite graph G=(V,E), i.e., all edges that are included in some maximum matching. We show that given any maximum matching in the graph, it is possible to perform this computation in linear time O(n+m) (where n=|V| and m=|E|). Hence, the time complexity of finding all maximally-matchable edges reduces to that of finding a single maximum matching, which is O(n1/2m) (Hopcroft and Karp [12], ), or O((n/logn)1/2m) for dense graphs with m=Θ(n2) (Alt et al. [2], ). This time complexity improves upon that of the best known algorithms for the problem, which is O(nm) (Costa [5], for bipartite graphs, and Carvalho and Cheriyan [6], for general graphs). Other algorithms for solving that problem are randomized algorithms due to Rabin and Vazirani [15], and Cheriyan [3], the runtime of which is . Our algorithm, apart from being deterministic, improves upon that time complexity for bipartite graphs when m=O(nr) and r<1.876. In addition, our algorithm is elementary, conceptually simple, and easy to implement.