We obtain the following new simultaneous time-space upper bounds for the directed reachability problem. (1) A polynomial-time, O(n^{2/3} * g^{1/3})-space algorithm for directed graphs embedded on orientable surfaces of genus g. (2) A polynomial-time, O(n^{2/3})-space algorithm for all H-minor-free graphs given the tree decomposition, and (3) for K_{3,3}-free and K_5-free graphs, a polynomial-time, O(n^{1/2 + epsilon})-space algorithm, for every epsilon > 0.#R##N##R##N#For the general directed reachability problem, the best known simultaneous time-space upper bound is the BBRS bound, due to  Barnes, Buss, Ruzzo, and Schieber,  which achieves a space bound of O(n/2^{k * sqrt(log(n))}) with polynomial running time, for any constant k. It is a significant open question to improve this bound for reachability over general directed graphs. Our algorithms beat the BBRS bound for graphs embedded on surfaces of genus n/2^{omega(sqrt(log(n))}, and for all H-minor-free graphs. This significantly broadens the class of directed graphs for which the BBRS bound can be improved.
['Diptarka Chakraborty', 'Aduri Pavan', 'Raghunath Tewari', 'N. V. Vinodchandran', 'Lin F. Yang']
New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs.