Analyzing Computational Complexity of Graph-Theoretic Problems with Restrictions on Width Parameters

我们的研究项目的目的是分析几个图论问题的计算复杂性，主要是在这些输入图是有界的一些宽度参数。本文研究了以下问题：（1）图的同构计数，（2）图的可达性，（3）k-边连通子图的抽取，（4）判定某平面图是否有对偶环，（5）图的分解，（6）图文法在框图中的应用，（7）判定Jones多项式的最大次数，（8）随机抽样和随机生成。在本研究计画中，我们针对上述问题设计了许多演算法。我们开发的是：当输入图具有有界树宽时计算图同构的多项式时间算法，当输入图具有有界路宽时计算图可达性的多项式空间算法，当输入图具有有界路宽时计算图可达性的多项式时间近似方案。提出了一种判定给定平面图是否具有对偶环的线性时间算法，一类pretzel链的Jones多项式最大次数的多项式时间算法，设计了一种处理框图的文法和一种有效的语法分析算法，一种有效的随机算法，用于均匀地产生SAT/MAXSAT问题的输入数据。

The purpose of our research project is to analyze the computational complexity of several graph-theoretic problems, mainly in case that those input graphs are bounded on some width parameters. We investigate the following problems : (1) counting graph isomorphisms, (2) graph reachability, (3) extracting k-edge connected subgraphs, (4) deciding whether some plane graph has a dual euler tour, (5) graph decomposition, (6) applications of graph grammars to block diagrams, (7) deciding the maximum degree of a Jones polynomial, (8) random sampling and random generation. In this research project, we design many algorithms for the above problems. What we developed are : a polynomial-time algorithm for counting graph isomorphisms when those input graphs are of bounded tree-width, a logarithmic-space algorithm for graph reachability when those input graphs are of bounded path-width, a polynomial-time approximation scheme for. extracting k-edge subgraphs, a linear-time algorithm for deciding whether a given plane graph has a dual euler tour, a polynomial-time algorithm for computing the maximum degree of Jones polynomial of some class of pretzel links, design a graph grammar for manipulating block diagrams and an efficient algorithm for those syntactic analysis, an efficient random algorithm for generating uniformly an input data for SAT/MAXSAT problem.