The Complexity of Subelection Isomorphism Problems

Piotr Faliszewski, Krzysztof Sornat, Stanisław Szufa

[AAAI-22] Main Track
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.

Introduction Video

Sessions where this paper appears

  • Poster Session 6

    Sat, February 26 8:45 AM - 10:30 AM (+00:00)
    Blue 6
    Add to Calendar

  • Poster Session 10

    Sun, February 27 4:45 PM - 6:30 PM (+00:00)
    Blue 6
    Add to Calendar

  • Oral Session 6

    Sat, February 26 10:30 AM - 11:45 AM (+00:00)
    Blue 6
    Add to Calendar