Finding strongly popular b-matchings in bipartite graphs

Tamás Király, Zsuzsa Mészáros-Karkus


The computational complexity of the bipartite popular matching problem depends on the type of indifference allowed in the preference lists. 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. Our result also extends to the many-to-many version, i.e. the strongly popular b-matching problem.

Bibtex entry:

AUTHOR = {Kir{\'a}ly, Tam{\'a}s and M{\'e}sz{\'a}ros-Karkus, Zsuzsa},
TITLE = {Finding strongly popular b-matchings in bipartite graphs},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2017},
NUMBER = {TR-2017-04}

Last modification: 13.3.2018. Please email your comments to Tamás Király!