New complexity bounds for reachability in special directed surface graphs

Path Isolation and Reachability in Surface-Embedded Graphs with Restricted Cycle and Cut Structure

Computational Complexity

Summary

Finding if one point can reach another along a path is a common problem in networks. The authors found new ways to decide reachability in certain directed graphs drawn on surfaces with restricted cycle or cut patterns. Their methods use special weighting tricks that make the problem easier to solve using less memory. These results provide better understanding of how hard reachability is in these structured graphs and improve related problems like perfect matching in bipartite graphs.

What this means in practice

  • For graph algorithm engineers: Develop memory-efficient algorithms for reachability queries in networks embedded on surfaces with limited complex cycles.
  • For network protocol designers: Improve methods to verify path existence in structured communication networks modeled by surface-embedded graphs with the given constraints.

A theory result. No direct application yet.

Authors

Neelabjo Shubhashis Choudhury, Chetan Gupta, Raghunath Tewari

Abstract

We study the reachability problem in directed surface-embedded graphs under two structural restrictions, using isolating weight assignments. First, we consider graphs whose underlying undirected embeddings contain at most polynomially many simple surface non-separating cycles. We develop a polynomially bounded, logspace-computable skew-symmetric edge-weight assignment with nonzero circulation around every simple cycle. This yields an unambiguous logspace (UL) upper bound for directed reachability. The construction also gives an SPL upper bound for bipartite perfect matching in the corresponding undirected graph class. Second, for $g$-genus directed graphs admitting a balanced hierarchical genus decomposition with $O(\log n)$ crossing edges at every partition, we obtain an unambiguous $O(\log g \cdot \log n)$-space bound for reachability. Our approach combines path-isolating weights for lower-genus subgraphs using polynomially bounded FKS hashing refinements at successive merging levels.