论文标题
强稳定且最大弱稳定的非交叉匹配
Strongly Stable and Maximum Weakly Stable Noncrossing Matchings
论文作者
论文摘要
在IWOCA 2019中，Ruangwises和Itoh引入了稳定的非交叉匹配，在这两条平行线上的每一侧都对每一侧的参与者对齐，并且没有两个匹配的边缘可以相互交叉。他们定义了两个稳定概念，即强烈稳定的非交叉匹配（SSNM）和弱稳定的非交叉匹配（WSNM），具体取决于阻塞对的强度。他们证明了WSNM始终存在，并提出了一个$ O（n^{2}）$ - 时间算法，以找到一个有$ n $男性和$ n $女性的实例的算法。他们还提出了确定SSNM存在并找到最大WSNM的复杂性的公开问题。在本文中，我们表明这两个问题在多项式时间内都可以解决。我们的算法适用于优先列表可能包含联系的扩展名，除了我们显示为NP完整的一种情况。即使每个人的首选项清单最多为两个，并且仅出现在男人的首选项列表中，即使每个人的喜好清单最多。为了补充这种棘手的性能，我们表明，如果一侧的首选项列表的长度被一个界限（但另一侧的偏好列表都没有结合），则可以在多项式时间内解决问题。
In IWOCA 2019, Ruangwises and Itoh introduced stable noncrossing matchings, where participants of each side are aligned on each of two parallel lines, and no two matching edges are allowed to cross each other. They defined two stability notions, strongly stable noncrossing matching (SSNM) and weakly stable noncrossing matching (WSNM), depending on the strength of blocking pairs. They proved that a WSNM always exists and presented an $O(n^{2})$-time algorithm to find one for an instance with $n$ men and $n$ women. They also posed open questions of the complexities of determining existence of an SSNM and finding a largest WSNM. In this paper, we show that both problems are solvable in polynomial time. Our algorithms are applicable to extensions where preference lists may include ties, except for one case which we show to be NP-complete. This NP-completeness holds even if each person's preference list is of length at most two and ties appear in only men's preference lists. To complement this intractability, we show that the problem is solvable in polynomial time if the length of preference lists of one side is bounded by one (but that of the other side is unbounded).
