论文标题
在任意图上识别单峰偏好：复杂性和算法
Recognizing Single-Peaked Preferences on an Arbitrary Graph: Complexity and Algorithms
论文作者
论文摘要
本文致力于对任意图上的单峰性研究。给定偏好集（一组替代方案的排名），我们旨在确定一个连接的图形g，从而使偏好是单峰的连接图，从某种意义上说，所有偏好是G的遍历。我们提出了一个整数线性编程公式（ILP），即最小化G中边缘数量或G中顶点的最大程度的问题。我们证明，在一般情况下，这两个问题都是NP-HARD。但是，我们表明，如果最佳边缘数为M-1（其中M是候选者的数量），则ILP的任何最佳解决方案都是整数，因此可以放松整数约束。这提供了识别树上单峰偏好的多项式时间复杂性的替代证明。我们证明了路径（轴）情况相同的结果，在这里也提供了识别问题多项式性的替代证明。此外，我们提供了一个多项式时间程序，以识别假卵（Pseudotree）上的单峰偏好（最多包含一个周期的连接图）。我们还可以在真实和合成数据集上给出一些实验结果。
This paper is devoted to a study of single-peakedness on arbitrary graphs. Given a collection of preferences (rankings of a set of alternatives), we aim at determining a connected graph G on which the preferences are single-peaked, in the sense that all the preferences are traversals of G. Note that a collection of preferences is always single-peaked on the complete graph. We propose an Integer Linear Programming formulation (ILP) of the problem of minimizing the number of edges in G or the maximum degree of a vertex in G. We prove that both problems are NP-hard in the general case. However, we show that if the optimal number of edges is m-1 (where m is the number of candidates) then any optimal solution of the ILP is integer and thus the integrality constraints can be relaxed. This provides an alternative proof of the polynomial-time complexity of recognizing single-peaked preferences on a tree. We prove the same result for the case of a path (an axis), providing here also an alternative proof of polynomiality of the recognition problem. Furthermore, we provide a polynomial-time procedure to recognize single-peaked preferences on a pseudotree (a connected graph that contains at most one cycle). We also give some experimental results, both on real and synthetic datasets.
