$$

Adapted from a talk by Prasanna Ramakrishnan at Stanford’s teach-us-anything seminar.

You probably know the drill about $s$-$t$ connectivity:

• DFS/BFS gets you $\mathsf{TISP}(m,n)$,¹
• Savitch’s gets you $\mathsf{TISP}(n^{O(\log n)},{\log }^{2}n)$.

Can you get the best of both worlds? Some believe $\mathsf{TISP}(\mathrm{poly}(n),\mathrm{polylog}(n))$ is possible. But for now, the best we can get in polynomial time is $n/2^{\mathrm{\Omega }(\sqrt{\log n})}$ space.²

Idea

Pras claims that if you’re given one week and the hint “find something in the middle of BFS and Savitch’s”, you could come up with it. I doubt I could.

The idea is to split the problem into two parts:

• one BFS-like part that “splits the path from $s$ to $t$ into $n/\lambda$ segments of length $\lambda$”;
• one Savitch-like part that can check whether two nodes are at distance $\le \lambda$ (as long as $\lambda$ is small).

The BFS-like part makes a lot of concessions in time in order to cut space. The Savitch-like part makes a lot of concessions in space in order to cut time.

BFS-like part: cut it up

BFS requires a lot of space to store all the “equidistance shells”: for each $d$, it stores the set$V_d$ of all vertices at distance $d$ from node $s$. One natural way to save on this is to only store one out of $\lambda$ of those shells: there must be some remainder $r$ such that the shells $V_r,V_{\lambda +r},V_{2\lambda +r},\dots$ contain only $O(n/\lambda )$ nodes.

How do you compute $V_{(i+1)\lambda +r}$ from the previous ones though? The idea is that $v\in V_{(i+1)\lambda +r}$ if and only if:

• it’s at distance exactly $\lambda$ from $V_{i\lambda +r}$;
• it’s not in any of the earlier shells $V_0,\dots ,V_{i\lambda +r-1}$.

The first part is easy to check using two small-distance queries from each $w\in V_{i\lambda +r}$. And you can check the second part simply by checking that $v$ is not a distance $<\lambda$ from the previous shells we memorized $V_r,\dots ,V_{(i-1)\lambda +r}$. That’s a lot of queries, but we’re fine with polynomial blow-ups in time!

Overall, we only make a polynomial number of queries, and we need $O(\frac{n\log n}{\lambda })$ bits of memory to store all the shells $V_r,V_{\lambda +r},\dots$. So if there was some $\mathsf{TISP}(t(n,\lambda ),s(n,\lambda ))$ way to check whether two points are at distance at most $\lambda$, we could solve STCON in

$$\mathsf{TISP}(\mathrm{poly}(n)\cdot t(n,\lambda ),\frac{n\log n}{\lambda }+s(n,\lambda )).$$

This means that to get poly-time sublinear-space connectivity, we need

• $\lambda \ge \omega (\log n)$;
• $t(n,\lambda )\le \mathrm{poly}(n)$;
• $s(n,\lambda )\le o(n)$.

Savitch-like part

Let’s figure what time-space trade-off we can get from Savitch assuming $s$ and $t$ are at distance $\le \lambda$. Out of the box, it gets you $n^{O(\log \lambda )}$ time and $O(\log n\log \lambda )$ space. Since $\lambda$ is superconstant, this is definitely not going to be polynomial-time, but this is already something nontrivial: for example, setting $\lambda =(\log n{)}^{100}$ gets you $\mathsf{TISP}(n^{O(\log \log n)},n/(\log n{)}^{99})$, which is incomparable with BFS and Savitch’s.

But really, out-of-the-box Savitch’s cares way too much about optimizing space. We only want sublinear space (we have this annoying $\frac{n\log n}{\lambda }$ anyway), so we should be able to do much better!

The trick is to reduce Savitch’s branching factor at the expense of space. Instead of choosing a specific middle vertex among all $n$ possible vertices, we’ll choose a collection of possible middle vertices among $k$ collections of $n/k$ vertices (decided arbitrarily, say by their remainder modulo $k$).

The specification of one recursion of Savitch’s then becomes:

$\mathrm{Savitch}(d,i\in [k],j\in [k],x\in {\{0,1\}}^{n/k})$: returns a vector $y\in {\{0,1\}}^{n/k}$ representing which nodes from collection $j$ are reachable within distance $\le d$ from at least one of the nodes in collection $i$ that are indicated by a $1$ in $x$.

To solve this recursive problem, first initialize $y\leftarrow 0^{n/k}$, then for each possible “middle collection” $l\in [k]$:

• make a recursive call to find out the vector $z\in {\{0,1\}}^{n/k}$ of each possible node in collection $l$ that is reachable within distance $\le d/2$ from at least one of the nodes in collection $i$ indicated by $x$;
• make a second recursive call to find out the vector $w\in {\{0,1\}}^{n/k}$ of each possible node in collection $j$ that is reachable within distance $\le d/2$ from at least one of the nodes in collection $l$ indicated by $z$;
• set $y\leftarrow y\vee w$ (component-wise).

Overall, there are $\log \lambda$ recursion levels, the branching factor is $k$, and we need $\mathrm{poly}(n)$ time and $O(n/k+\log k)$ memory at each recursion level, so this gives

$$\mathsf{TISP}(\mathrm{poly}(n)\cdot k^{O(\log \lambda )},(\log \lambda )(n/k+\log k)).$$

Choosing parameters

Let’s ignore the $+\log k$, it will end up being small anyway. We’re left with

$$\mathsf{TISP}(\mathrm{poly}(n)\cdot k^{O(\log \lambda )},\frac{n\log n}{\lambda }+\frac{n\log \lambda }{k}).$$

The log factors in the right-hand side are probably not going to be very different, so a reasonable first step is to equalize the denominators by setting $k:=\lambda$, and get

$$\mathsf{TISP}(\mathrm{poly}(n)\cdot {\lambda }^{O(\log \lambda )},\frac{n\log n}{\lambda }).$$

Then, it only remains to solve for ${\lambda }^{O(\log \lambda )}\le \mathrm{poly}(n)$, which holds as long as $\lambda \le 2^{O(\sqrt{\log n})}$. So the best³ bound we can get for polynomial time is

$$\mathsf{TISP}(\mathrm{poly}(n),\frac{n}{2^{\mathrm{\Omega }\left(\sqrt{\log n}\right)}}).$$

1. $\mathsf{TISP}(t(n),s(n))$ is the class of problems solvable in time $O(t(n))$ and space $O(s(n))$ simultaneously. ↩

2. Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, Baruch Schieber, “A sublinear pace, polynomial time algorithm for directed s-t connectivity”. ↩

3. Actually you get to choose whatever constant you want for the $\mathrm{\Omega }(\cdot )$. ↩