An instance of the marriage problem is given by a graph $G = (A \cup B,E)$, together with, for each vertex of $G$, a strict preference order over its neighbors. A matching $M$ of $G$ is popular in the marriage instance 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 exists 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 there are instead 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 to show not only positive results on popular matchings (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 nonbipartite.

We consider popular matching problems in both bipartite and non-bipartite graphs with strict preference lists. It is known that every stable matching is a min-size popular matching. A subclass of max-size popular matchings called dominant matchings has been well-studied in bipartite graphs: they always exist and there is a simple linear time algorithm to find one. We show that it is NP-complete to decide if a bipartite graph admits a popular matching that is neither stable nor dominant. This gives rise to the anomaly that though it is easy to find min-size and max-size popular matchings in bipartite graphs, it is NP-complete to decide if there exists any popular matching whose size is sandwiched between the two extremes. We also show a number of related hardness results, such as (tight) 1/2-inapproximability of the maximum cost popular matching problem when costs are nonnegative. In non-bipartite graphs, we show a strong negative result: it is NP-hard to decide whether a popular matching exists or not, and the same result holds if we replace popular with dominant. On the positive side, we show the following results in any graph: we identify a subclass of dominant matchings called strongly dominant matchings and show a linear time algorithm to decide if a strongly dominant matching exists or not; we show an efficient algorithm to compute a popular matching of minimum cost in a graph with edge costs and bounded treewidth, or decide there is no popular matching.