@article{CsehFaenzaKavithaetal.2022,
  author    = {Cseh, Agnes and Faenza, Yuri and Kavitha, Telikepalli and Powers, Vladlena},
  title     = {Understanding popular matchings via stable matchings},
  series = {SIAM journal on discrete mathematics},
  volume    = {36},
  journal   = {SIAM journal on discrete mathematics},
  number    = {1},
  publisher = {Society for Industrial and Applied Mathematics},
  address   = {Philadelphia},
  issn      = {0895-4801},
  doi       = {10.1137/19M124770X},
  pages     = {188 -- 213},
  year      = {2022},
  abstract  = {An instance of the marriage problem is given by a graph G = (A boolean OR 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.},
  language  = {en}
}
@article{CsehHeeger2020,
  author    = {Cseh, Agnes and Heeger, Klaus},
  title     = {The stable marriage problem with ties and restricted edges},
  series = {Discrete optimization},
  volume    = {36},
  journal   = {Discrete optimization},
  publisher = {Elsevier},
  address   = {Amsterdam},
  issn      = {1572-5286},
  doi       = {10.1016/j.disopt.2020.100571},
  pages     = {11},
  year      = {2020},
  abstract  = {In the stable marriage problem, a set of men and a set of women are given, each of whom has a strictly ordered preference list over the acceptable agents in the opposite class. A matching is called stable if it is not blocked by any pair of agents, who mutually prefer each other to their respective partner. Ties in the preferences allow for three different definitions for a stable matching: weak, strong and super-stability. Besides this, acceptable pairs in the instance can be restricted in their ability of blocking a matching or being part of it, which again generates three categories of restrictions on acceptable pairs. Forced pairs must be in a stable matching, forbidden pairs must not appear in it, and lastly, free pairs cannot block any matching. Our computational complexity study targets the existence of a stable solution for each of the three stability definitions, in the presence of each of the three types of restricted pairs. We solve all cases that were still open. As a byproduct, we also derive that the maximum size weakly stable matching problem is hard even in very dense graphs, which may be of independent interest.},
  language  = {en}
}