The Analysis of Computational Complexity of Discrete Problems

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

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.