×

Topologically trivial closed walks in directed surface graphs. (English) Zbl 1466.05049

Summary: Let \(G\) be a directed graph with \(n\) vertices and \(m\) edges, embedded on a surface \(S\), possibly with boundary, with first Betti number \(\beta\). 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 (\beta (n + m))\) time. Our algorithms rely on subtle relationships between strong connectivity in \(G\) and in the dual graph \(G^\ast\); our contractible-closed-walk algorithm also relies on a seminal topological result of J. Hass and P. Scott [Isr. J. Math. 51, 90–120 (1985; Zbl 0576.57009)]. 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^2L^2)\) 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 \ge 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.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C85 Graph algorithms (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments
57M15 Relations of low-dimensional topology with graph theory
68U03 Computational aspects of digital topology
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Citations:

Zbl 0576.57009
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Alexander, JW, Topological invariants of knots and links, Trans. Am. Math. Soc., 30, 2, 275-306 (1928) · JFM 54.0603.03
[2] Arge, L., Toma, L., Zeh, N.: I/O-efficient topological sorting of planar DAGs. In: 15th Annual ACM Symposium on Parallelism in Algorithms and Architectures (San Diego 2003), pp. 85-93. ACM, New York (2003)
[3] Barrett, Ch; Jacob, R.; Marathe, M., Formal-language-constrained path problems, SIAM J. Comput., 30, 3, 809-837 (2000) · Zbl 0968.68066
[4] Bradford, PG; Thomas, DA, Labeled shortest paths in digraphs with negative and positive edge weights, Theor. Inform. Appl., 43, 3, 567-583 (2009) · Zbl 1175.68196
[5] Brandt, JW, Convergence and continuity criteria for discrete approximations of the continuous planar skeleton, CVGIP: Image Underst., 59, 1, 116-124 (1994)
[6] Cabello, S., Finding shortest contractible and shortest separating cycles in embedded graphs, ACM Trans. Algorithms, 6, 2, # 24 (2010) · Zbl 1300.05296
[7] Cabello, S.; Chambers, EW; Erickson, J., Multiple-source shortest paths in embedded graphs, SIAM J. Comput., 42, 4, 1542-1571 (2013) · Zbl 1276.05031
[8] Cabello, S., Colin de Verdière, É., Lazarus, F.: Finding shortest non-trivial cycles in directed graphs on surfaces. In: 26th Annual Symposium on Computational Geometry (Snowbird 2010), pp. 156-165. ACM, New York (2010) · Zbl 1284.05272
[9] Cabello, S.; Colin de Verdière, ÉC; Lazarus, F., Finding cycles with topological properties in embedded graphs, SIAM J. Discrete Math., 25, 4, 1600-1614 (2011) · Zbl 1237.05112
[10] Cabello, S.; Colin de Verdière, É.; Lazarus, F., Finding shortest non-trivial cycles in directed graphs on surfaces, J. Comput. Geom., 7, 1, 123-148 (2016) · Zbl 1405.05033
[11] Cabello, S.; Devos, M.; Erickson, J.; Mohar, B., Finding one tight cycle, ACM Trans. Algorithms, 6, 4, # 61 (2010) · Zbl 1300.05071
[12] Cabello, S.; Mohar, B., Finding shortest non-separating and non-contractible cycles for topologically embedded graphs, Discrete Comput. Geom., 37, 2, 213-235 (2007) · Zbl 1115.05019
[13] Chambers, EW; Colin de Verdière, É.; Erickson, J.; Lazarus, F.; Whittlesey, K., Splitting (complicated) surfaces is hard, Comput. Geom., 41, 1-2, 94-110 (2008) · Zbl 1152.65026
[14] Chambers, E.W., Erickson, J., Nayyeri, A.: Minimum cuts and shortest homologous cycles. In: 25th Annual Symposium on Computational Geometry (Aarhus 2009), pp. 377-385. ACM, New York (2009) · Zbl 1388.05177
[15] Chambers, EW; Erickson, J.; Nayyeri, A., Homology flows, cohomology cuts, SIAM J. Comput., 41, 6, 1605-1634 (2012) · Zbl 1260.05070
[16] Chang, H.-C., Erickson, J., Letscher, D., de Mesmay, A., Schleimer, S., Sedgwick, E., Thurston, D., Tillmann, S.: Tightening curves on surfaces via local moves. In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2018), pp. 121-135. SIAM, Philadelphia (2018) · Zbl 1408.57021
[17] Chang, H.-C., Erickson, J., Xu, C.: Detecting weakly simple polygons. In: 26th Annual ACM-SIAM Symposium on Discrete Algorithms (San Diego 2015), pp. 1655-1670. SIAM, Philadelphia (2015) · Zbl 1371.68288
[18] Chepoi, V., Dragan, F.F., Estellon, B., Habib, M., Vaxès, Y.: Diameters, centers, and approximating trees of \(\delta \)-hyperbolic geodesic spaces and graphs. In: 24th Annual Symposium on Computational Geometry (College Park 2008), pp. 59-68. ACM, New York (2008) · Zbl 1221.68295
[19] Cohen, E.; Megiddo, N., Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs, J. Assoc. Comput. Mach., 40, 4, 791-830 (1993) · Zbl 0782.68053
[20] Colin de Verdière, É.; Erickson, J., Tightening nonsimple paths and cycles on surfaces, SIAM J. Comput., 39, 8, 3784-3813 (2010) · Zbl 1216.05156
[21] Collatz, L., Spektren periodischer Graphen, Results Math., 1, 1-2, 42-53 (1978) · Zbl 0402.05054
[22] Dehn, M., Über unendliche diskontinuierliche Gruppen, Math. Ann., 71, 1, 116-144 (1911) · JFM 42.0508.03
[23] Dehn, M., Transformation der Kurven auf zweiseitigen Flächen, Math. Ann., 72, 3, 413-421 (1912) · JFM 43.0571.03
[24] Dehn, M., Papers on Group Theory and Topology (1987), New York: Springer, New York · Zbl 1264.01046
[25] Despré, V., Lazarus, F.: Computing the geometric intersection number of curves. In: 33rd International Symposium on Computational Geometry. Leibniz Int. Proc. Inform., vol. 77, # 35. Leibniz-Zent. Inform., Wadern (2017) · Zbl 1436.57019
[26] Dey, TK; Guha, S., Transforming curves on surfaces, J. Comput. Syst. Sci., 58, 2, 297-325 (1999) · Zbl 0922.68069
[27] Edelsbrunner, H.; Harer, JL, Computational Topology. An Introduction (2010), Providence: American Mathematical Society, Providence · Zbl 1193.55001
[28] Edmonds, J.; Karp, RM, Theoretical improvements in algorithmic efficiency for network flow problems, J. Assoc. Comput. Mach., 19, 2, 248-264 (1972) · Zbl 0318.90024
[29] Eppstein, D.: Dynamic generators of topologically embedded graphs. In: 14th Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore 2003), pp. 599-608. ACM, New York (2003) · Zbl 1092.68572
[30] Epstein, DBA, Curves on \(2\)-manifolds and isotopies, Acta Math., 115, 83-107 (1966) · Zbl 0136.44605
[31] Erickson, J.: Shortest non-trivial cycles in directed surface graphs. In: 27th Annual Symposium on Computational Geometry (Paris 2011), pp. 236-243. ACM, New York (2011) · Zbl 1283.68359
[32] Erickson, J., Fox, K., Lkhamsuren, L.: Holiest minimum-cost paths and flows in surface graphs. In: 50th Annual ACM SIGACT Symposium on Theory of Computing (Los Angeles 2018), pp. 1319-1332. ACM, New York (2018) · Zbl 1428.68322
[33] Erickson, J.; Har-Peled, S., Optimally cutting a surface into a disk, Discrete Comput. Geom., 31, 1, 37-59 (2004) · Zbl 1060.68129
[34] Erickson, J., Nayyeri, A.: Minimum cuts and shortest non-separating cycles via homology covers. In: 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco 2011), pp. 1166-1176. SIAM, Philadelphia (2011) · Zbl 1376.05146
[35] Erickson, J., Wang, Y.: Topologically trivial closed walks in directed surface graphs. In: 35th International Symposium on Computational Geometry. Leibniz Int. Proc. Inform., vol. 129, # 34. Leibniz-Zent. Inform., Wadern (2019)
[36] Erickson, J., Whittlesey, K.: Transforming curves on surfaces redux. In: 24th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2013), pp. 1646-1655. SIAM, Philadelphia (2013) · Zbl 1421.68173
[37] Floyd, WJ; Plotnick, SP, Growth functions on Fuchsian groups and the Euler characteristic, Invent. Math., 88, 1, 1-29 (1987) · Zbl 0608.20036
[38] Fox, K.: Shortest non-trivial cycles in directed and undirected surface graphs. In: 24th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2013), pp. 352-364. SIAM, Philadelphia (2013) · Zbl 1421.68174
[39] Gersten, SM; Short, HB, Small cancellation theory and automatic groups, Invent. Math., 102, 2, 305-334 (1990) · Zbl 0714.20016
[40] Giblin, P., Graphs, Surfaces and Homology (2010), Cambridge: Cambridge University Press, Cambridge · Zbl 1201.55001
[41] Goldberg, AV; Tarjan, RE, A new approach to the maximum-flow problem, J. Assoc. Comput. Mach., 35, 4, 921-940 (1988) · Zbl 0661.90031
[42] Grigorchuk, R.; de la Harpe, P., On problems related to growth, entropy, and spectrum in group theory, J. Dynam. Control Syst., 3, 1, 51-89 (1997) · Zbl 0949.20033
[43] Gromov, M.: Hyperbolic groups. In: Essays in Group Theory. Math. Sci. Res. Inst. Publ., vol. 8, pp. 75-263. Springer, New York (1987) · Zbl 0634.20015
[44] Hass, J.; Scott, P., Intersections of curves on surfaces, Isr. J. Math., 51, 1-2, 90-120 (1985) · Zbl 0576.57009
[45] Hatcher, A., Algebraic Topology (2002), Cambridge: Cambridge University Press, Cambridge · Zbl 1044.55001
[46] Iwano, K.: Two-Dimensional Dynamic Graphs and their VLSI Applications. PhD thesis, Princeton University (1987)
[47] Iwano, K., Steiglitz, K.: Testing for cycles in infinite graphs with periodic structure. In: 19th Annual ACM Symposium on Theory of Computing (New York 1987), pp. 46-55. ACM, New York (1987)
[48] Iwano, K.; Steiglitz, K., A semiring on convex polygons and zero-sum cycle problems, SIAM J. Comput., 19, 5, 883-901 (1990) · Zbl 0711.68095
[49] Kao, M-Y, Linear-processor NC algorithms for planar directed graphs I: strongly connected components, SIAM J. Comput., 22, 3, 431-459 (1993) · Zbl 0773.68040
[50] Kao, M-Y; Klein, PN, Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs, J. Comput. Syst. Sci., 47, 3, 459-500 (1993) · Zbl 0795.68086
[51] Kao, M.-Y., Shannon, G.E.: Local reorientation, global order, and planar topology. In: 21st Annual ACM Symposium on Theory of Computing (Seattle 1989), pp. 286-296. ACM, New York (1989)
[52] Kao, M-Y; Shannon, GE, Linear-processor NC algorithms for planar directed graphs II: directed spanning trees, SIAM J. Comput., 22, 3, 460-481 (1993) · Zbl 0773.68041
[53] Karp, RM; Miller, RE; Winograd, S., The organization of computations for uniform recurrence equations, J. Assoc. Comput. Mach., 14, 3, 563-590 (1967) · Zbl 0171.38305
[54] Klein, PN; Mozes, S.; Weimann, O., Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n\log^2 n)\)-time algorithm, ACM Trans. Algorithms, 6, 2, # 30 (2010) · Zbl 1300.05301
[55] Kosaraju, S.R., Sullivan, G.F.: Detecting cycles in dynamic graphs in polynomial time (preliminary version). In: 20th Annual ACM Symposium on Theory of Computing (Chicago 1988), pp. 398-406. ACM, New York (1988)
[56] Kutz, M.: Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time. In: 22nd Annual Symposium on Computational Geometry (Sedona 2006), pp. 430-438. ACM, New York (2006) · Zbl 1153.57304
[57] Lazarus, F., Rivaud, J.: On the homotopy test on surfaces. In: IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 440-449. IEEE Computer Soc., Los Alamitos (2012)
[58] Lyndon, RC; Schupp, PE, Combinatorial Group Theory. Classics in Mathematics (2001), Berlin: Springer, Berlin · Zbl 0997.20037
[59] Möbius, A.F.: Über der Bestimmung des Inhaltes eines Polyeders. Berichte über die Verhandlungen der Königlich Sächsischen Gesellschaft der Wissenschaften zu Leipzig, Math.-Phys. Cl. 17, 31-68 (1865)
[60] Milnor, J., A note on curvature and fundamental group, J. Differ. Geom., 2, 1, 1-7 (1968) · Zbl 0162.25401
[61] Mohar, B.; Thomassen, C., Graphs on Surfaces. Johns Hopkins Studies in the Mathematical Sciences (2001), Baltimore: Johns Hopkins University Press, Baltimore
[62] Moran, JF, The growth rate and balance of homogeneous tilings in the hyperbolic plane, Discrete Math., 173, 1-3, 151-186 (1997) · Zbl 0895.52007
[63] Mozes, S., Nikolaev, K., Nussbaum, Y., Weimann, O.: Minimum cut of directed planar graphs in \(O(n\log \log n)\) time. In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2018), pp. 477-494. SIAM, Philadelphia (2018) · Zbl 1403.68172
[64] Mozes, S., Wulff-Nilsen, Ch.: Shortest paths in planar graphs with real lengths in \(O(n\log^2 n/\log \log n)\) time. In: Algorithms—ESA 2010 (18th Annual European Symposium on Algorithms (Liverpool 2010)). Part II. Lecture Notes in Comput. Sci., vol. 6347, pp. 206-217. Springer, Berlin (2010) · Zbl 1287.05073
[65] Muller, DE; Schupp, PE, Groups, the theory of ends, and context-free languages, J. Comput. Syst. Sci., 26, 3, 295-310 (1983) · Zbl 0537.20011
[66] Neumann-Coto, M., A characterization of shortest geodesics on surfaces, Algebr. Geom. Topol., 1, 349-368 (2001) · Zbl 0991.53024
[67] Orlin, J.B.: Some problems on dynamic/periodic graphs. In: Progress in Combinatorial Optimization (Waterloo 1982), pp. 273-293. Academic Press, Toronto (1984)
[68] Papadimitriou, Ch.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover, Mineola (1998) · Zbl 0944.90066
[69] Plesník, J., The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two, Inf. Process. Lett., 8, 4, 199-201 (1979) · Zbl 0399.68070
[70] Ramachandran, V.; Yang, H., Finding the closed partition of a planar graph, Algorithmica, 11, 5, 443-468 (1994) · Zbl 0804.68108
[71] Rao, SK; Kailath, T., Regular iterative algorithms and their implementation on processor arrays, Proc. IEEE, 76, 3, 259-269 (1988)
[72] Sleator, DD; Tarjan, RE, A data structure for dynamic trees, J. Comput. Syst. Sci., 26, 3, 362-391 (1983) · Zbl 0509.68058
[73] Smikun, LB, Connection between context-free groups and groups with decidable problems of automata equivalence, Cybernetics, 12, 5, 687-691 (1976)
[74] Thomassen, C., Embeddings of graphs with no short noncontractible cycles, J. Comb. Theory Ser. B, 48, 2, 155-177 (1990) · Zbl 0704.05011
[75] Tomizawa, N., On some techniques useful for solution of transportation network problems, Networks, 1, 2, 173-194 (1971) · Zbl 0253.90015
[76] Waite, WM, Path detection in multidimensional iterative arrays, J. Assoc. Comput. Mach., 14, 2, 300-310 (1967) · Zbl 0152.35706
[77] Yannakakis, M.: Graph-theoretic methods in database theory. In: 9th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (Nashville 1990), pp. 230-242. ACM, New York (1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.