Popular Matching in Roommates Setting Is NP-hard
Popular Matching in Roommates Setting Is NP-hard
复制标题
室友环境中的热门匹配是 NP 困难的
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
M. Zehavi
中科院分区：
文献类型：
--
作者：
Sushmita Gupta;P. Misra;Saket Saurabh;M. Zehavi
在室友设置（而不是婚姻设置）中，流行匹配问题的输入由图G（不一定是二分的）组成，其中每个顶点都严格按照顺序排列其邻居，称为其偏好。在POPULAR MATCHING问题中，目标是测试是否存在匹配M*，使得不存在匹配M，其中更多的顶点更喜欢它们在M中的匹配状态（根据它们的偏好）而不是它们在M* 中的匹配状态。在这篇文章中，我们通过证明问题是NP-完全的，解决了室友环境中的POPULAR MATCHING问题的计算复杂性。因此，我们解决了一个过去十年来一再明确提出的悬而未决的问题。
An input to the POPULAR MATCHING problem, in the roommates setting (as opposed to the marriage setting), consists of a graph G (not necessarily bipartite) where each vertex ranks its neighbors in strict order, known as its preference. In the POPULAR MATCHING problem the objective is to test whether there exists a matching M* such that there is no matching M where more vertices prefer their matched status in M (in terms of their preferences) over their matched status in M*. In this article, we settle the computational complexity of the POPULAR MATCHING problem in the roommates setting by showing that the problem is NP-complete. Thus, we resolve an open question that has been repeatedly and explicitly asked over the last decade.