The Complexity and Algorithmic Results of Realizing a Popular Matching

In this dissertation, we are concerned with the popular matching realization problem, which is an extension of the popular matching problem. An instance of the popular matching problem consists of a set of applicants A, a set of posts P, and a set of preference lists. According to the preference lists, the goal is to match each applicant with at most one unique post so that the resulting matching is ""popular."" A matching M mapping from A to P is popular if there is no other matching M'' such that more applicants prefer M'' to M than prefer M to M''. However, such a matching does not always exist. To remedy the issue of the non-existence of a popular matching, a possible manipulation is to neglect some applicants such that there is a popular matching for the remaining applicants and posts. Given that each applicant is appended with a cost for neglecting, the popular matching realization problem asks for a subset of applicants, with minimum sum of costs, whose deletion results in an instance admitting a popular matching. We prove that this problem is NP-hard, and it remains NP-hard to approximate to within a certain factor. For the special case where the costs of all applicants are equal, we show that the problem can be solved in O(sqrt{n}m) time, where n is the number of applicants and posts, and m is total length of the preference lists. Furthermore, we prove that the problem can be solved in O(n+m) time if preference lists are strictly ordered. Another extension of the popular matching problem is also considered in this dissertation. Given that each post is appended with a cost for duplicating, the min-cost augmentation problem asks for a set of posts, with minimum sum of costs, whose joining results in an instance admitting a popular matching. The problem has been shown to be NP-hard. We prove it remains NP-hard to approximate to within a factor, which is a stronger lower bound compared with previous work''s results. For the special case where the costs of all posts are equal, we show the problem can be solved in O(sqrt{n}m), and in O(n+m) time if preference lists are strictly ordered.