ðŸ”¥ To appear in Proceedings of the 35th International Symposium on Computational Geometry, 2019.

Abstract:

LetGbe a directed graph with n vertices and m edges, embedded on a surfaceS, possibly with boundary, with first Betti numberÎ². We consider the complexity of finding closed directed walks inGthat are either contractible (trivial in homotopy) or bounding (trivial in integer homology) inS. Specifically, we describe algorithms to determine whetherGcontains 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 inGand in the dual graphG*; 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(

g^{2}L^{2}) non-terminals that generates all contractible closed walks of length at mostL, and only contractible closed walks, in a system of quads of genusgâ‰¥2. Finally, we show that computing shortest simple contractible cycles, shortest simple bounding cycles, and shortest bounding closed walks are all NP-hard.

Publications - Jeff Erickson (jeffe@illinois.edu) 15 Feb 2019