Popular Roommates in Simply Exponential Time

Abstract 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>O</mml:mi> <mml:mo>∗</mml:mo> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>k</mml:mi> <mml:mi>n</mml:mi> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> time algorithm for this problem, where $$k &lt; 7.32$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>&lt;</mml:mo> <mml:mn>7.32</mml:mn> </mml:mrow> </mml:math> . 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>O</mml:mi> <mml:mo>∗</mml:mo> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> 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.