ECCC-Report TR14-035https://eccc.weizmann.ac.il/report/2014/035Comments and Revisions published for TR14-035en-usThu, 13 Mar 2014 22:03:37 +0200
Paper TR14-035
| New Time-Space Upperbounds for Directed Reachability in High-genus and $H$-minor-free Graphs. |
Diptarka Chakraborty,
A. Pavan,
Raghunath Tewari,
N. V. Vinodchandran,
Lin Yang
https://eccc.weizmann.ac.il/report/2014/035We obtain the following new simultaneous time-space upper bounds for the directed reachability problem.
(1) A polynomial-time,
$\tilde{O}(n^{2/3}g^{1/3})$-space algorithm for directed graphs embedded on orientable surfaces of genus $g$. (2) A polynomial-time, $\tilde{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$.
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. Thu, 13 Mar 2014 22:03:37 +0200https://eccc.weizmann.ac.il/report/2014/035