Savitch's algorithm

This solves the STCON (s-t connectivity) problem—finding a path between two nodes in a directed graph using \(O(\log ^2 n)\) space.

It defines a function Path\((u,v,k)\) to check if there is a path from \(u\) to \(v\) of length at most \(2^k\).

To compute Path(a, b, k), it uses the following divide and conquer technique:

• Base case: If k = 0, return true if (a, b) is an edge or a = b (0-length path).
• Recursive case: For each possible intermediate node w (iterate over all n nodes), check if Path(a, w, k/2) and Path(w, b, k/2). Return true if any w works.

The pseudo code can be written as:

reachable_within_t_steps(u, v, t): # letting this be the recurrence
	if u == v: return true
	else if t == 1: return true if (u, v) in E else false

	for m in 0, 1, …, n - 1:
	if reachable_within_t_steps(u, m, floor(t/2)) and
			reachable_within_t_steps(m, v, ceil(t/2)))
		return true
	return false

The algorithm works on the idea that there must be an intermediate node \(m\).

The algorithm is not efficient in terms of time complexity. It achieves a time complexity of \(O(n^{\log n})\) which is superpolynomial. However, this is the most space optimal algorithm available to solve the connectivity problem.

Node indices and k need O(log n) bits each.

Recursion stack has depth O(log n), so total space is \(O(\log² n)\).

No extra graph storage beyond adjacency list access (read-only).