2026-08-21T18:34:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27438 2026-08-21T14:42:40Z ddc:004 open_access

Maximum Matchings and Short Voting Paths Kavitha, Telikepalli Bipartite graphs Fractional matchings Polytopes LP duality Our input is a marriage instance G = (A ∪ B, E), i.e., it is a bipartite graph where every vertex has strict preferences over its neighbors. The preferences that a vertex has on its neighbors extend naturally to preferences over matchings. A maximum matching M that does not lose an election against any maximum matching (where vertices cast votes) is a popular maximum-matching. These matchings are useful in practice - they always exist and can be efficiently computed [Kavitha, SICOMP 2014]. Suppose preferences change; then the problem is to update the current matching M_0 via a short voting path to a popular maximum-matching, where a length-𝓁 voting path from M_0 to M_𝓁 is a sequence of maximum matchings ⟨M_0,M_1,…,M_𝓁⟩ such that each matching is more popular than its predecessor. There are maximum matchings from which there is no voting path (of any length) to a popular maximum-matching [Bhattacharya et al., ICALP 2015]. We show a polynomial-time algorithm to decide if there exists a short voting path, i.e. one of length ≤ 2, from a given maximum matching to a popular maximum-matching and find one, if so. Voting paths motivate natural relaxations of popularity: pseudo-popular maximum-matchings and mostly-popular maximum-matchings; these yield more egalitarian or optimal solutions than popular maximum-matchings. We show polynomial-time algorithms to compute such optimal solutions that go beyond popularity. In particular, we give a combinatorial characterization of pseudo-popular maximum-matchings in terms of forced vertices and forbidden edges. We also show a polynomial-time algorithm to compute at most |E| = m popular maximum-matchings such that any maximum matching that loses to some popular maximum-matching loses to at least one of these m matchings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Telikepalli Kavitha 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.56 urn:nbn:de:0030-drops-274380 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.56 eng https://creativecommons.org/licenses/by/4.0/legalcode