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 条

[41] On the complexity of the isomorphism relation for finitely generated groups [J].

Thomas, S ;

Velickovic, B .

JOURNAL OF ALGEBRA, 1999, 217 (01) :352-373

[42] An isomorphism between subexponential and parameterized complexity theory [J].

Chen, Yijia ;

Grohe, Martin .

SIAM JOURNAL ON COMPUTING, 2007, 37 (04) :1228-1258

[43] ON GENERIC COMPLEXITY OF THE ISOMORPHISM PROBLEM FOR FINITE SEMIGROUPS [J].

Rybalov, A. N. .

PRIKLADNAYA DISKRETNAYA MATEMATIKA, 2021, (51) :120-128

[44] Generic case complexity of the Graph Isomorphism Problem [J].

Noskov, Gennady A. ;

Rybalov, Alexander N. .

GROUPS COMPLEXITY CRYPTOLOGY, 2016, 8 (01) :9-20

[45] The Descriptive Complexity of Subgraph Isomorphism Without Numerics [J].

Verbitsky, Oleg ;

Zhukovskii, Maksim .

COMPUTER SCIENCE - THEORY AND APPLICATIONS (CSR 2017), 2017, 10304 :308-322

[46] On the generic complexity of the searching graph isomorphism problem [J].

Rybalov, Alexander .

GROUPS COMPLEXITY CRYPTOLOGY, 2015, 7 (02) :191-193

[47] Complexity of Isomorphism Problem for Computable Projective Planes [J].

Kogabaev N.T. .

Journal of Mathematical Sciences, 2014, 203 (4) :509-515

[48] On the AC0 Complexity of Subgraph Isomorphism [J].

Li, Yuan ;

Razborov, Alexander ;

Rossman, Benjamin .

2014 55TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2014), 2014, :344-353

[49] An Isomorphism between Subexponential and Parameterized Complexity Theory [J].

Chen, Yijia ;

Grohe, Martin .

CCC 2006: TWENTY-FIRST ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2006, :314-+

[50] THE ISOMORPHISM OF SOME PROBLEMS OF THE PERCOLATION THEORY [J].

BALAGUROV, BY .

ZHURNAL EKSPERIMENTALNOI I TEORETICHESKOI FIZIKI, 1983, 85 (02) :568-584

← 1 2 3 4 5 →