Some Observations on the Computational Complexity of Graph Accessibility Problem (Extended Abstract)

We investigate the space complexity of the (undirected) graph accessibility problem (UGAP for short). We first observe that for a given graph G, the problem can be solved deterministically in space O(sw(G)2 log₂n), where n denotes the number of nodes and sw(G) denotes the separation-width of G that is an invariant of graphs introduced in this paper. We next observe 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 NC1-reducibility. This result tells us that the problem is essentially hard for deterministic log-space.