Understanding Popular Matchings via Stable Matchings
Understanding Popular Matchings via Stable Matchings
复制标题
通过稳定匹配了解热门匹配
DOI：
--
复制
发表时间：
2018
影响因子：
0.8
通讯作者：
V. Powers
中科院分区：
文献类型：
--
作者：
Ágnes Cseh;Yuri Faenza;T. Kavitha;V. Powers
图G给出了一个婚姻问题的实例，对于图G的每个顶点，对其相邻顶点都有严格的优先顺序。如果M没有输掉与任何顶点为选民的匹配，那么匹配的M在婚姻实例中是受欢迎的。每个稳定匹配都是最小尺寸的流行匹配；另一类总是存在并且易于计算的流行匹配是优势匹配集。如果一个受欢迎的匹配M战胜了任何更大的匹配，那么这个匹配M就是优势的。因此，每个优势匹配都是一个最大大小的流行匹配，并且已知优势匹配集是辅助图中稳定匹配集的线性像。从复杂性理论的角度来看，文献的结果似乎表明，稳定的和占主导地位的匹配在受欢迎的匹配类别中表现得非常相似。本文的目的是证明稳定匹配和优势匹配的可追溯性确实存在差异，并进一步研究它们对流行匹配的重要性。首先，我们证明了检验所有流行的匹配是否都是稳定的很容易，但是检验所有流行的匹配是否都是主导的却很难。其次，我们展示了如何从本文研究的某些稳定匹配问题的np -硬度中推导出流行匹配问题的一些新的和最近的硬度结果，从而表明稳定匹配不仅可以用于显示流行匹配的正结果（众所周知），而且可以用于显示大多数负结果。我们给出了新的硬度结果的问题包括定义最小尺寸。最大尺寸)不稳定的流行匹配(例如：占主导地位)。对于已知的结果，我们给出了一个新的简单的证明，即当G是非二部的时，找到一个流行匹配的np -硬度。
An instance of the marriage problem is given by a graph G together with, for each vertex of G, a strict preference order over its neighbors. A matching M of Gis popular in the marriage instance if M does not lose a head-to-head election against anymatching where vertices are voters. Every stable matching is a min-size popular matching; another subclass of popular matchings that always exist and can be easily computed is theset of dominant matchings. A popular matching M is dominant if M wins the head-to-headelection against any larger matching. Thus every dominant matching is a max-size popularmatching and it is known that the set of dominant matchings is the linear image of the set ofstable matchings in an auxiliary graph. Results from the literature seem to suggest that stableand dominant matchings behave, from a complexity theory point of view, in a very similarmanner within the class of popular matchings.The goal of this paper is to show that indeed there are differences in the tractability of stableand dominant matchings, and to investigate further their importance for popular matchings.First, we show that it is easy to check if all popular matchings are also stable, however it isco-NP-hard to check if all popular matchings are also dominant. Second, we show how somenew and recent hardness results on popular matching problems can be deduced from the NP-hardnessof certain problems on stable matchings, also studied in this paper, thus showing thatstable matchings can be employed not only to show positive results on popular matching (as isknown), but also most negative ones. Problems for which we show new hardness results includefinding a min-size (resp. max-size) popular matching that is not stable (resp. dominant). Aknown result for which we give a new and simple proof is the NP-hardness of finding a popularmatching when G is non-bipartite.