Algorithmica Прикладные компьютерные науки

Popular Roommates in Simply Exponential Time

Telikepalli Kavitha
Springer Nature · 2024-12-10 · DOI 10.1007/s00453-024-01287-4

Аннотация

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)$$ O ∗ ( 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 ∗ ( 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.

Читать у издателя →