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.STACS.2019.34
URN: urn:nbn:de:0030-drops-102730
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10273/
Gupta, Chetan ;
Sharma, Vimal Raj ;
Tewari, Raghunath
Reachability in O(log n) Genus Graphs is in Unambiguous Logspace
Abstract
We show that given an embedding of an O(log n) genus graph G and two vertices s and t in G, deciding if there is a path from s to t in G is in unambiguous logarithmic space.
Unambiguous computation is a restriction of nondeterministic computation where the nondeterministic machine has at most one accepting computation path on each input. An important fundamental question in computational complexity theory is whether this is an actual restriction or are unambiguous computations as powerful as general nondeterminism. We investigate this problem in the domain of logarithmic space bounded computations, where the corresponding unambiguous and general nondeterministic classes are UL and NL respectively.
In 1997 Reinhardt and Allender showed that NL and UL are equal in a non-uniform model. More specifically they showed that if one can efficiently construct an O(log n)-bit min-unique weight function for a graph, then these classes are equal unconditionally as well. In other words, they gave a UL algorithm to solve reachability in graphs with a min-unique weight assignment. Using this approach reachability in various classes of graphs such as planar graphs, constant genus graphs, minor free graphs, etc., have been shown to be in UL by devising min-unique weight functions for those classes.
In this paper we improve these results by constructing a min-unique weight function for O(log n) genus graphs. We define signature of a path in a graph as the parity of the number of crossings of that path with respect to each handle of the surface on which the graph is embedded. We construct our weight function in two steps. First we ensure that between any pair of vertices, amongst all paths having the same signature, the minimum weight path is unique. Now since in a genus g graph there are 2^{2g} many possible signatures, we use the hashing scheme of Fredman, Komlós and Szemerédi to isolate a unique minimum weight path among these 2^{2g} many paths isolated in the first step.
BibTeX - Entry
@InProceedings{gupta_et_al:LIPIcs:2019:10273,
author = {Chetan Gupta and Vimal Raj Sharma and Raghunath Tewari},
title = {{Reachability in O(log n) Genus Graphs is in Unambiguous Logspace}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {34:1--34:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-100-9},
ISSN = {1868-8969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10273},
doi = {10.4230/LIPIcs.STACS.2019.34},
annote = {Keywords: logspace unambiguity, high genus, path isolation}
}
|
Keywords: |
|
logspace unambiguity, high genus, path isolation |
|
Collection: |
|
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
12.03.2019 |
