A preference system $\mathcal{I}$ is an undirected graph where vertices have preferences over their neighbors, and $\mathcal{I}$ admits a master list if all preferences can be derived from a single ordering over all vertices. We study the problem of deciding whether a given preference system~$\mathcal{I}$ is close to admitting a master list based on three different distance measures. We determine the computational complexity of the following questions: can $\mathcal{I}$ be modified by (i) $k$ swaps in the preferences, (ii) $k$ edge deletions, or (iii) $k$ vertex deletions so that the resulting instance admits a master list? We investigate these problems in detail from the viewpoint of parameterized complexity and of approximation. We also present two applications related to stable and popular matchings.
翻译:偏好系统 $\ mathcal{ I} $ 是一张未定向的图表, 其中脊椎偏好邻居, 而 $\ mathcal{ I} $ 允许所有偏好都来自所有脊椎的单次排序。 我们研究确定特定偏好系统~ $\ mathcal{ I} $ 是否接近接受基于三种不同距离测量的总列表的问题。 我们决定了下列问题的计算复杂性 : $\ mathcal{ I} $ 是否可以修改为 (一) 偏好 $k 的交换, (二) $k$ 边缘删除, 或 (三) $k vertex 删除, 以便由此产生的实例接纳主列表? 我们从参数复杂度和近似度的角度详细研究这些问题。 我们还提出了两个与稳定和流行匹配有关的应用程序 。