TY - JOUR

T1 - Topologically Trivial Closed Walks in Directed Surface Graphs

AU - Erickson, Jeff

AU - Wang, Yipu

N1 - Funding Information:
Research on this paper was partially supported by NSF grant CCF-1408763. An extended abstract of this paper was presented at the 33rd International Symposium on Computational Geometry [].
Funding Information:
The first author would like to thank Tillmann Miltzow for asking the annoying question that led to this work (“Is that even computable ?”) and to apologize for still being unable to answer it.
Publisher Copyright:
© 2020, Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2020/12

Y1 - 2020/12

N2 - 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 describe three polynomial-time algorithms to compute shortest contractible closed walks, depending on whether the fundamental group of the surface is free, abelian, or hyperbolic. A key step in our algorithm for hyperbolic surfaces is the construction of a context-free grammar with O(g2L2) non-terminals that generates all contractible closed walks of length at most L, and only contractible closed walks, in a system of quads of genus g≥ 2. Finally, we show that computing shortest simple contractible cycles, shortest simple bounding cycles, and shortest bounding closed walks are all NP-hard. Finally, we consider the complexity of detecting negative closed walks with trivial topology, when some edges of the input graph have negative weights. We show that negative bounding walks can be detected in polynomial time, by reduction to maximum flows. We also describe polynomial-time algorithms to find negative contractible walks in graphs on the torus or any surface with boundary; the remaining case of hyperbolic surfaces remains open. The corresponding problems for simple cycles are all NP-hard.

AB - 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 describe three polynomial-time algorithms to compute shortest contractible closed walks, depending on whether the fundamental group of the surface is free, abelian, or hyperbolic. A key step in our algorithm for hyperbolic surfaces is the construction of a context-free grammar with O(g2L2) non-terminals that generates all contractible closed walks of length at most L, and only contractible closed walks, in a system of quads of genus g≥ 2. Finally, we show that computing shortest simple contractible cycles, shortest simple bounding cycles, and shortest bounding closed walks are all NP-hard. Finally, we consider the complexity of detecting negative closed walks with trivial topology, when some edges of the input graph have negative weights. We show that negative bounding walks can be detected in polynomial time, by reduction to maximum flows. We also describe polynomial-time algorithms to find negative contractible walks in graphs on the torus or any surface with boundary; the remaining case of hyperbolic surfaces remains open. The corresponding problems for simple cycles are all NP-hard.

KW - Computational topology

KW - Directed graphs

KW - Graph algorithms

KW - Homology

KW - Homotopy

UR - http://www.scopus.com/inward/record.url?scp=85097080027&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85097080027&partnerID=8YFLogxK

U2 - 10.1007/s00454-020-00255-3

DO - 10.1007/s00454-020-00255-3

M3 - Article

AN - SCOPUS:85097080027

SN - 0179-5376

VL - 64

SP - 1253

EP - 1294

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 4

ER -