ECCC-Report TR09-050https://eccc.weizmann.ac.il/report/2009/050Comments and Revisions published for TR09-050en-usThu, 02 Jul 2009 07:01:21 +0300
Paper TR09-050
| Logspace reduction of directed reachability for bounded genus graphs to the planar case |
Jan Kyncl,
Tomas Vyskocil
https://eccc.weizmann.ac.il/report/2009/050Directed 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 important restricted version of the reachability problem, where the input graph is planar. Planar reachability is hard for L and is contained in NL but is not known to be NL-complete or contained in L. Allender et al. showed that reachability for graphs embedded on the torus is logspace-reducible to the planar case. We generalize this result to graphs embedded on a fixed surface of arbitrary genus.
Thu, 02 Jul 2009 07:01:21 +0300https://eccc.weizmann.ac.il/report/2009/050