Popular edges and dominant matchings

• 成果类型: Article
• 署名作者: Cseh, Agnes; Kavitha, Telikepalli
• 署名单位: Hungarian Academy of Sciences; Corvinus University Budapest; Tata Institute of Fundamental Research (TIFR)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1183-y
• 发表日期: 2018
• 页码: 209-229
• 关键词: stable marriage problem

摘要

Given a bipartite graph G = (A. B, E) with strict preference lists and given an edge e *. E, we ask if there exists a popular matching in G that contains e *. We call this the popular edge problem. Amatching M is popular if there is no matching M such that the vertices that prefer M to M outnumber those that prefer M to M . It is known that every stable matching is popular; however G may have no stable matching with the edge e *. In this paper we identify another natural subclass of popular matchings called dominant matchings and show that if there is a popular matching that contains the edge e *, then there is either a stable matching that contains e * or a dominant matching that contains e *. This allows us to design a linear time algorithm for identifying the set of popular edges. When preference lists are complete, we show an O(n3) algorithm to find a popular matching containing a given set of edges or report that none exists, where n = vertical bar A vertical bar + vertical bar B vertical bar.