Space complexity of undirected graph accessibility problem

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

In this research project, we investigate the space complexity of the graph accessibility problem (alternatively called the st-connectivity problem). We first show that for a given (undirected or directed) graph G, the problem can be solveddeterministically in space O(pw(G)^2 log_2 n), where n denotes the number of nodesand pw(G) denotes the path-width of G.As an immediate consequence, for the class of all graphs with path-width bounded above by a given constant, the problem can be solved deterministically in logarithmic space. As far as the authors know, there was no nontrivial class of graphs, except the class of cycle-free graphs, for which the problem is solvable in logarithmic space. Thus, our result observes a second nontrivial class of graphs with that property. We next show that for the class of all graphs consisting of only two paths, the problem still remains to be hard for deterministic log-space under the NC^1 -reducibility. This result observes that the problem is essentially hard for deterministic log-space. We further exhibit some other problems to be hard for deterministic log-space. We futher investigate the time compleixty of computing the number of isomorphisms between two given graphs. We obtain an algorithm for this problem wokring in time O(n^<k+4>) where n denotes the number of vertices in the graphs and k denotes the tree-width of the graphs.