2026-07-24T02:23:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11582 2024-03-06T10:48:22Z ddc:004 open_access

Popular Roommates in Simply Exponential Time Kavitha, Telikepalli Roommates instance Popular matching Stable matching Dual certificate We consider the popular matching problem in a graph G = (V,E) on n vertices with strict preferences. A matching M is popular if there is no matching N in G such that 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 has a popular matching or not. There is no faster algorithm known for this problem than the brute force algorithm that could take n! time. Here we show a simply exponential time algorithm for this problem, i.e., one that runs in O^*(k^n) time, where k is a constant. We use the recent breakthrough result on the maximum number of stable matchings possible in such instances to analyze our algorithm for the popular matching problem. We identify a natural (also, hard) subclass of popular matchings called truly popular matchings and show an O^*(2^n) time algorithm for the truly popular matching problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Telikepalli Kavitha 2019 Is Part Of LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2019.20 urn:nbn:de:0030-drops-115820 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.20 eng https://creativecommons.org/licenses/by/3.0/legalcode