The Analysis of Computational Complexity of Discrete Problems

点击翻译按钮获取中文摘要

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.