Kannan, Sampath ;
Khanna, Sanjeev ;
Roy, Sudeepa
STCON in Directed UniquePath Graphs
Abstract
We study the problem of spaceefficient
polynomialtime algorithms for {\em directed
stconnectivity} (STCON).
Given a directed graph $G$, and a pair of vertices $s, t$, the STCON problem
is to decide if there exists a path from $s$ to $t$ in $G$.
For general graphs, the best polynomialtime algorithm for STCON
uses space that is only slightly sublinear.
However, for special classes of directed graphs, polynomialtime polylogarithmicspace
algorithms are known for STCON. In this paper, we continue this thread of research
and study a class of graphs called
\emph{uniquepath graphs with respect to source $s$},
where there is at most one simple path from $s$ to any vertex in the graph.
For these graphs, we give
a polynomialtime algorithm that uses
$\tilde O(n^{\varepsilon})$ space for any constant $\varepsilon \in (0,1]$.
We also give a polynomialtime, $\tilde O(n^\varepsilon)$space
algorithm to \emph{recognize} uniquepath graphs.
Uniquepath graphs are related to configuration graphs of unambiguous
logspace computations, but they can have some directed cycles. Our results
may be viewed along the continuum of sublinearspace polynomialtime
algorithms for STCON in different classes of directed graphs  from
slightly sublinearspace algorithms for general graphs to $O(\log n)$ space algorithms for trees.
BibTeX  Entry
@InProceedings{kannan_et_al:LIPIcs:2008:1758,
author = {Sampath Kannan and Sanjeev Khanna and Sudeepa Roy},
title = {{STCON in Directed UniquePath Graphs}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {256267},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897088},
ISSN = {18688969},
year = {2008},
volume = {2},
editor = {Ramesh Hariharan and Madhavan Mukund and V Vinay},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1758},
URN = {urn:nbn:de:0030drops17589},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2008.1758},
annote = {Keywords: Algorithm, complexity, stconnectivity}
}
2008
Keywords: 

Algorithm, complexity, stconnectivity 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

Related Scholarly Article: 


Issue date: 

2008 
Date of publication: 

2008 