2026-07-23T15:38:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17414 2024-03-06T10:59:41Z ddc:004 open_access

Stable Matchings with One-Sided Ties and Approximate Popularity Kavitha, Telikepalli Bipartite graphs Maximum matchings Unpopularity factor We consider a matching problem in a bipartite graph G = (A ∪ B, E) where vertices in A rank their neighbors in a strict order of preference while vertices in B are allowed to have weak rankings, i.e., ties are allowed in their preferences. Stable matchings always exist in G and are easy to find, however popular matchings need not exist and it is NP-complete to decide if one exists. This motivates the "approximately popular" matching problem. A well-known measure of approximate popularity is low unpopularity factor. We show that when each tie in G has length at most k, there always exists a stable matching whose unpopularity factor is at most k. Our proof is algorithmic and we compute such a stable matching in polynomial time. Our result can be considered to be a generalization of Gärdenfors' result (1975) which showed that when rankings are strict, every stable matching is popular. There are several applications where the size of the matching is its most important attribute. What one seeks here is a maximum matching M such that there is no maximum matching more popular than M. When rankings are weak, it is NP-hard to decide if G admits such a matching. When ties are one-sided and of length at most k, we show a polynomial time algorithm to find a maximum matching whose unpopularity factor within the set of maximum matchings is at most 2k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Telikepalli Kavitha 2022 Is Part Of LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2022.22 urn:nbn:de:0030-drops-174144 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.22 eng https://creativecommons.org/licenses/by/4.0/legalcode