论文标题
稳定的匹配和受限制的偏好：结构和复杂性
Stable Matchings with Restricted Preferences: Structure and Complexity
论文作者
论文摘要
众所周知，每个稳定的匹配实例$ i $都有一个旋转poset $ r（i）$，可以有效地计算，并且$ r（i）$的下调与$ i $的稳定匹配项一对一。此外，对于每个poset $ p $，实例$ i（p）$都可以有效地构造，以便$ i（p）$的旋转poset是同构至$ p $的。在这种情况下，我们说$ i（p）$实现$ p $。许多研究人员利用实例的旋转poset来开发快速算法或确定稳定匹配问题的硬度。 为了获得对采样稳定匹配的复杂性的参数理解，Bhatnagar等人。 [SODA 2008]引入了稳定的匹配实例，其偏好列表受到限制，但在实践中出现的模型情况。在本文中，我们研究了四个这样的参数限制。我们的目标是表征这些模型产生的旋转posets：$ k $ banded，$ k $ -attribute，$（k_1，k_2）$ - 列表，$ k $ range。 我们证明存在一个常数的$ k $，因此在前三个型号中，对于某些固定常数$ k $，在前三个型号中，每个旋转poset都可以实现。我们描述了鉴于Poset的Hasse图，用于构建此类实例的有效算法。结果，即使对于这些有限的实例，计算稳定匹配的基本问题仍然是$ \＃$ bis complete。 对于$ k $ - 范围的首选项，我们表明poset $ p $是可以实现的，并且仅当$ p $的hasse图具有$ k $的功能界定的路径宽度。使用此表征，我们表明，当通过实例的范围进行参数时，可以固定参数：准确计数和均匀地采样稳定的匹配，找到中位数，性别平等和平衡稳定匹配。
It is well known that every stable matching instance $I$ has a rotation poset $R(I)$ that can be computed efficiently and the downsets of $R(I)$ are in one-to-one correspondence with the stable matchings of $I$. Furthermore, for every poset $P$, an instance $I(P)$ can be constructed efficiently so that the rotation poset of $I(P)$ is isomorphic to $P$. In this case, we say that $I(P)$ realizes $P$. Many researchers exploit the rotation poset of an instance to develop fast algorithms or to establish the hardness of stable matching problems. In order to gain a parameterized understanding of the complexity of sampling stable matchings, Bhatnagar et al. [SODA 2008] introduced stable matching instances whose preference lists are restricted but nevertheless model situations that arise in practice. In this paper, we study four such parameterized restrictions; our goal is to characterize the rotation posets that arise from these models: $k$-bounded, $k$-attribute, $(k_1, k_2)$-list, $k$-range. We prove that there is a constant $k$ so that every rotation poset is realized by some instance in the first three models for some fixed constant $k$. We describe efficient algorithms for constructing such instances given the Hasse diagram of a poset. As a consequence, the fundamental problem of counting stable matchings remains $\#$BIS-complete even for these restricted instances. For $k$-range preferences, we show that a poset $P$ is realizable if and only if the Hasse diagram of $P$ has pathwidth bounded by functions of $k$. Using this characterization, we show that the following problems are fixed parameter tractable when parametrized by the range of the instance: exactly counting and uniformly sampling stable matchings, finding median, sex-equal, and balanced stable matchings.
