Topologically trivial closed walks in directed surface graphs

With Yipu Wang*.

­čöąSubmitted to the 30th ACM-SIAM Symposium on Discrete Algorithms (2019)

Let G be a directed graph with n vertices and m edges, embedded on a surface S, possibly with boundary, with first Betti number ╬▓. We consider the complexity of finding closed directed walks in G that are either contractible (trivial in homotopy) or bounding (trivial in integer homology) in S. Specifically, we describe algorithms to determine whether G contains a simple contractible cycle in O(n + m) time, or a contractible closed walk in O(n + m) time, or a bounding closed walk in O(╬▓ (n + m)) time. Our algorithms rely on subtle relationships between strong connectivity in G and in the dual graph G*; our contractible-closed-walk algorithm also relies on a seminal topological result of Hass and Scott. We also prove that detecting simple bounding cycles is NP-hard.

We also consider the complexity of finding shortest trivial closed walks in G. Specifically, we describe polynomial-time algorithms (independent of ╬▓) to compute shortest contractible closed walks on the torus, and on any surface with boundary; the problem remains open for surfaces without boundary with genus at least 2. Finally, we prove that computing shortest simple contractible cycles, computing shortest simple bounding cycles, and computing shortest bounding closed walks are all NP-hard.

Publications - Jeff Erickson ( 03 Aug 2018