The Complexity of Subelection Isomorphism Problems

被引：0
|
作者：
Faliszewski, Piotr [1 ]
Sornat, Krzysztof [1 ]
Szufa, Stanislaw [1 ,2 ]
机构：
[1] AGH Univ Sci & Technol, Krakow, Poland
[2] Jagiellonian Univ, Krakow, Poland
来源：
THIRTY-SIXTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FOURTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE / THE TWELVETH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE | 2022年
基金：
欧洲研究理事会;
关键词：
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
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.
引用
收藏
页码：4991 / 4998
页数：8
相关论文
共 50 条
  • [1] The Complexity of Subelection Isomorphism Problems
    Faliszewski, Piotr
    Sornat, Krzysztof
    Szufa, Stanislaw
    Journal of Artificial Intelligence Research, 2024, 80 : 1343 - 1371
  • [2] On the Complexity of Polytope Isomorphism Problems
    Volker Kaibel
    Alexander Schwartz
    Graphs and Combinatorics, 2003, 19 : 215 - 230
  • [3] On the Complexity of Matroid Isomorphism Problems
    Rao, Raghavendra B., V
    Sarma, Jayalal M. N.
    COMPUTER SCIENCE - THEORY AND APPLICATIONS, 2009, 5675 : 286 - +
  • [4] On the complexity of polytope isomorphism problems
    Kaibel, V
    Schwartz, A
    GRAPHS AND COMBINATORICS, 2003, 19 (02) : 215 - 230
  • [5] The Complexity of Sub election Isomorphism Problems
    Faliszewski, Piotr
    Sornat, Krzysztof
    Szufa, Stanislaw
    JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2024, 80 : 1343 - 1371
  • [6] The computational complexity of equivalence and isomorphism problems - Introduction
    Goos, G
    COMPUTATIONAL COMPLEXITY OF EQUIVALENCE AND ISOMORPHISM PROBLEMS, 2000, 1852 : 1 - 10
  • [7] On the complexity of submap isomorphism and maximum common submap problems
    Solnon, Christine
    Damiand, Guillaume
    de la Higuera, Colin
    Janodet, Jean-Christophe
    PATTERN RECOGNITION, 2015, 48 (02) : 302 - 316
  • [8] ON THE COMPLEXITY OF ISOMORPHISM PROBLEMS FOR TENSORS, GROUPS, AND POLYNOMIALS I: TENSOR ISOMORPHISM-COMPLETENESS
    Grochow, Joshua
    Qiao, Youming
    SIAM JOURNAL ON COMPUTING, 2023, 52 (02) : 568 - 617
  • [9] The complexity of game isomorphism
    Gabarro, Joaquim
    Garcia, Alina
    Serna, Maria
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (48) : 6675 - 6695
  • [10] On the complexity of game isomorphism
    Gabarro, Joaquim
    Garcia, Alina
    Serna, Maria
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2007, PROCEEDINGS, 2007, 4708 : 559 - +
12345