Apaths

An A-path is a concept in graph theory used when a subset A of vertices is designated as terminals. Let G = (V,E) be a graph and A ⊆ V. An A-path is a path P = v0, v1, ..., vk in G such that v0 ∈ A, vk ∈ A, and every interior vertex vi for 0 < i < k lies outside A (i.e., vi ∈ V \ A). A path of length one, connecting two vertices in A, is an A-path since it has no interior vertices.

Variants and role: A-paths are used to study connections among terminals in A while avoiding other terminals as intermediates. A set of vertex-disjoint A-paths connecting prescribed pairs of A-vertices is called an A-linkage; such structures arise in disjoint-paths problems and in graph-minor arguments. A-paths also appear in proofs of connectivity and separation results, where one needs to route connections between terminal vertices while controlling how terminals in A separate the graph.

Computational aspects: Questions about A-paths fall under the broader family of disjoint-path problems. Checking the existence of an A-path between two vertices in A is straightforward through a standard graph search that forbids interior vertices from A. More complex questions seek maximum or disjoint collections of A-paths and are connected to network flow, graph algorithms, and certain fixed-parameter approaches in graph theory.

See also: A-linkage, disjoint-paths problem, graph minor theory, Menger's theorem.