Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Maximum cardinality popular matchings in strict two-sided preference lists

Huang, Chien-Chung and Kavitha, Telikepalli

MPI-I-2010-1-001. November 2010, 17 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
We consider the problem of computing a maximum cardinality {\em popular}
matching in a bipartite
graph $G = (\A\cup\B, E)$ where each vertex $u \in \A\cup\B$ ranks its
neighbors in a
strict order of preference. This is the same as an instance of the {\em
stable marriage}
problem with incomplete lists.
A matching $M^*$ is said to be popular if there is no matching $M$ such
that more vertices are better off in $M$ than in $M^*$.


Popular matchings have been extensively studied in the case of one-sided
preference lists, i.e.,
only vertices of $\A$ have preferences over their neighbors while
vertices in $\B$ have no
preferences; polynomial time algorithms
have been shown here to determine if a given instance admits a popular
or not and if so, to compute one with maximum cardinality. It has very
been shown that for two-sided preference lists, the problem of
determining if a given instance
admits a popular matching or not is NP-complete. However this hardness
assumes that preference lists have {\em ties}.
When preference lists are {\em strict}, it is easy to
show that popular matchings always exist since stable matchings always
exist and they are popular.
But the
complexity of computing a maximum cardinality popular matching was
unknown. In this paper
we show an $O(mn)$ algorithm for this problem, where $n = |\A| + |\B|$ and
$m = |E|$.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2010-1-001.pdf MPI-I-2010-1-001.pdf 168 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Huang, Chien-Chung and Kavitha, Telikepalli},
  TITLE = {Maximum cardinality popular matchings in strict two-sided preference lists},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2010-1-001},
  MONTH = {November},
  YEAR = {2010},
  ISSN = {0946-011X},