= DFS lowpoint
{c}
{title2=$\operatorname{low}(v)$}
For a finite <simple graph> that is an <undirected graph>, the <DFS lowpoint> of $v$ is the smallest <DFS discovery time> reachable by following zero or more discovery <edges> down its <rooted tree>, then at most one non-discovery <edge> to an ancestor. Staying at $v$ is allowed. Ignore the reverse traversal of the discovery <edge> to the <parent in a rooted tree>: it is the same <edge>, not an escape route. Start with $\operatorname{low}(v)=\operatorname{disc}(v)$. On returning from a <child in a rooted tree> $w$, replace $\operatorname{low}(v)$ by $\min\{\operatorname{low}(v),\operatorname{low}(w)\}$. For a non-discovery <edge> from $v$ to an earlier ancestor $a$, replace it by $\min\{\operatorname{low}(v),\operatorname{disc}(a)\}$. This summarizes how far upward the explored branch can reconnect. https://sites.cs.ucsb.edu/~gilbert/cs240a/notes/TarjanDFS.pdf[Tarjan (1972), §3, LOWPT recurrence, pp. 151–153]{ref}
The <cut vertex> criterion has a separate case for each <root of a tree> in the discovery <forest>:
* A nonroot <vertex> $u$ is a <cut vertex> exactly when some <child in a rooted tree> $w$ satisfies $\operatorname{low}(w)\geq\operatorname{disc}(u)$.
* A <root of a tree> is a <cut vertex> exactly when it has at least two <children in a rooted tree>, counting discovery <edges>, rather than all <graph neighbours>.
* A discovery <edge> $uw$ is a <bridge in a graph> exactly when $\operatorname{low}(w)>\operatorname{disc}(u)$. A non-discovery <edge> is never a <bridge in a graph>.
Why does equality matter? If $\operatorname{low}(w)=\operatorname{disc}(u)$, the branch below $w$ can reconnect to $u$, so the discovery <edge> $uw$ lies on a <graph cycle> and is not a <bridge in a graph>. Deleting the <vertex> $u$ destroys that reconnection too. If $u$ has a <parent in a rooted tree>, the branch is then separated from that <parent in a rooted tree>, explaining the non-strict <cut vertex> test. For a <root of a tree>, there is no earlier side to separate from; distinct discovery branches cannot have an <edge> between them, since <depth-first search> would have explored them as one branch. This gives the two-<children in a rooted tree> rule. These are proof outlines of the criteria. https://algs4.cs.princeton.edu/41graph/Biconnected.java.html[Sedgewick and Wayne, Biconnected.java: discovery, lowpoint and root tests]{ref}https://algs4.cs.princeton.edu/41graph/[Sedgewick and Wayne, Algorithms, §4.1: bridge detection]{ref}
In the joined-$CD$ example with <DFS discovery times> $1,2,3,4,5,6$, the <DFS lowpoints> in label order are $1,1,1,4,4,4$. For $C$ and its <child in a rooted tree> $D$, $4>3$: $CD$ is a <bridge in a graph>, and $C$ is a <cut vertex>. For $D$ and its <child in a rooted tree> $E$, $4=4$: $D$ is a <cut vertex>, although $DE$ is not a <bridge in a graph>. The <root of a tree> $A$ has only one <child in a rooted tree>, $B$, so it is not a <cut vertex>. In the shared-$A$ example, the <root of a tree> $A$ has two <children in a rooted tree>, $B$ and $D$, and is a <cut vertex>, while every <DFS lowpoint> is $1$ and no <edge> passes the strict <bridge in a graph> test.
Restart <depth-first search> at every undiscovered <vertex> to cover a disconnected <graph>, applying the <root of a tree> rule separately in each <connected component of a graph>. With <adjacency lists> and constant-cost label operations, computing all <DFS lowpoints>, <cut vertices> and <bridges in a graph> has <time complexity> $O(|V|+|E|)$ in <Big O notation>, because each <vertex> is discovered once and each <edge> is inspected twice. The simple parent-skipping rule assumes a <simple graph>. In a <multigraph>, skip only the actual parent <edge>, identified individually: a parallel <edge> to the same <parent in a rooted tree> is a valid reconnection and can prevent the first <edge> from being a <bridge in a graph>. The criteria here concern <undirected graphs>; a <directed graph> requires a different connectivity analysis.
Back to article page
