= Solution
Split a <graph path> of length at most $2k$ into two consecutive parts of length at most $k$, allowing a zero-length part. Conversely, concatenating two such parts gives a <walk> of length at most $2k$ and hence the same <reachability>. Therefore
$$
\boxed{P_{2k}=P_k\odot P_k.}
$$
Start at $P_1=I\lor E$, then square to obtain $P_2,P_4,P_8,\ldots$. Stop at equality of successive <matrices>, or after the length bound reaches $n-1$. The invariant is now $P=P_{2^r}$ after $r$ squarings. Equality implies closure under composition, and the included <identity matrix> ensures <reflexivity>.
For the same elementary dense <Boolean matrix multiplication> and equality stopping test, the cost is
$$
\boxed{T_{\mathrm{square}}=\Theta\!\left(n^3(1+\log(m+1))\right),\qquad \text{space}=\Theta(n^2).}
$$
The additive constant covers the final stability check and the cases $m=0,1$. Thus, with $m\geq2$, the number of cubic passes falls from $\Theta(m)$ to $\Theta(\log m)$. In terms of $n$ alone the worst-case bound improves from $\Theta(n^4)$ to $\Theta(n^3\log n)$ for these implementations. A directed chain also requires logarithmically many squarings. This comparison uses ordinary triple-loop multiplication, rather than a faster <matrix multiplication> method.
Back to article page
