Max-size popular matchings and extensions.

We consider the max-size popular matching problem in a roommates instance G =(V,E) with strict preference lists. A matching M is popular if there is nomatching M' in G such that the vertices that prefer M' to M outnumber thosethat prefer M to M'. We show it is NP-hard to compute a max-size popularmatching in G. This is in contrast to the tractability of this problem inbipartite graphs where a max-size popular matching can be computed in lineartime. We define a subclass of max-size popular matchings called stronglydominant matchings and show a linear time algorithm to solve the stronglydominant matching problem in a roommates instance.

We consider a generalization of the max-size popular matching problem inbipartite graphs: this is the max-weight popular matching problem where thereis also an edge weight function w and we seek a popular matching of largestweight. We show this is an NP-hard problem and this is so even when w(e) iseither 1 or 2 for every edge e. We also show an algorithm with running timeO*(2^{n/4}) to find a max-weight popular matching matching in G = (A U B,E)$ onn vertices.