The Complexity of Subelection Isomorphism Problems

Piotr Faliszewski, Krzysztof Sornat, Stanislaw Szufa

AAAI 2022 pp. 4991-4998

doi:10.1609/AAAI.V36I5.20430 /aaai/2022/faliszewski2022aaai-complexity/

Abstract

We study extensions of the Election Isomorphism problem, focused on the existence of isomorphic subelections. Specifically, we propose the Subelection Isomorphism and the Maximum Common Subelection problems and study their computational complexity and approximability. Using our problems in experiments, we provide some insights into the nature of several statistical models of elections.

PDF AAAI Semantic Scholar

Cite

Text

Faliszewski et al. "The Complexity of Subelection Isomorphism Problems." AAAI Conference on Artificial Intelligence, 2022. doi:10.1609/AAAI.V36I5.20430

Markdown

[Faliszewski et al. "The Complexity of Subelection Isomorphism Problems." AAAI Conference on Artificial Intelligence, 2022.](https://mlanthology.org/aaai/2022/faliszewski2022aaai-complexity/) doi:10.1609/AAAI.V36I5.20430

BibTeX

@inproceedings{faliszewski2022aaai-complexity,
  title     = {{The Complexity of Subelection Isomorphism Problems}},
  author    = {Faliszewski, Piotr and Sornat, Krzysztof and Szufa, Stanislaw},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2022},
  pages     = {4991-4998},
  doi       = {10.1609/AAAI.V36I5.20430},
  url       = {https://mlanthology.org/aaai/2022/faliszewski2022aaai-complexity/}
}