= Minimum reachable label propagation
Assign each <vertex> of a finite <directed graph> a label in a <total order>. To find the least label reachable from each vertex, first compress its <strongly connected components>. Give each component its own least label, then process the <condensation graph> in reverse <topological order>, replacing each label by the minimum of itself and its successors' labels. Every reachable component is either the current one or reached through a first outgoing edge; <induction> over this order proves the recurrence. The graph-processing work is $O(|V|+|E|)$ with constant-cost label comparisons. Store a representative vertex as well when a witness is required.
Back to article page
