Trading Determinism for Time in Space Bounded Computations

Introduction

Deciding reachability between a pair of vertices in a graph is an important computational problem from the perspective of space bounded computations. It is well known that reachability in directed graphs characterizes the complexity class nondeterministic logspace (\NL). For undirected graphs the problem was known to be hard for the class deterministic logspace (Ł) and in a breakthrough result Reingold showed that is contained in Ł as well [Rei08]. Several other restrictions of the reachability problem are known to characterize other variants of space bounded complexity classes [Ete97, Bar89, BLMS98].

Unambiguous computations are a restriction of general nondeterministic computations where the Turing machine has at most one accepting computation path on every input. In the space bounded domain, unambiguous logspace (in short \UL) is the class of languages for which there is a nondeterministic logspace bounded machine that has a unique accepting path for every input in the language and zero accepting path otherwise. \UL was first formally defined and studied in [BJLR91, AJ93]. In 2000 Reinhardt and Allender showed that the class \NL is contained in a non-uniform version of \UL [RA00]. In a subsequent work it was shown that under the hardness assumption that deterministic linear space has functions that cannot be computed by circuits of size $2^{\epsilon n}$, it can be shown that $\NL=\UL$ [ARZ99]. Although it is widely believed that \NL and \UL are the same unconditionally and in a uniform setting, the question still remains open.

Savitch’s Theorem states that reachability in directed graphs is in $\DSPACE(\log^{2}n)$, however the algorithm requires quasipolynomial time [Sav70]. On the other hand standard graph traversal algorithms such as DFS and BFS can decide reachability in polynomial time (in fact linear time) but require linear space. Wigderson asked the question that can we solve reachability in $\mathcal{O}(n^{1-\epsilon})$ space and polynomial time simultaneously, for some $\epsilon>0$ [Wig92]. Barnes et. al. gave a partial answer to this question by giving a $\mathcal{O}(n/2^{\sqrt{\log n}})$ space and polynomial time algorithm for the problem [BBRS92]. Although this bound has been improved for several subclasses such as planar graphs [INP+13], layered planar graphs [CT15], minor-free and bounded genus graphs [CPT+14], for general directed graphs (and hence for the class \NL) we still do not have a better deterministic space upper bound simultaneously with polynomial time.

In this paper we show that directed graph reachability can be decided by an unambiguous $\mathcal{O}(\log^{2}n)$ space algorithm that simultaneously requires only polynomial time. Thus we get an improvement in the time required by Savitch’s algorithm by sacrificing determinism. Formally, we show the following theorem.

For the remainder of this paper all graphs that we consider are directed graphs unless stated otherwise.

2 Min-uniqueness of Graphs

An important ingredient of our proof is the min-uniqueness property of graphs. A graph $G$ is said to be min-unique with respect to an edge weight function $W$ if the minimum weight path between every pair of vertices in $G$ is unique with respect to $W$. This turns out to be an important property and has been studied in earlier papers [Wig94, GW96, RA00]. In fact, the fundamental component of Reinhardt and Allender’s paper is a \UL algorithm for testing whether a graph is min-unique and then deciding reachability in min-unique graphs in \UL [RA00]. They achieve this by proposing a double inductive counting technique which is a clever adaptation of the inductive counting technique of Immerman and Szelepcsényi [Imm88, Sze88]. As a result of Reinhardt and Allender’s algorithm, in order to show that reachability in a class of graphs can be decided in \UL, one only needs to design an efficient algorithm which takes as input a graph from this class and outputs an $\mathcal{O}(\log n)$ bit weight function with respect to which the graph is min-unique. This technique was successfully used to show a \UL upper bound on the reachability problem in several natural subclasses of general graphs such as planar graphs [BTV07], graphs with polynomially many paths from the start vertex to every other vertex [PTV12], bounded genus graphs [DKTV11] and minor-free graphs [AGGT16]. For the latter two classes of graphs reachability was shown to be in \UL earlier as well by giving reductions to planar graphs [KV10, TW09]. Note that Reinhardt and Allender defines min-uniqueness for unweighted graphs where the minimum length path is unique, whereas we define it for weighted graphs where the minimum weight path is unique. However it can easily be seen that both these notions are equivalent.

3 Overview of the Proof

We prove Theorem 1 in two parts. We first show how to construct an $\mathcal{O}(\log^{2}n)$ bit weight function $W$ with respect to which the input graph $G$ becomes min-unique. Our construction of the weight function $W$ uses an iterative process to assign weights to the edges of $G$. We start by considering a subgraph of $G$ having a fixed radius and construct an $\mathcal{O}(\log n)$ bit weight function with respect to which this subgraph becomes min-unique. For this we first observe that there are polynomially many paths in such a subgraph and then use the prime based hashing scheme of Fredman, Komlós and Szemerédi [FKS84] to give distinct weights to all such paths. Thereafter, in each successive round of the algorithm, we construct a new weight function with respect to which a subgraph of double the radius of the previous round becomes min-unique and the new weight function has an additional $\mathcal{O}(\log n)$ bits. Hence in $\mathcal{O}(\log n)$ many rounds we get a weight function which has $\mathcal{O}(\log^{2}n)$ bits and with respect to which $G$ is min-unique. We show that this can be done by an unambiguous, polynomial time algorithm using $\mathcal{O}(\log^{2}n)$ space. This technique is similar to the isolating weight construction in [FGT16], but their construction is in \qNC.

We then show that given a graph $G$ and an $\mathcal{O}(\log^{2}n)$ bit weight function with respect to which $G$ is min-unique, reachability in $G$ can be decided by an unambiguous, polynomial time algorithm using $\mathcal{O}(\log^{2}n)$ space. Note that a straightforward application of Reinhardt and Allender’s algorithm will not give the desired bound. This is because “unfolding” a graph with $\mathcal{O}(\log^{2}n)$ bit weights will result in a quasipolynomially large graph. As a result we will not achieve a polynomial time bound. We tackle this problem by first observing that although there are $2^{\mathcal{O}(\log^{2}n)}$ many different weight values, the weight of a shortest path can only use polynomial number of distinct such values. Using this observation we give a modified version of Reinhardt and Allender’s algorithm that iterates over the “good” weight values and ignores the rest. This allows us to give a polynomial time bound.

The rest of the paper is organized as follows. In Section 2 we define the various notations and terminologies used in this paper. We also state prior results that we use in this paper. In Section 3 we give the proof of Theorem 1.

Preliminaries

Correspondingly we define the function $l$ which represents the minimum length of such paths as

A graph $G_{w}$ is said to be min-unique for paths of length at most $i$, if for any pair of vertices $u$ and $v$, the shortest path from $u$ to $v$ with length at most $i$, is unique. $G_{w}$ is said to be min-unique if $G_{w}$ is min unique for paths of arbitrary length. Define weight function

For a graph $G_{w}$, vertex $u$ in $G$, length $i$ and weight value $k$, we define the quantities $c_{k}^{i}(u)$ and $D_{k}^{i}(u)$ as the number of vertices at a distance at most $k$ from $u$, using paths of length at most $i$ and the sum of the distances to all such vertices respectively. Formally,

An unambiguous Turing machine is a nondeterministic Turing machine that has at most one accepting computation path on every input [Val76]. We shall consider unambiguous computations in the context of space bounded computations. $\USPACE(s(n))$ denotes the class of languages decided by an unambiguous machine using $\mathcal{O}(s(n))$ space. In particular, $\UL=\USPACE(\log n)$. $\TIUSP(t(n),s(n))$ denotes the class of languages decided by an unambiguous machine using $\mathcal{O}(s(n))$ space and $\mathcal{O}(t(n))$ time simultaneously. In particular, when $t(n)$ is a polynomial, we define

For graphs having polynomially many paths, we use the well known hashing technique due to Fredman, Komlós and Szemerédi [FKS84] to compute a weight function that assigns distinct weights to all such paths. We state the result below in a form that will be useful for our purpose.

[FKS84, PTV12] For every constant $c$ there is a constant $c^{\prime}$ so that for every set $S$ of $n$ bit integers with $|S|\leq n^{c}$ there is a $c^{\prime}\log n$ bit prime number $p$ so that for all $x\neq y\in S,\ x\not\equiv y\bmod{p}$.

Henceforth we will refer to Theorem 2 as the FKS hashing lemma.

Min-unique Weight Assignment

Reinhardt and Allender [RA00] showed that for every $n$ there is a sequence of $n^{2}$ $\mathcal{O}(\log n)$ bit weight functions such that every graph $G$ on $n$ vertices is min-unique with respect to at least one of them. For each weight function they construct an unweighted graph (say $G_{w}$) by replacing every edge with a path of length equal to the weight of that edge. Since the weights are $\mathcal{O}(\log n)$ bit values therefore $G_{w}$ is polynomially large in $n$. Next they show that using the double inductive counting technique one can check unambiguously using a logspace algorithm if $G_{w}$ is min-unique, and if so then check if there is a path from $s$ to $t$ as well. They iterate over all weight functions until they obtain one with respect to which $G_{w}$ is min-unique and use the corresponding graph $G_{w}$ to check reachability. Since we use an $\mathcal{O}(\log^{2}n)$ bit weight function with respect to which the input graph is min-unique, we cannot construct an unweighted graph by replacing every edge with a directed path of length equal to the corresponding edge weight.

Theorem 3 shows how to construct the desired weight function.

There is a nondeterministic algorithm that takes as input a directed graph $G$ and outputs along a unique computation path, an $\mathcal{O}(\log^{2}n)$ bit weight function $W$ such that $G_{W}$ is min-unique, while all other computation paths halt and reject. For any two vertices $s$ and $t$ the algorithm also checks whether there is a path from $s$ to $t$ in G. The algorithm uses $\mathcal{O}(\log^{2}n)$ space and runs in polynomial time.

Since directed graph reachability is complete for \NL, Theorem 1 follows from Theorem 3.

To prove Theorem 3 we design an algorithm that outputs the desired weight function. The formal description of the construction is given in Algorithm 1. The algorithm works in an iterative manner for $\log n$ number of rounds. Initially we consider all paths in $G$ of length at most $l$ where $l=2^{1}$. The number of such paths is bounded by $n^{l}$ and therefore by the FKS hashing lemma there exist a $c^{\prime}\log n$ bit prime $p_{1}$ such that with respect to the weight function $W_{1}:=w_{0}\bmod p_{1}$, $G_{w_{1}}$ is min-unique for paths of length at most $l$. To find the right prime $p_{1}$ we iterate over all $c^{\prime}\log n$ bit primes and use Lemma 7 to check whether $G_{w_{1}}$ is min-unique for paths of length at most $l$.

We prove this by induction on the number of rounds, say $j$. Assume that $G_{W_{j-1}}$ is min-unique for paths of length at most $2^{j-1}$. In the $j$-th round, the algorithm considers all paths of length at most $2^{j}$. By applying Lemma 4 we get a weight function $W_{j}$ from $W_{j-1}$ which uses $\mathcal{O}(j\cdot\log n)$ bits and $G_{W_{j}}$ is min-unique for paths of length at most $2^{j}$. Hence in $\log n$ many rounds we get a weight function $W:=W_{\log n}$ such that $G_{W}$ is min-unique. Note that the inner repeat-until loop runs for at most $n^{c^{\prime}}$ iterations due to the FKS hashing lemma.

Let $p_{j}$ be the prime used in the $j$-th round of Algorithm 1. Define $p^{\prime}:=\max\{p_{j}\mid j\in[\log n]\}$. By the FKS hashing lemma $p^{\prime}$ is bounded by a polynomial in $n$, say $n^{c^{\prime}}$. We set $B:=n^{c^{\prime}+2}$. This implies that for any weight function of the form $w=w_{0}\bmod p_{j}$ and any path $P$ in $G$, $w(P)<B$. Observe that with respect to the final weight function $W$, for any path $P$ in $G$, $W(P)<B^{q}$.

In each round the size of $W_{j}$ increases by $\mathcal{O}(\log n)$ bits and after $\log n$ rounds $W_{\log n}$ is an $\mathcal{O}(\log^{2}n)$ bit weight function. By Lemma 7 checking whether a graph is min-unique with respect to an $\mathcal{O}(\log^{2}n)$ bit weight function requires $\mathcal{O}(\log^{2}n)$ space. Thus the total space complexity of Algorithm 1 is $\mathcal{O}(\log^{2}n)$.

The FKS hashing lemma guarantees that in each round only a polynomial number of primes need to be tested to find a weight function which is min-unique for paths of length at most $2^{j}$. By Lemma 7 checking whether a graph is min-unique for paths of length at most $2^{j}$ can be done in polynomial time. Thus each round runs in polynomial time. There are only $\log n$ many round and hence Algorithm 1 runs in polynomial time.

By Lemma 7, Algorithm 2 is a nondeterministic algorithm which outputs its answer along a unique computation path, while all other computation paths halt and reject. All other steps in Algorithm 1 are deterministic. This shows the unambiguity requirement of the theorem. ∎

There is a nondeterministic algorithm $\mathcal{A}$, that takes as inputs $(G,w)$ where $G$ is a graph on $n$ vertices and $w$ is a $k$ bit weight function such that $G_{w}$ is min-unique for paths of length at most $l$. $\mathcal{A}$ outputs a $(k+\mathcal{O}(\log n))$ bit weight function $w^{\prime}$ such that $G_{w^{\prime}}$ is min-unique for paths of length at most $2l$, along a unique computation path while all other computation paths halt and reject. $\mathcal{A}$ uses $\mathcal{O}(k+\mathcal{O}(\log n))$ space and runs in polynomial time.

The encoding of the output weight function $w^{\prime}$ is the concatenation of the $k$ bit representation of the input weight function $w$ and an $\mathcal{O}(\log n)$ bit prime number $p$. The output weight function $w^{\prime}$ is calculated as $w^{\prime}:=B\cdot w+w_{0}\bmod p$, where $B$ is the number defined in Algorithm 1. Multiplication using $B$ is used just to left shift $w$ and make room for the new function $w_{0}\bmod p$.

Lemma 4 proves the correctness of each iteration of the outer for loop of Algorithm 1. Before proving the lemma, we will show that if $G_{w}$ is min-unique for paths of length at most $l$, then the number of minimum weight paths with respect to $w$ of length at most $2l$ is bounded by a polynomial independent of $l$. Hence it allows us to use the FKS hashing lemma to isolate such paths.

Let $G$ be a graph with $n$ vertices and $w$ be a weight function such the graph $G_{w}$ is min-unique for paths of length at most $l$. Then for any pair of vertices $u$ and $v$, $\left|\mathcal{P}_{w}^{2l}(u,v)\right|$ is at most $n$.

Let $P$ be a shortest path from $u$ to $v$ in $G_{w}$ with length at most $2l$ with center vertex $x$. That is $P\in\mathcal{P}_{w}^{2l}(u,v)$. Let $P_{1}$ and $P_{2}$ be the subpaths from $u$ to $x$ and $x$ to $v$. Since $x$ is the center of $P$, $P_{1}$ has length at most $l$. Note that $P_{1}$ is the unique shortest path of length at most $l$ from $u$ to $x$ in $G_{w}$. This is because if there exists another path of length at most $l$ with a smaller weight than $P_{1}$ from $u$ to $x$ then replacing $P_{1}$ with this path in $P$ will result in a path of length at most $2l$ from $u$ to $v$ with a lower weight than $P$. But this cannot happen since $P$ is a shortest path from $u$ to $v$.

There is only one shortest path of length at most $2l$ from $u$ to $v$ with $x$ as its center.

Assume there is another shortest path $P^{\prime}$ of length at most $2l$ from $u$ to $v$ with $x$ as its center. Let $P_{1}^{\prime}$ be the subpath of $P^{\prime}$ from $u$ to $x$. Since $x$ is the center of $P^{\prime}$, $P^{\prime}_{1}$ is of length at most $l$. Similar to $P_{1}$, $P^{\prime}_{1}$ is a shortest path of length at most $l$ from $u$ to $x$. This means there are two shortest paths of length at most $l$ from $u$ to $x$. This is a contradiction since $G$ is min-unique for paths of length at most $l$. ∎

Therefore each vertex can be the center of at most one path of length at most $2l$ from $u$ to $v$. Thus the total number of shortest paths of length at most $2l$ from $u$ to $v$ in $G_{w}$ is at most $n$. Hence $\left|\mathcal{P}_{w}^{2l}(u,v)\right|\leq n$. This completes the proof of Lemma 5. ∎

When we sum over all possible pairs of $u$ and $v$, the total number of shortest paths of length at most $2l$ in $G_{w}$ is at most $n^{3}$.

$G_{w}$ is min-unique for paths of length at most $l$. Therefore by Lemma 5 the number of shortest paths between all pairs of vertices with at most $2l$ edges in $G$ is at most $n^{3}$. Let $\mathcal{S}$ be the set of these $n^{3}$ shortest paths. With respect to the weight function $w_{0}$ (see Section 2) each element of $\mathcal{S}$ gets a distinct weight. So by using the FKS hashing lemma we get a constant $c^{\prime}$ and a $c^{\prime}\log n$ bit prime number $p$ such that with respect to the weight function $\widehat{w}$ such that $\widehat{w}:=w_{0}\bmod p$, each element of $\mathcal{S}$ gets a distinct weight. Moreover, in $G$ between any pair of vertices the shortest path in $\mathcal{S}$ is unique.

Let $B$ be the number as defined in Algorithm 1. Now consider the weight function $w^{\prime}:=B\cdot w+\widehat{w}$. Since $w$ is a $k$ bit weight function and $\widehat{w}$ is an $\mathcal{O}(\log n)$ bit weight function therefore $w^{\prime}$ is a $(k+\mathcal{O}(\log n))$ bit weight function. Clearly $w$ has higher precedence than $\widehat{w}$ in $w^{\prime}$. So for any two paths $P_{1}$ and $P_{2}$ in $G$ , we have if $w^{\prime}(P_{1})<w^{\prime}(P_{2})$ then either $w(P_{1})<w(P_{2})$ or both the predicates $w(P_{1})=w(P_{2})$ and $\widehat{w}(P_{1})<\widehat{w}(P_{2})$ are true. Additionally if $w^{\prime}(P_{1})=w^{\prime}(P_{2})$ then $w(P_{1})=w(P_{2})$ and $\widehat{w}(P_{1})=\widehat{w}(P_{2})$.

All the unique shortest paths of length at most $2l$ in $G_{w}$, will be unique shortest paths of length at most $2l$ in $G_{w^{\prime}}$ also. If there are multiple shortest paths of length at most $2l$ from $u$ to $v$ in $G_{w}$, $\widehat{w}$ gives a unique weight to each of these paths. So $G_{w^{\prime}}$ is min-unique for paths of length at most $2l$.

We can check whether a graph $G_{w^{\prime}}$ is min-unique for paths of length at most $2l$ using Lemma 7. Since $p$ is an $c^{\prime}\log n$ bit prime number, we can iterate over all the $c^{\prime}\log n$ bit primes and find $p$. ∎

2 Checking for min-uniqueness

The next lemma shows how to check whether $G_{w}$ is min-unique for paths of length at most $l$ in an unambiguous manner.

There is a nondeterministic algorithm that takes as input a directed graph $G$, a $k$ bit weight function $w$ and a length $i$ and outputs along a unique computation path whether or not the graph $G_{w}$ is min-unique for paths of length at most $i$, while all other computation paths halt and reject. The algorithm uses $\mathcal{O}(k+\log n)$ space and runs in polynomial time.

For every vertex $v$ in the $G_{w}$ we check whether there are two minimum weight paths of length at most $i$ to some other vertex in $G$. Algorithm 2 gives a formal description of this process. The algorithm iterates over all shortest path weight values that can be achieved by some path of length at most $i$.

In the $k$-th stage of the algorithm it considers a ball of radius $k$ consisting of vertices which have a shortest path of weight at most $k$ from $v$ and length at most $i$. $c_{k}^{i}(v)$ denotes the number of vertices in this ball and $D_{k}^{i}(v)$ denotes the sum of the weights of the shortest paths to all such vertices. Initially $k=0$, $c_{0}^{i}(v)=1$ (consisting of only the vertex $v$) and $D_{0}^{i}(v)=0$.

A direct implementation of the double inductive counting technique of Reinhardt and Allender [RA00] does not work since this would imply that we cycle over all possible weight values, which we cannot afford. We bypass this hurdle by considering only the relevant weight values. We compute the immediate next shortest path weight value $k^{\prime}$, and use $k^{\prime}$ as the weight value for the next stage of the algorithm. This computation is implemented in Algorithm 3). Lemma 8 proves the correctness of this process. Note that the number of shortest path weight values from a fixed vertex is bounded by the number of vertices in the graph. This ensure that the number of iterations of the inner repeat-until loop of Algorithm 2 is bounded by $n$.

After we get the appropriate weight value $k^{\prime}$, we then compute the values of $c_{k^{\prime}}^{i}(v)$ and $D_{k^{\prime}}^{i}(v)$ by using a technique similar to Reinhardt and Allender (implemented in Algorithm 4). Additionally we also maintain a shared flag value $\mathsf{BAD.WEIGHT}$ between Algorithms 2 and 4, which is set to $\mathsf{true}$ if $G_{w}$ is not min-unique for paths of length at most $i$, else it is $\mathsf{false}$.

Note that Algorithm 5 is the only algorithm where we use non-determinism. The algorithm is similar to the unambiguous subroutine of Reinhardt and Allender [RA00] with the only difference being that here we consider weight of a path instead of length of a path. The algorithm assumes that the subgraph induced by all the paths of length at most $i$ and weight at most $k$ from $u$ is min-unique.

As a corollary of Theorem 1 we get the following result.

For $s(n)\geq\log n$, $\NSPACE(s(n))\subseteq\TIUSP(2^{\mathcal{O}(s(n))},s^{2}(n))$.

References