---
title: "Are There Any Nicely Structured Preference Profiles Nearby?"
authors:
  - "Robert Bredereck"
  - "Jiehua Chen"
  - "Gerhard J. Woeginger"
doi: ""
url: "https://ijcai.org/proceedings/2013/21"
pdf: "https://ijcai.org/proceedings/2013/0021.pdf"
venue: "Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence"
year: 2013
pages: "62-67"
track: ""
keywords:
---

# Are There Any Nicely Structured Preference Profiles Nearby?

Robert Bredereck, Jiehua Chen, Gerhard J. Woeginger

*Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence*, pages 62-67.

## Abstract

We investigate the problem of deciding whether a given preference profile is close to a nicely structured preference profile of a certain type, as for instance single-peaked, single-caved, single-crossing, value-restricted, best-restricted, worst-restricted, medium-restricted, or group-separable profiles. We measure this distance by the number of voters or alternatives that have to be deleted so as to reach a nicely structured profile. Our results classify all considered problem variants with respect to their computational complexity, and draw a clear line between computationally tractable (polynomial time solvable) and computationally intractable (NP-hard) questions.