Tarjan-Vishkin Algorithm

Purpose: Compute biconnected components in $O(\log n)$ parallel time using $O(n+m)$ processors — a classic PRAM algorithm (1985). Sequentially it is $O(n+m)$, the same as Tarjan’s DFS version, but with no recursion and no inherently sequential DFS.

Why DFS is a problem in parallel

Tarjan’s biconnectivity algorithm relies on DFS discovery times and low values, and depth-first search is P-complete — believed to have no efficient parallel algorithm. Tarjan-Vishkin sidesteps this by replacing “DFS structure” with “spanning tree + auxiliary graph connectivity”, both of which parallelise well.

Algorithm

1. Spanning tree. Build any spanning tree $T$ (in parallel, via pointer jumping or a randomized approach).
2. Euler tour. Compute an Euler tour of $T$ and, from it, preorder numbers and subtree sizes using list ranking — the fundamental parallel primitive, $O(\log n)$ time.
3. Low/high values. For each vertex compute low[v] and high[v] (the minimum and maximum preorder numbers reachable from $v$‘s subtree via one non-tree edge) with parallel prefix operations over the Euler tour.
4. Auxiliary graph $G^{\prime }$. Build a graph whose vertices are the edges of $G$, connecting two edges when they are known to lie in the same biconnected component. The connection rules are local tests on low/high and the tree structure — all evaluable in parallel.
5. Connected components of $G^{\prime }$. Each component is one biconnected component of $G$. Parallel connectivity is $O(\log n)$ by pointer jumping / hooking.

Complexity

• Parallel: $O(\log n)$ time with $O(n+m)$ processors on a CRCW PRAM
• Work: $O((n+m)\log n)$ — not quite work-optimal, but close
• Sequential simulation: $O(n+m)$

Why it’s worth knowing

Two transferable ideas:

1. Euler tour technique. Turning a tree into a list, then answering subtree queries with prefix sums over that list, is the foundation of Euler tour trees, subtree updates on a BIT, and LCA via RMQ. Tarjan-Vishkin is where the technique was introduced.
2. Replacing DFS with a spanning tree plus local tests. Whenever an algorithm “needs DFS”, ask whether it really needs the order or just the tree. Often the tree suffices, and then the algorithm parallelises.

Sequential alternative

For any contest, write Tarjan’s DFS-based algorithm: one pass, disc/low arrays, an edge stack, about 30 lines. See Bridges and Articulation Points and Biconnected Components.

Variants / Use Cases

• Parallel connected components, MST, and list ranking — the same PRAM toolkit
• Euler Tour technique — the reusable idea
• Block-cut tree — what you build once you have the biconnected components
• Schieber-Vishkin LCA — the same Vishkin, another $O(1)$-query structure with parallel origins