Header menu link for other important links
X
Polynomial min/max-weighted reachability is in unambiguous log-space
Published in Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
2014
Volume: 29
   
Pages: 597 - 609
Abstract
For a graph G(V,E) and a vertex s ε 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) weight1 from s to v. Instead, if the number of paths of minimum(resp. maximum) weight is bounded by nc 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 [11] 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 [7, 12] and [11], combined with a hashing technique due to [5] (also used in [6]). 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 [8] 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.
About the journal
JournalLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISSN18688969
Open AccessNo
Concepts (13)
  •  related image
    Algorithms
  •  related image
    Computational complexity
  •  related image
    Directed graphs
  •  related image
    Software engineering
  •  related image
    Directed acyclic graphs
  •  related image
    HASHING TECHNIQUES
  •  related image
    LONGEST PATH PROBLEMS
  •  related image
    Reachability
  •  related image
    Reachability problem
  •  related image
    SPACE COMPLEXITY
  •  related image
    VERIFICATION METHOD
  •  related image
    WEIGHTING SCHEME
  •  related image
    Graph theory