  Given a bipartite graph G = (A u B, E) with strict preference lists and and
edge e*, we ask if there exists a popular matching in G that contains the edge
e*. We call this the popular edge problem. A matching M is popular if there is
no matching M' such that the vertices that prefer M' to M outnumber those that
prefer M to M'. It is known that every stable matching is popular; however G
may have no stable matching with the edge e* in it. In this paper we identify
another natural subclass of popular matchings called "dominant matchings" and
show that if there is a popular matching that contains the edge e*, then there
is either a stable matching that contains e* or a dominant matching that
contains e*. This allows us to design a linear time algorithm for the popular
edge problem. We also use dominant matchings to efficiently test if every
popular matching in G is stable or not.
