2026-07-26T00:12:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12477 2024-03-06T10:50:14Z ddc:004 open_access

Popular Matchings with One-Sided Bias Kavitha, Telikepalli Bipartite graphs Stable matchings Gale-Shapley algorithm LP-duality Let G = (A ∪ B,E) be a bipartite graph where A consists of agents or main players and B consists of jobs or secondary players. Every vertex has a strict ranking of its neighbors. A matching M is popular if for any matching N, the number of vertices that prefer M to N is at least the number that prefer N to M. Popular matchings always exist in G since every stable matching is popular. A matching M is A-popular if for any matching N, the number of agents (i.e., vertices in A) that prefer M to N is at least the number of agents that prefer N to M. Unlike popular matchings, A-popular matchings need not exist in a given instance G and there is a simple linear time algorithm to decide if G admits an A-popular matching and compute one, if so. We consider the problem of deciding if G admits a matching that is both popular and A-popular and finding one, if so. We call such matchings fully popular. A fully popular matching is useful when A is the more important side - so along with overall popularity, we would like to maintain "popularity within the set A". A fully popular matching is not necessarily a min-size/max-size popular matching and all known polynomial time algorithms for popular matching problems compute either min-size or max-size popular matchings. Here we show a linear time algorithm for the fully popular matching problem, thus our result shows a new tractable subclass of popular matchings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Telikepalli Kavitha 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.70 urn:nbn:de:0030-drops-124774 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.70 eng https://creativecommons.org/licenses/by/3.0/legalcode