Accessibility problem in graphs

The accessibility problem in graphs (also STCON or USTCON, GAP, PATH or REACH) deals with the question of whether there is a path from a node to a node in a graph . Does such a way, then from out of reach . Otherwise, of from unreachable . GAP stands for engl. Graph Accessibility Problem and REACH for Engl. Reachability . ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle t}$ ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle s}$

The abbreviation STCON stands for Engl. st-Connectivity and describes the reachability problem in a directed graph . In this variant it is an NL-complete problem.

The abbreviation USTCON stands for English. undirected st-Connectivity and describes the accessibility problem in an undirected graph . In this variant it is an L-complex problem.

It can be solved , for example, with the help of breadth-first search or depth-first search .

Statements and sentences

In undirected graph, each node of any other node if and only accessible from when the graph connected is.

In directed graphs this is the case if and only if the graph is strongly connected .

The STCON problem is NL-complete .

The STCON problem is in ( Savitch's Theorem ) ${\ displaystyle DSPACE (o (log (n) ^ {2}))}$

The USTCON problem lies in the L complexity class .

The proof idea for STCON is NL-complete

It has to be shown that every problem in NL can be reduced to STCON and that STCON is in NL.

A suitable algorithm must be specified for STCON in NL. A nondeterministic Turing machine (NTM) advises the (correct) successor nodes to find the node they are looking for. In addition, a binary counter is maintained that counts up to a maximum (after each step). The space consumption is because only the current node needs to be saved and the meter only needs memory. ${\ displaystyle | V |}$ ${\ displaystyle {\ mathcal {O}} (log (n))}$ ${\ displaystyle {\ mathcal {O}} (log (n))}$
The problems in NL are those that can be solved in logarithmic space by an NTM. Every Turing machine has a configuration graph which describes the different configurations of a TM (the head position, the tape content and the status). The configuration graph of an NTM, which solves a problem in NL, is, since the set inclusion holds, of maximally polynomial size. In order to find a way and thus a solution for any problem in NL, we only have to solve the following problem: "Is there a way from the initial state to the accepting state?" The algorithm given above can provide us with the solution to this problem. ${\ displaystyle NL \ subseteq P}$

swell

Christos H. Papadimitriou: Computational Complexity . Addison-Wesley, ISBN 978-0201530827