|
The computational complexity of the popular matching problem in bipartite preference systems with ties depends greatly on the structure of ties. If one side has strict preferences while nodes on the other side are indifferent (but prefer to be matched), then a popular matching can be found in polynomial time [Cseh, Huang, Kavitha, 2015]. However, as the same paper points out, the problem becomes NP-complete if one side has strict preferences while the other side can have both indifferent nodes and nodes with strict preferences. We show that the problem of finding a strongly popular matching is polynomial-time solvable even in the latter case.
Bibtex entry:
| AUTHOR | = | {Kir{\'a}ly, Tam{\'a}s and M{\'e}sz{\'a}ros-Karkus, Zsuzsa}, |
| TITLE | = | {Finding strongly popular matchings in certain bipartite preference systems}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2016}, |
| NUMBER | = | {TR-2016-16} |