@article{Elkind_Faliszewski_Lackner_Obraztsova_2015, title={The Complexity of Recognizing Incomplete Single-Crossing Preferences}, volume={29}, url={https://ojs.aaai.org/index.php/AAAI/article/view/9321}, DOI={10.1609/aaai.v29i1.9321}, abstractNote={ <p> We study the complexity of deciding if a given profile of incomplete votes (i.e., a profile of partial orders over a given set of alternatives) can be extended to a single-crossing profile of complete votes (total orders). This problem models settings where we have partial knowledge regarding votersâ€™ preferences and we would like to understand whether the given preference profile may be single-crossing. We show that this problem admits a polynomial-time algorithm when the order of votes is fixed and the input profile consists of top orders, but becomes NP-complete if we are allowed to permute the votes and the input profile consists of weak orders or independent-pairs orders. Also, we identify a number of practical special cases of both problems that admit polynomial-time algorithms. </p> }, number={1}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Elkind, Edith and Faliszewski, Piotr and Lackner, Martin and Obraztsova, Svetlana}, year={2015}, month={Feb.} }