Breadth-first-search levels for Baker's shifting decomposition
DefinitionWilliamsonShmoys_BakerLevelapproximation-algorithmsgraph-theoryplanar-graphs
For a simple graph on the vertex set (Fin n), bakerRoot G v is the smallest vertex label in the connected component of , and bakerLevel G v is the graph distance from that root to . These are the breadth-first-search levels used in Baker's technique: the search is run from one fixed vertex of each connected component (here, the least label), and a vertex lies in level when its distance from the search root of its component is . Adjacent vertices always lie in the same component and their levels differ by at most one.
Definition code
import Mathlib.Combinatorics.SimpleGraph.Metric
set_option autoImplicit false
namespace WilliamsonShmoys
/-- The root of the connected component of `v`: the least vertex label reachable
from `v`. Breadth-first search in Baker's decomposition (Williamson–Shmoys,
Section 10.2, p. 270) is started from one vertex in each connected component;
this fixes that vertex canonically as the component's smallest label. -/
noncomputable def bakerRoot {n : ℕ} (G : SimpleGraph (Fin n)) (v : Fin n) : Fin n := by
classical
exact (Finset.univ.filter (fun u => G.Reachable u v)).min'
⟨v, Finset.mem_filter.2 ⟨Finset.mem_univ v, SimpleGraph.Reachable.refl v⟩⟩
/-- The breadth-first-search level of `v`: its graph distance from the root of its
connected component (Williamson–Shmoys, Section 10.2, p. 270, where the vertices
are partitioned into levels `L₀, L₁, …` by distance from the search root). -/
noncomputable def bakerLevel {n : ℕ} (G : SimpleGraph (Fin n)) (v : Fin n) : ℕ :=
G.dist (bakerRoot G v) v
end WilliamsonShmoys
Source
David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011, Section 10.2 (planar graphs, Baker's technique), author electronic manuscript pp. 269-272; breadth-first-search levels L_0, L_1, ... on p. 270, used in the proof of Theorem 10.11 (p. 271).