  Let $G = (A \cup B, E)$ be an instance of the stable marriage problem with
strict preference lists. A matching $M$ is popular in $G$ if $M$ does not lose
a head-to-head election against any matching where vertices are voters. Every
stable matching is a min-size popular matching; another subclass of popular
matchings that always exist and can be easily computed is the set of dominant
matchings. A popular matching $M$ is dominant if $M$ wins the head-to-head
election against any larger matching. Thus every dominant matching is a
max-size popular matching and it is known that the set of dominant matchings is
the linear image of the set of stable matchings in an auxiliary graph. Results
from the literature seem to suggest that stable and dominant matchings behave,
from a complexity theory point of view, in a very similar manner within the
class of popular matchings.
  The goal of this paper is to show that indeed there are differences in the
tractability of stable and dominant matchings, and to investigate further their
importance for popular matchings. First, we show that it is easy to check if
all popular matchings are also stable, however it is co-NP hard to check if all
popular matchings are also dominant. Second, we show how some new and recent
hardness results on popular matching problems can be deduced from the
NP-hardness of certain problems on stable matchings, also studied in this
paper, thus showing that stable matchings can be employed not only to show
positive results on popular matching (as is known), but also most negative
ones. Problems for which we show new hardness results include finding a
min-size (resp. max-size) popular matching that is not stable (resp. dominant).
A known result for which we give a new and simple proof is the NP-hardness of
finding a popular matching when $G$ is non-bipartite.
