Planar and grid graph reachability problems

Eric Allender, David A.Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy

Research output: Contribution to journalArticlepeer-review

30 Scopus citations

Abstract

We study the complexity of restricted versions of s-t-connectivity, which is the standard complete problem for NL. In particular, we focus on different classes of planar graphs, of which grid graphs are an important special case. Our main results are: • Reachability in graphs of genus one is logspace-equivalent to reachability in grid graphs (and in particular it is logspace-equivalent to both reachability and non-reachability in planar graphs). • Many of the natural restrictions on grid-graph reachability (GGR) are equivalent under AC0reductions (for instance, undirected GGR, outdegree-one GGR, and indegree-one-outdegree-one GGR are all equivalent). These problems are all equivalent to the problem of determining whether a completed game position in HEX is a winning position, as well as to the problem of reachability in mazes studied by Blum and Kozen (IEEE Symposium on Foundations of Computer Science (FOCS), pp. 132-142, 1978). These problems provide natural examples of problems that are hard for NC1 under AC0 reductions but are not known to be hard for L; they thus give insight into the structure of L. • Reachability in layered planar graphs is logspace-equivalent to layered grid graph reachability (LGGR). We show that LGGR lies in UL (a subclass of NL). • Series-Parallel digraphs (on which reachability was shown to be decidable in logspace by Jakoby et al.) are a special case of single-source-single-sink planar directed acyclic graphs (DAGs); reachability for such graphs logspace reduces to single-source-single-sink acyclic grid graphs. We show that reachability on such grid graphs AC0 reduces to undirected GGR. • We build on this to show that reachability for single-source multiple-sink planar DAGs is solvable in L.

Original languageEnglish (US)
Pages (from-to)675-723
Number of pages49
JournalTheory of Computing Systems
Volume45
Issue number4
DOIs
StatePublished - Aug 2009

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Keywords

  • Algorithms
  • Circuit complexity
  • Complexity theory
  • Grid graphs
  • Logspace
  • Planar graphs
  • Reachability

Fingerprint

Dive into the research topics of 'Planar and grid graph reachability problems'. Together they form a unique fingerprint.

Cite this