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 条
  • [21] The Parameterized Complexity of Geometric Graph Isomorphism
    Arvind, V.
    Rattan, Gaurav
    ALGORITHMICA, 2016, 75 (02) : 258 - 276
  • [22] STRONG ISOMORPHISM REDUCTIONS IN COMPLEXITY THEORY
    Buss, Sam
    Chen, Yijia
    Flum, Joerg
    Friedman, Sy-David
    Mueller, Moritz
    JOURNAL OF SYMBOLIC LOGIC, 2011, 76 (04) : 1381 - 1402
  • [23] The Parameterized Complexity of Geometric Graph Isomorphism
    V. Arvind
    Gaurav Rattan
    Algorithmica, 2016, 75 : 258 - 276
  • [24] The Parameterized Complexity of Geometric Graph Isomorphism
    Arvind, Vikraman
    Rattan, Gaurav
    PARAMETERIZED AND EXACT COMPUTATION, IPEC 2014, 2014, 8894 : 51 - 62
  • [25] Complexity of DNF and isomorphism of monotone formulas
    Goldsmith, J
    Hagen, M
    Mundhenk, M
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2005, PROCEEDINGS, 2005, 3618 : 410 - 421
  • [26] Polynomial Equivalence of the Problems "Predicate Formulas Isomorphism and Graph Isomorphism"
    Kosovskaya, T. M.
    Kosovskii, N. N.
    VESTNIK ST PETERSBURG UNIVERSITY-MATHEMATICS, 2019, 52 (03) : 286 - 292
  • [27] On the ring isomorphism & automorphism problems
    Kayal, N
    Saxena, N
    TWENTIETH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2005, : 2 - 12
  • [28] Polynomial Equivalence of the Problems “Predicate Formulas Isomorphism and Graph Isomorphism”
    T. M. Kosovskaya
    N. N. Kosovskii
    Vestnik St. Petersburg University, Mathematics, 2019, 52 : 286 - 292
  • [29] IDENTITY EQUIVALENCE AND ISOMORPHISM OF PROBLEMS
    MATERNA, P
    JOURNAL OF SYMBOLIC LOGIC, 1969, 34 (01) : 24 - &
  • [30] ISOMORPHISM OF 2 PROBLEMS OF MECHANICS
    ORESHKINA, LN
    DOKLADY AKADEMII NAUK SSSR, 1986, 291 (05): : 1080 - 1082
12345