TY - JOUR

T1 - The popular matching and condensation problems under matroid constraints

AU - Kamiyama, Naoyuki

N1 - Funding Information:
This work was supported by JSPS KAKENHI Grant Number 25730006. The author would like to thank anonymous referees for helpful comments on an earlier version of this paper.
Publisher Copyright:
© 2015, Springer Science+Business Media New York.

PY - 2016/11/1

Y1 - 2016/11/1

N2 - The popular matching problem introduced by Abraham, Irving, Kavitha, and Mehlhorn is a matching problem in which there exist applicants and posts, and applicants have preference lists over posts. A matching M is said to be popular, if there exists no other matching N such that the number of applicants that prefer N to M is larger than the number of applicants that prefer M to N. The goal of this problem is to decide whether there exists a popular matching, and find a popular matching if one exists. In this paper, we first consider a matroid generalization of the popular matching problem with strict preference lists, and give a polynomial-time algorithm for this problem. In the second half of this paper, we consider the problem of transforming a given instance of a matroid generalization of the popular matching problem with strict preference lists by deleting a minimum number of applicants so that it has a popular matching. This problem is a matroid generalization of the popular condensation problem with strict preference lists introduced by Wu, Lin, Wang, and Chao. By using the results in the first half, we give a polynomial-time algorithm for this problem.

AB - The popular matching problem introduced by Abraham, Irving, Kavitha, and Mehlhorn is a matching problem in which there exist applicants and posts, and applicants have preference lists over posts. A matching M is said to be popular, if there exists no other matching N such that the number of applicants that prefer N to M is larger than the number of applicants that prefer M to N. The goal of this problem is to decide whether there exists a popular matching, and find a popular matching if one exists. In this paper, we first consider a matroid generalization of the popular matching problem with strict preference lists, and give a polynomial-time algorithm for this problem. In the second half of this paper, we consider the problem of transforming a given instance of a matroid generalization of the popular matching problem with strict preference lists by deleting a minimum number of applicants so that it has a popular matching. This problem is a matroid generalization of the popular condensation problem with strict preference lists introduced by Wu, Lin, Wang, and Chao. By using the results in the first half, we give a polynomial-time algorithm for this problem.

UR - http://www.scopus.com/inward/record.url?scp=84944699668&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84944699668&partnerID=8YFLogxK

U2 - 10.1007/s10878-015-9965-8

DO - 10.1007/s10878-015-9965-8

M3 - Article

AN - SCOPUS:84944699668

SN - 1382-6905

VL - 32

SP - 1305

EP - 1326

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 4

ER -