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 .
- 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 )
- 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.
- 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.
swell
- Christos H. Papadimitriou: Computational Complexity . Addison-Wesley, ISBN 978-0201530827