2026-08-07T18:21:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19416 2024-03-06T11:03:59Z ddc:004 open_access

Perfect Matchings and Popularity in the Many-To-Many Setting Kavitha, Telikepalli Makino, Kazuhisa Bipartite graphs Matchings under preferences Capacities Dual certificates We consider a matching problem in a bipartite graph G where every vertex has a capacity and a strict preference list ranking its neighbors. We assume that G admits a perfect matching, i.e., one that fully matches all vertices. It is only perfect matchings that are feasible here and we seek one that is popular within the set of perfect matchings - it is known that such a matching exists in G and can be efficiently computed. Now we are in the weighted setting, i.e., there is a cost function on the edge set, and we seek a min-cost popular perfect matching in G. We show that such a matching can be computed in polynomial time. Our main technical result shows that every popular perfect matching in a hospitals/residents instance G can be realized as a popular perfect matching in the marriage instance obtained by cloning vertices. Interestingly, it is known that such a mapping does not hold for popular matchings in a hospitals/residents instance. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Telikepalli Kavitha and Kazuhisa Makino 2023 Is Part Of LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2023.43 urn:nbn:de:0030-drops-194167 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.43 eng https://creativecommons.org/licenses/by/4.0/legalcode