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

我们的研究项目的目的是分析几个图论问题的计算复杂性，主要是在这些输入图在某些宽度参数上有界的情况下。我们研究了下列问题：(1)计数图同构，(2)图的可达性，(3)提取k-边连通子图，(4)判断某个平面图是否有对偶欧拉圈，(5)图分解，(6)图文法在框图中的应用，(7)确定Jones多项式的最大次数，(8)随机抽样和随机生成。在本研究项目中，我们针对上述问题设计了多种算法。我们所开发的是：当输入图是有界树宽时，计算图同构的多项式时间算法，当输入图是有界路宽时，图可达性的对数空间算法，多项式时间近似方案。提取k边子图，用线性时间算法判断平面图是否有对偶欧拉圈，用多项式时间算法计算某类椒盐链环的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.