direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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.


Ágnes Cseh
TEL 512

Back to the research colloquium site.

To top

Zusatzinformationen / Extras