The Analysis of Computational Complexity of Discrete Problems

离散问题的计算复杂性分析

• 批准号: 13640139
• 负责人: TODA Seinosuke
• 金额: $ 2.24万
• 依托单位: Nihon University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13640139/
• 关键词: Computational Complexity; graph theory; graph isomorphism; self avoiding walk; polynomial time algorithm; #P complete; chordal graph; grid graph; 2次元格子グラフ; 超立方体グラフ; self-avoiding walk; 数え上げ問題; 結び目; 自明性判定問題; ブレイド; 共役問題; 絡み目; 同型写真像; 多項式時間; Computational Complexity; graph theory; graph isomorphism; self avoiding walk; polynomial time algorithm; #P complete; chordal graph; grid graph; 2次元格子グラフ; 超立方体グラフ; self-avoiding walk; 数え上げ問題; 結び目; 自明性判定問題; ブレイド; 共役問題; 絡み目; 同型写真像; 多項式時間

In this research project, we mainly investigate the computational complexity of discrete problems. In particular, we dealt with graph Isomorphism problem and the problem of counting self avoiding walks in graphs. At this point, exploring the. precise complexity of the problems has remained to be important open questions in computational complexity theory while many researches were done so far. We currently believe that investigating their computational complexity may give us a new insight on the structure of computations. In this research project, we obtained several results mentioned as follows. Related to the graph isomorphism problem, we first showed that the problem of counting graph isomorphisms among partial k-trees was computable in polynomial time with developing a dynamic programming algorithm. In this algorithm, we had to compute the permanent of bipartite graphs, which is the number of perfect matching in bipartite graphs. In usual, such a computation has appeared to be hard. But, in our case, we found that bipartite graphs concerned had a strong symmetry, and then we succeeded to design an efficient algorithm for computing the permanent. We further showed that the graph isomorphism problem on the class of chordal bipartite graphs and on the class of strongly chordal graphs remained to be GI -complete.. These results refine the previous knowledge on the complexity. of the problem. We also showed that the problems of counting self-avoiding walks both in two-dimensional grid graphs and in hypercube graphs were complete for #P. This is a first result concerned on the complexity of the problem. We further showed that the problem was #EXP-complete in case that an input graph was given in a succinct representation form. We further designed a linear-time algorithm for 7-coloring 1 -planar graphs, and we study a possibility of developing software systems with using graph grammar theory.

在该研究项目中，我们主要研究离散问题的计算复杂性。特别是，我们处理图形同构问题以及计算自我避免在图形中行走的问题。在这一点上，探索。这些问题的精确复杂性仍然是计算复杂性理论中的重要开放问题，而到目前为止进行了许多研究。我们目前认为，调查其计算复杂性可能会使我们对计算结构有了新的见解。在该研究项目中，我们获得了如下提到的几个结果。与图形同构问题有关，我们首先表明，在多项式时间内，可以计算部分K-Trees之间的图形同构问题，并开发动态编程算法。在此算法中，我们必须计算两分图的永久性，这是双方图中完美匹配的数量。通常，这样的计算似乎很难。但是，在我们的情况下，我们发现相关的两分图具有很强的对称性，然后我们成功地设计了一种用于计算永久性的有效算法。我们进一步表明，在弦弦两分的类别和强烈的和弦图等级上的图形同构问题仍然是gi -complete。这些结果完善了先前关于复杂性的知识。问题。我们还表明，在二维网格图中计算自我避免步行的问题，以及在超立方体图中的#P完整问题。这是问题的复杂性的第一个结果。我们进一步表明，如果以简洁的表示形式给出了输入图，则问题是＃Exp-Complete。我们进一步为7色1平面图设计了一种线性时间算法，并研究了使用图形语法理论开发软件系统的可能性。