We study in this paper single-peakedness on arbitrary graphs. Given a collection of preferences (rankings 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 extreme point solution of the continuous relaxation 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.

A set of voters’ preferences on a set of candidates is 2-Euclidean if candidates and voters can be mapped to the plane so that the preferences of each voter decrease with the Euclidean distance between her position and the positions of candidates. Based on geometric properties, we propose a recognition algorithm, that returns either “yes” (together with a planar positioning of candidates and voters) if the preferences are 2-Euclidean, or “no” if it is able to find a concise certificate that they are not, or “unknown” if a time limit is reached. Our algorithm outperforms a quadratically constrained programming solver achieving the same task, both in running times and the percentage of instances it is able to recognize. In the numerical tests conducted on the PrefLib library of preferences, 91.5% (resp. 4.5%) of the available sets of complete strict orders are proven not to be (resp. to be) 2-Euclidean, and the status of only 4.5% of them could not be decided. Furthermore, for instances involving 5 (resp. 6, 7) candidates, we were able to find planar representations that are compatible with 87.4% (resp. 58.1%, 60.1%) of voters’ preferences.