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.597
URN: urn:nbn:de:0030-drops-48744
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4874/
Dhayal, Anant ;
Sarma, Jayalal ;
Sawlani, Saurabh
Polynomial Min/Max-weighted Reachability is in Unambiguous Log-space
Abstract
For a graph G(V,E) and a vertex s in V, a weighting scheme (w : E -> N) is called a min-unique (resp. max-unique) weighting scheme, if for any vertex v of the graph G, there is a unique path of minimum (resp. maximum) weight from s to v. Instead, if the number of paths of minimum (resp. maximum) weight is bounded by n^c for some constant c, then the weighting scheme is called a min-poly (resp. max-poly) weighting scheme.
In this paper, we propose an unambiguous non-deterministic log-space (UL) algorithm for the problem of testing reachability in layered directed acyclic graphs (DAGs) augmented with a min-poly weighting scheme. This improves the result due to Reinhardt and Allender [Reinhardt/Allender, SIAM J. Comp., 2000] where a UL algorithm was given for the case when the weighting scheme is min-unique.
Our main technique is a triple inductive counting, which generalizes the techniques of [Immermann, Siam J. Comp.,1988; Szelepcsényi, Acta Inf.,1988] and [Reinhardt/Allender, SIAM J. Comp., 2000], combined with a hashing technique due to [Fredman et al.,J. ACM, 1984] (also used in [Garvin et al., Comp. Compl.,2014]). We combine this with a complementary unambiguous verification method, to give the desired UL algorithm.
At the other end of the spectrum, we propose a UL algorithm for testing reachability in layered DAGs augmented with max-poly weighting schemes. To achieve this, we first reduce reachability in DAGs to the longest path problem for DAGs with a unique source, such that the reduction also preserves the max-poly property of the graph. Using our techniques, we generalize the double inductive counting method in [Limaye et al., CATS, 2009] where UL algorithms were given for the longest path problem on DAGs with a unique sink and augmented with a max-unique weighting scheme.
An important consequence of our results is that, to show NL = UL, it suffices to design log-space computable min-poly (or max-poly) weighting schemes for DAGs.
BibTeX - Entry
@InProceedings{dhayal_et_al:LIPIcs:2014:4874,
author = {Anant Dhayal and Jayalal Sarma and Saurabh Sawlani},
title = {{Polynomial Min/Max-weighted Reachability is in Unambiguous Log-space}},
booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
pages = {597--609},
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/4874},
URN = {urn:nbn:de:0030-drops-48744},
doi = {10.4230/LIPIcs.FSTTCS.2014.597},
annote = {Keywords: Reachability Problem, Space Complexity, Unambiguous Algorithms}
}
Keywords: |
|
Reachability Problem, Space Complexity, Unambiguous Algorithms |
Collection: |
|
34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) |
Issue Date: |
|
2014 |
Date of publication: |
|
12.12.2014 |