Lagmental Vicfred

A DFS Low-Link Value Detects Back Edges by Vicfred

Last updated: Thu 07 February 2019

tags: mathematics, connectivity, bridges, Menger theorem

The low value of a vertex is the earliest discovery time reachable from its subtree using at most one back edge. The point is to make the formal expression readable enough to audit line by line.

The mathematical object

Connectivity asks how many vertices or edges must be removed to disconnect a graph \(G\). Depth-first search timestamps \(\operatorname{tin}(v)\) and low-link values \(\operatorname{low}(v)\) expose local cut structure.

$$ \operatorname{low}(v)=\min\left(\operatorname{tin}(v),\ \operatorname{tin}(w)\text{ over back edges},\ \operatorname{low}(u)\text{ over children}\right) $$

The definition determines which expressions are legal; only then does the identity become meaningful. An equality in \(\mathcal A\) may change ambient meaning, so I keep \(\mathsf D\) separate from \(\mathsf C\).

$$ \operatorname{low}(v)\le\operatorname{tin}(v) $$

One explicit computation

The middle display is intentionally dense: it is where signs, bounds, multiplicities, or normalising factors are most likely to be lost.

$$ \operatorname{low}(v)=\min\!\left\{\operatorname{tin}(v),\min_{(v,w)\ \mathrm{back}}\operatorname{tin}(w),\min_{u\ \mathrm{child}}\operatorname{low}(u)\right\} $$

Why the identity matters

The two-row display is also a debugging tool: if the conclusion changes when only notation changes, some hidden choice has entered the argument.

$$ \begin{aligned} \mathsf{D}\;&:\quad \operatorname{low}(v)=\min\left(\operatorname{tin}(v),\ \operatorname{tin}(w)\text{ over back edges},\ \operatorname{low}(u)\text{ over children}\right),\\[5pt] \mathsf{C}\;&:\quad \operatorname{low}(v)\le\operatorname{tin}(v). \end{aligned} $$

Where it can fail

Bridge and articulation criteria depend on DFS-tree relationships. Applying them to an arbitrary spanning tree gives false positives.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \operatorname{low}(v)\le\operatorname{tin}(v) \end{gathered}} $$

The result is compact enough to reuse without pretending that the caveat has disappeared. The worked line remains the quickest consistency check.

This article was posted on Thu 25 April 2013. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.