Popular matchings with two-sided preferences and one-sided ties

From MaRDI portal

(Redirected from Publication:3448799)

Jump to:navigation, search

DOI10.1007/978-3-662-47672-7_30MaRDI QIDQ3448799zbMATH OpenOpenAlexFDO

Authors Ágnes Cseh, Chien-Chung Huang, Telikepalli Kavitha

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.07168

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We are given a bipartite graph

G = (A c u p B, E)

where each vertex has a preference list ranking its neighbors: in particular, every

a i n A

ranks its neighbors in a strict order of preference, whereas the preference lists of

b i n B

may contain ties. A matching

M

is popular if there is no matching

M^{'}

such that the number of vertices that prefer

M^{'}

to

M

exceeds the number of vertices that prefer

M

to~

M^{'}

. We show that the problem of deciding whether

G

admits a popular matching or not is NP-hard. This is the case even when every

b i n B

either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each

b i n B

puts all its neighbors into a single tie. That is, all neighbors of

b

are tied in

b

's list and

b

desires to be matched to any of them. Our main result is an

O (n^{2})

algorithm (where

n = | A c u p B |

) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in

B

have no preferences and do not care whether they are matched or not.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Popular matchings with two-sided preferences and one-sided ties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448799)

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Popular_matchings_with_two-sided_preferences_and_one-sided_ties&oldid=87225365"