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/
Go to the corresponding LIPIcs Volume Portal


Dhayal, Anant ; Sarma, Jayalal ; Sawlani, Saurabh

Polynomial Min/Max-weighted Reachability is in Unambiguous Log-space

pdf-format:
50.pdf (0.5 MB)


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


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