License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4873/
Go to the corresponding LIPIcs Volume Portal

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:
49.pdf (0.5 MB)

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
Collection: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue Date: 2014
Date of publication: 12.12.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI