Computable reachability for finite graphs (neighbour closure)
DefinitionFastReachabilityMathlib decides reachability in a finite simple graph through SimpleGraph.reachable_iff_exists_finsetWalkLength_nonempty, which asks whether some walk of length less than joins the two vertices. That is a correct decision procedure but an impractical one: the number of walks grows exponentially, and in practice it becomes unusable past roughly ten vertices.
This file supplies the standard alternative, neighbour closure. For a finite simple graph on a vertex type with decidable adjacency, define one round of closure on a finite set by
Each round either enlarges or leaves it unchanged, so after rounds the process has certainly stabilised. The reachable set from a vertex is therefore defined as
This is the usual breadth-first characterisation of a connected component, expressed so that it evaluates: step is a Finset operation built from filter and union, and iterating it a fixed number of times gives a closed-form Finset rather than a search over walks.
The accompanying theorem FastReach.mem_reachSet_iff states that this really does compute reachability, , which is what makes the construction usable as a drop-in replacement for Mathlib's decision procedure.
Formalization Note Imports are deliberately narrow — only Mathlib.Combinatorics.SimpleGraph.Connectivity.Finite — so that downstream files stay cheap to compile. step takes the graph explicitly and requires [DecidableRel G.Adj]; reachSet additionally uses Fintype.card V as the iteration count. No finiteness assumption beyond [Fintype V] [DecidableEq V] is needed.
import Mathlib.Combinatorics.SimpleGraph.Connectivity.Finite
/-!
# Computable reachability for finite graphs
Mathlib decides `SimpleGraph.Reachable` via `reachable_iff_exists_finsetWalkLength_nonempty`,
which enumerates every walk of length `< |V|`; that is infeasible past roughly ten vertices.
This file provides the standard neighbour-closure alternative: iterate "add all neighbours of
the current set" `|V|` times starting from `{u}`.
-/
namespace FastReach
open Finset SimpleGraph
variable {V : Type*} [Fintype V] [DecidableEq V]
/-- One round of neighbour closure: add every vertex adjacent to something already in `s`. -/
def step (G : SimpleGraph V) [DecidableRel G.Adj] (s : Finset V) : Finset V :=
s ∪ univ.filter (fun v => ∃ u ∈ s, G.Adj u v)
/-- The vertices reachable from `u`, obtained by iterating neighbour closure `|V|` times.
Since each round either grows the set or has reached a fixed point, `|V|` rounds suffice. -/
def reachSet (G : SimpleGraph V) [DecidableRel G.Adj] (u : V) : Finset V :=
(step G)^[Fintype.card V] {u}
end FastReach