Recognizing Single-Peaked Preferences on an Arbitrary Graph: Complexity and Algorithms

Bruno Escoffier, Olivier Spanjaard, Magdaléna Tydrichová

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…