Pfadexistenz

Pfadexistenz is a concept used in graph theory and computer science to refer to the decision problem of determining whether a path exists between two specified vertices in a graph. Formally, given a graph G=(V,E) and two vertices s and t, the question asks whether there is a sequence of vertices v0, v1, ..., vk with v0=s, vk=t, and each consecutive pair (vi,vi+1) connected by an edge in E. The conventional notion of a path is often a simple path, i.e., with no repeated vertices, though in many contexts a path may be allowed to repeat vertices.

The problem applies to both undirected and directed graphs. In an undirected graph, a path simply connects s to t along edges without regard to direction. In a directed graph, the question concerns the existence of a directed path from s to t. Pfadexistenz is a fundamental primitive in many algorithms and data structures and is closely related to the broader notion of reachability.

Algorithms and complexity: Pfadexistenz is typically solved by graph traversal algorithms such as breadth-first search or depth-first search, which run in time linear in the size of the graph, O(|V|+|E|). These algorithms can output an explicit path when one exists. For many queries, data structures that maintain reachability information or transitive closures are used, especially in repeated-query scenarios. In computational complexity, directed reachability is a canonical problem that is complete for the class NL under logspace reductions, reflecting its central role in theory.

Variants and applications: Variants include restricted paths (e.g., paths of bounded length, paths avoiding certain vertices or edges) and reachability in dynamic graphs. Pfadexistenz is a core component of tasks in network routing, circuit design, program analysis (control-flow graphs), social-network analysis, and many graph algorithms that rely on connectivity and path existence.