New answers tagged

1

Here is a definition of $O$ for one variable from Cormen, Introduction to Algorithms: $f(n) = O(g(n))$ means there exist positive constants $c$ and $n_0$ such that $0 \leq f(n) \leq cg(n)$ for all $n \geq n_0$. The extension to multiple variables is obvious: $f(m,n) = O(g(m,n))$ means there exist positive constants $c$ and $n_0$ such that $0 \leq f(m,n) \leq ...


7

The problem is L-complete. It’s easier to think about it when the edges are written backwards. That is, I will consider the problem formulated as follows: given a directed acyclic graph such that every node has out-degree at most $1$, and vertices $s$ and $t$, determine if $t$ is reachable from $s$. To see that it is in L, just follow the unique path ...


8

I don't know any publication where this is stated, but it is an $NLOGSPACE$-complete. For the lower bound one can give a reduction from the reachability problem, which is the problem of determining whether there is a path between two vertices $s$ and $t$ in a given (directed) graph $G= (V,E)$. Indeed, the following formula $$p_s \land \bigwedge_{(v,u) \in E} ...


Top 50 recent answers are included