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 条
[31]   SEMIGROUPS OF IDEALS AND ISOMORPHISM PROBLEMS [J].
Garcia-sanchez, Pedro a. ;
Tringali, Salvatore .
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2025, 153 (06) :2323-2339
[32]   On Borel complexity of the isomorphism problems for graph related classes of Lie algebras and finite p-groups [J].
Lipyanski, Ruvim ;
Vanetik, Natalia .
JOURNAL OF ALGEBRA AND ITS APPLICATIONS, 2015, 14 (05)
[33]   The Descriptive Complexity of Subgraph Isomorphism Without Numerics [J].
Oleg Verbitsky ;
Maksim Zhukovskii .
Theory of Computing Systems, 2019, 63 :902-921
[34]   ON THE AC0 COMPLEXITY OF SUBGRAPH ISOMORPHISM [J].
Li, Yuan ;
Razborov, Alexander ;
Rossman, Benjamin .
SIAM JOURNAL ON COMPUTING, 2017, 46 (03) :936-971
[35]   On the Parallel Parameterized Complexity of the Graph Isomorphism Problem [J].
Das, Bireswar ;
Enduri, Murali Krishna ;
Reddy, I. Vinod .
WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2018, 2018, 10755 :252-264
[36]   The space complexity of k-tree isomorphism [J].
Arvind, V. ;
Das, Bireswar ;
Koebler, Johannes .
ALGORITHMS AND COMPUTATION, 2007, 4835 :822-+
[37]   The Descriptive Complexity of Subgraph Isomorphism Without Numerics [J].
Verbitsky, Oleg ;
Zhukovskii, Maksim .
THEORY OF COMPUTING SYSTEMS, 2019, 63 (04) :902-921
[38]   ON THE COMPLEXITY OF THE RELATIONS OF ISOMORPHISM AND BI-EMBEDDABILITY [J].
Motto Ros, Luca .
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2012, 140 (01) :309-323
[39]   THE COMPLEXITY OF THE ISOMORPHISM CLASS OF SOME BANACH SPACES [J].
Godefroy, Gilles .
JOURNAL OF NONLINEAR AND CONVEX ANALYSIS, 2017, 18 (02) :231-240
[40]   Quantum Query Complexity of Subgraph Isomorphism and Homomorphism [J].
Kulkarni, Raghav ;
Podder, Supartha .
33RD SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2016), 2016, 47
12345