Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.585
URN: urn:nbn:de:0030-drops-48730
URL: https://drops.dagstuhl.de/opus/volltexte/2014/4873/
Chakraborty, Diptarka ; Pavan, A. ; Tewari, Raghunath ; Vinodchandran, N. V. ; Yang, Lin Forrest
New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{chakraborty_et_al:LIPIcs:2014:4873,
author = {Diptarka Chakraborty and A. Pavan and Raghunath Tewari and N. V. Vinodchandran and Lin Forrest Yang},
title = {{New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs}},
booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
pages = {585--595},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-77-4},
ISSN = {1868-8969},
year = {2014},
volume = {29},
editor = {Venkatesh Raman and S. P. Suresh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4873},
URN = {urn:nbn:de:0030-drops-48730},
doi = {10.4230/LIPIcs.FSTTCS.2014.585},
annote = {Keywords: Reachability, Space complexity, Time-Space Efficient Algorithms, Graphs on Surfaces, Minor Free Graphs, Savitch's Algorithm, BBRS Bound}
}
| Keywords: | Reachability, Space complexity, Time-Space Efficient Algorithms, Graphs on Surfaces, Minor Free Graphs, Savitch's Algorithm, BBRS Bound | |
| Seminar: | 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) | |
| Issue date: | 2014 | |
| Date of publication: | 12.12.2014 |
