2026-07-21T19:38:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1758 2024-03-06T10:33:07Z ddc:004 open_access

STCON in Directed Unique-Path Graphs Kannan, Sampath Khanna, Sanjeev Roy, Sudeepa Algorithm complexity st-connectivity We study the problem of space-efficient polynomial-time algorithms for {\em directed st-connectivity} (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 polynomial-time algorithm for STCON uses space that is only slightly sublinear. However, for special classes of directed graphs, polynomial-time poly-logarithmic-space algorithms are known for STCON. In this paper, we continue this thread of research and study a class of graphs called \emph{unique-path 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 polynomial-time algorithm that uses $\tilde O(n^{\varepsilon})$ space for any constant $\varepsilon \in (0,1]$. We also give a polynomial-time, $\tilde O(n^\varepsilon)$-space algorithm to \emph{recognize} unique-path graphs. Unique-path graphs are related to configuration graphs of unambiguous log-space computations, but they can have some directed cycles. Our results may be viewed along the continuum of sublinear-space polynomial-time algorithms for STCON in different classes of directed graphs - from slightly sublinear-space algorithms for general graphs to $O(\log n)$ space algorithms for trees. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sampath Kannan and Sanjeev Khanna and Sudeepa Roy 2008 Is Part Of LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2008.1758 urn:nbn:de:0030-drops-17589 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1758 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode