New Algorithmic Complexity Bounds for Isomorphism Problems over Graphs and other Algebraic Structures

图和其他代数结构上同构问题的新算法复杂度界限

• 批准号: 225911997
• 负责人: Professor Dr. Jacobo Torán
• 金额: --
• 依托单位: Institut für Theoretische Informatik (Theo)
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2013
• 资助国家: 德国
• 起止时间: 2012-12-31 至 2017-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/225911997?language=en
• 关键词: New; Algorithmic; Complexity; Bounds; Isomorphism

Isomorphism problems play a very important role in theoretical as well as practical algorithmic applications. The exact complexity classification of the Graph Isomorphism problem as wellas isomorphism problems for other algebraic structures has been elusive for several decades. The known techniques and standard complexity classes do not seem to be adequate to classify these problems.Several results obtained in the first part of the project improve the complexity classification of isomorphism problems following new approaches from areas like parameterized complexity or circuit theory. In the second part of the proposal we would like to continue thisline of research. On one hand we will further use tools and methods described in the first proposal, like parameterized complexity appliedto Hypergraph Isomorphism and restricted versions of Graph Isomorphism. Onon the other hand we plan to study isomorphism problemsfrom two new perspectives: the variations arising in the problem complexity when the inputs areprovided in a succinct way, and the connections of Graph Isomorphism withthe area of proof complexity.

同构问题在理论和实际算法应用中都有着非常重要的作用。图的同构问题以及其他代数结构的同构问题的确切复杂性分类几十年来一直难以捉摸。已知的技术和标准的复杂性分类不足以对这些问题进行分类，本项目第一部分的一些结果改进了同构问题的复杂性分类，并从参数复杂性或电路理论等领域提出了新的方法。在提案的第二部分，我们希望继续这条研究路线。一方面，我们将进一步使用第一个方案中描述的工具和方法，如应用于超图同构的参数化复杂性和图同构的受限版本。另一方面，我们计划从两个新的角度来研究同构问题：当输入以简洁的方式提供时，问题复杂性的变化；以及图的同构与证明复杂性区域的联系。

项目成果

On the Resolution Complexity of Graph Non-isomorphism

关于图非同构的解析复杂度

• DOI: 10.1007/978-3-642-39071-5_6
• 发表时间: 2013
• 作者: Jacobo Torán

CNF and DNF succinct graph encodings

CNF 和 DNF 简洁图编码

• DOI: 10.1016/j.ic.2016.06.009
• 发表时间: 2016
• 期刊: Inf. Comput.
• 作者: Bireswar Das;Patrick Scharpfenecker;Jacobo Torán
• 通讯作者: Jacobo Torán

On the Structure of Solution-Graphs for Boolean Formulas

布尔公式解图的结构

• DOI: 10.1007/978-3-319-22177-9_10
• 发表时间: 2015
• 期刊: Electron. Colloquium Comput. Complex.
• 作者: Patrick Scharpfenecker

The Graph Isomorphism Problem (Dagstuhl Seminar 15511)

• DOI: 10.4230/dagrep.5.12.1
• 发表时间: 2015
• 期刊: Dagstuhl Reports
• 作者: L. Babai;A. Dawar;Pascal Schweitzer;J. Torán

Problems on succinctly encoded graphs

简洁编码图的问题

• DOI: 10.18725/oparu-4390
• 发表时间: 2017
• 作者: Patrick Scharpfenecker