2026-07-22T07:05:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4873 2024-03-06T10:35:29Z ddc:004 open_access

New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs Chakraborty, Diptarka Pavan, A. Tewari, Raghunath Vinodchandran, N. V. Yang, Lin Forrest Reachability Space complexity Time-Space Efficient Algorithms Graphs on Surfaces Minor Free Graphs Savitch's Algorithm BBRS Bound 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. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Diptarka Chakraborty and A. Pavan and Raghunath Tewari and N. V. Vinodchandran and Lin Forrest Yang 2014 Is Part Of LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2014.585 urn:nbn:de:0030-drops-48730 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.585 eng https://creativecommons.org/licenses/by/3.0/legalcode