Min/Max-Poly Weighting Schemes and the NL versus UL Problem

For a graph G(V, E) (|V| = n) and a vertex s ∈ V, a weighting scheme (W : E ↔→ Z +) 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, where weight of a path is the sum of the weights assigned to the edges. 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 article, we propose an unambiguous nondeterministic log-space (UL) algorithm for the problem of testing reachability graphs augmented with a min-poly weighting scheme. This improves the result in Reinhardt and Allender [2000], in which a UL algorithm was given for the case when the weighting scheme is min-unique. Our main technique involves triple inductive counting and generalizes the techniques of Immerman [1988], Szelepcśenyi [1988], and Reinhardt and Allender [2000], combined with a hashing technique due to Fredman et al. [1984] (also used in Garvin et al. [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 layered DAGs to the longest path problem for DAGs with a unique source, such that the reduction also preserves the max-unique and max-poly properties of the graph. Using our techniques, we generalize the double inductive counting method in Limaye et al. [2009], in which the UL algorithm was 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 layered DAGs.