Popular Roommates in Simply Exponential Time

We consider the popular matching problem in a roommates instance G on n vertices, i.e., G is a graph where each vertex has a strict preference order over its neighbors. A matching M is popular if there is no matching N such that the vertices that prefer N to M outnumber those that prefer M to N. It is known that it is NP-hard to decide if G admits a popular matching or not. There is no better algorithm known for this problem than the brute force algorithm that enumerates all matchings and tests each for popularity—this could take n! time. Here we show an \(O^*(k^n)\) $O^{\ast }(k^n)$ time algorithm for this problem, where \(k < 7.32\) $k<7.32$ . We use the recent breakthrough result on the maximum number of stable matchings possible in a roommates instance to analyze our algorithm for the popular matching problem. We identify a natural (also, hard) subclass of popular matchings called truly popular matchings that are “popular fractional” and show an \(O^*(2^n)\) $O^{\ast }(2^n)$ time algorithm for the truly popular matching problem in G. We also identify a subclass of max-size popular matchings called super-dominant matchings and show a linear time algorithm for the super-dominant roommates problem.