Directed reachability (or briefly reachability) is the following decision problem: given a directed graph G and two of its vertices s,t, determine whether there is a directed path from s to t in G. Directed reachability is a standard complete problem for the complexity class NL. Planar reachability is an ... more >>>

In this paper, we study the circuit value problem for monotone Boolean circuits (that is, circuits without negation gates) when the circuits are embedded on a surface of bounded genus, and all inputs to the circuits lie on at most constantly many faces. We show that this problem can be ... more >>>

We study the parallel complexity of computing the arboricity of a graph, defined as the minimum number of forests into which its edges can be partitioned.
For graphs of bounded treewidth, we present a simple dynamic programming–based parallel algorithm that constructs an optimal partition of the edges into forests.
For ... more >>>