Sie sind hier

# Popular Matchings in Complete Graphs

Ágnes Cseh (Hungarian Academy of Sciences)



Our input is a complete graph G=(V,E) on n vertices where each vertex has a strict ranking of all other vertices in G. Our goal is to construct a matching in G that is popular. A matching M is popular if M does not lose a head-to-head election against any matching M′, where each vertex casts a vote for the matching in {M,M′} where it gets assigned a better partner. The popular matching problem is to decide whether a popular matching exists or not. The popular matching problem in G is easy to solve for odd n. Surprisingly, the problem becomes NP-hard for even n, as we show in our paper. Joint work with T. Kavitha, appeared at FSTTCS'18.

Date
Speaker
Location
Language
11.07.2019
16:15
Ágnes Cseh
TEL 512
English

Back to the research colloquium site.

To top