Space complexity of undirected graph accessibility problem

在这个研究项目中，我们研究了图可达性问题（也称为st-连通性问题）的空间复杂性。我们首先证明了对于给定的（无向或有向）图G，问题可以在空间O（pw(G)^2 log_2 n）中确定性地解决，其中n表示节点数，pw(G)表示G的路径宽度。作为一个直接的结果，对于路径宽度由给定常数限定的所有图类，问题可以在对数空间中确定性地解决。据作者所知，除了在对数空间中可解的无循环图外，不存在非平凡图类。因此，我们的结果观察到具有该性质的第二个非平凡类图。接下来，我们证明了在NC^1 -可约性下，对于只包含两条路径的所有图的类，确定性对数空间的问题仍然是困难的。这个结果表明，对于确定性对数空间来说，这个问题本质上是困难的。我们进一步展示了确定性对数空间难以解决的其他一些问题。我们进一步研究了计算两个给定图之间同构数的时间复杂度。我们得到了一个在O（n^<k+4>）时间内工作的算法，其中n表示图中的顶点数，k表示图的树宽度。

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.