The Analysis of Computational Complexity of Discrete Problems

在这个研究项目中，我们主要研究离散问题的计算复杂性。特别地，我们处理了图的同构问题和图的自避免行走计数问题。此时，探索。在计算复杂性理论中，问题的精确复杂性一直是一个重要的开放性问题，目前已有许多研究。我们目前相信，研究它们的计算复杂性可能会让我们对计算结构有一个新的认识。在这个研究项目中，我们获得了以下几个结果。针对图同构问题，我们首先通过开发一种动态规划算法，证明了部分k树间图同构的计数问题在多项式时间内是可计算的。在这个算法中，我们需要计算二部图的永久数，即二部图中完美匹配的个数。通常，这样的计算似乎是困难的。但是，在我们的例子中，我们发现有关的二部图具有很强的对称性，然后我们成功地设计了一个有效的算法来计算永久的。进一步证明了弦二部图类和强弦二部图类上的图同构问题仍然是GI -完全的。这些结果完善了以前关于复杂性的知识。这个问题。我们还证明了在二维网格图和超立方图中计数自回避行走的问题对于#P是完全的。这是有关问题复杂性的第一个结果。我们进一步表明，如果输入图以简洁的表示形式给出，则问题是#EXP-complete。我们进一步设计了一种7色1平面图的线性时间算法，并研究了利用图语法理论开发软件系统的可能性。

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.