This work presents a log-space reduction which compresses an $n$-vertex directed a cyclic graph with $m(n)$ sources embedded on a surface of genus $g(n)$, to a graph with $O(m(n)+g(n))$ vertices while preserving reach ability between a given pair of vertices. Applying existing algorithms to this reduced graph yields new deterministic algorithms with improved space bounds as well as improved simultaneous time-space bounds for the reach ability problem over a large class of directed a cyclic graphs. Specifically, it significantly extends the class of surface-embedded graphs with log-space reach ability algorithms: from planar graphs with $O(log n)$ sources, to graphs with $2^{O(sqrt{log n})}$ sources embedded on a surface of genus $2^{O(sqrt{log n})}$. Additionally, it yields an $O(n^{1-epsilon})$ space algorithm with polynomial running time for reach ability over graphs with $O(n^{1-epsilon})$ sources embedded on surfaces of genus $O(n^{1-epsilon})$.
展开▼
