×

A general purpose algorithm for counting simple cycles and simple paths of any length. (English) Zbl 1423.05171

Summary: We describe a general purpose algorithm for counting simple cycles and simple paths of any length \(\ell \) on a (weighted di)graph on \(N\) vertices and \(M\) edges, achieving an asymptotic running time of \(O\left( N+M+(\ell ^\omega +\ell \Delta ) |S_\ell |\right) \). In this expression, \(|S_\ell |\) is the number of (weakly) connected induced subgraphs of \(G\) on at most \(\ell \) vertices, \(\Delta \) is the maximum degree of any vertex and \(\omega \) is the exponent of matrix multiplication. We compare the algorithm complexity both theoretically and experimentally with most of the existing algorithms for the same task. These comparisons show that the algorithm described here is the best general purpose algorithm for the class of graphs where \((\ell ^{\omega -1}\Delta ^{-1}+1) |S_\ell |\le |\mathrm{Cycle}_\ell |\), with \(|\mathrm{Cycle}_\ell |\) the total number of simple cycles of length at most \(\ell \), including backtracks and self-loops. On Erdős-Rényi random graphs, we find empirically that this happens when the edge probability is larger than circa \(4 / N\). In addition, we show that some real-world networks also belong to this class. Finally, the algorithm permits the enumeration of simple cycles and simple paths on networks where vertices are labeled from an alphabet on \(n\) letters with an asymptotic running time of \(O\left( N+M+(n^\ell \ell ^\omega +\ell \Delta ) |S_\ell |\right) \). A Matlab implementation of the algorithm proposed here is available for download.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C22 Signed and weighted graphs
05C30 Enumeration in graph theory
05C38 Paths and cycles
05C80 Random graphs (graph-theoretic aspects)
68W40 Analysis of algorithms

Software:

KONECT; Matlab

References:

[1] Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17, 209-223 (1997) · Zbl 0865.68093 · doi:10.1007/BF02523189
[2] Amini, Omid, Fomin, Fedor V., Saurabh, Saket: Counting subgraphs via homomorphisms. SIAM J. Discrete Math. 26(2), 695-717 (2012) · Zbl 1248.05122 · doi:10.1137/100789403
[3] Avis, D., Fukuda, K.: Reverse search for enumeration. Discrete Appl. Math. 65, 21-46 (1996) · Zbl 0854.68070 · doi:10.1016/0166-218X(95)00026-N
[4] Barabási, Albert-László, Albert, Réka: Emergence of scaling in random networks. Science 286(5439), 509-512 (1999) · Zbl 1226.05223 · doi:10.1126/science.286.5439.509
[5] Bax, E., Franklin, J.: A finite-difference sieve to count paths and cycles by length. Inf. Process. Lett. 60(4), 171-176 (1996) · Zbl 0900.68230 · doi:10.1016/S0020-0190(96)00159-7
[6] Bax, Eric T.: Algorithms to count paths and cycles. Inf. Process. Lett. 52(5), 249-252 (1994) · Zbl 0815.68077 · doi:10.1016/0020-0190(94)00151-0
[7] Birmelé, E., Ferreira, R., Grossi, R., Marino, A., Pisanti, N., Rizzi, R., Sacomoto, G.: Optimal listing of cycles and st-paths in undirected paths. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1884-1896 (2013) · Zbl 1423.68329
[8] Bürgisser, P., Clausen, M., Amin Shokrollahi, M.: Algebraic Complexity Theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer, Berlin, New York (1997) · Zbl 1087.68568
[9] Cash, Gordon G.: The number of \[n\] n-cycles in a graph. Appl. Math. Comput. 184(2), 1080-1083 (2007) · Zbl 1115.05043
[10] Chang, Y.C., Fu, H.L.: The number of 6-cycles in a graph. Bull. Inst. Combin. Appl. 39, 27-30 (2003) · Zbl 1050.05065
[11] Demaine, E.D., Reidl, F., Rossmanith, P., Villaamil, Fernando, S., Sikdar, S., Sullivan, B.D.: Structural sparsity of complex networks: random graph models and linear algorithms. CoRR (2014). arXiv:1406.2587 · Zbl 1425.05149
[12] Dorn, F. (2010) Planar subgraph isomorphism revisited. In: Marion, J.-Y., Schwentick, T. (eds.) 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), volume 5 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 263-274. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany · Zbl 1230.68230
[13] Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)
[14] Elbassioni, K.: A polynomial delay algorithm for generating connected induced subgraphs of a given cardinality. J. Graph Algorithms Appl. 19, 273-280 (2015) · Zbl 1312.05132 · doi:10.7155/jgaa.00357
[15] Eppstein, David: Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl. 3(3), 1-27 (1999) · Zbl 0949.05055 · doi:10.7155/jgaa.00014
[16] Flum, Jörg, Grohe, Martin: The parameterized complexity of counting problems. SIAM J. Comput. 33, 892-922 (2004) · Zbl 1105.68042 · doi:10.1137/S0097539703427203
[17] Giscard, P.-L., Rochet, P.: Enumerating simple paths from connected induced subgraphs (2016). arXiv:1606.00289 · Zbl 1402.05104
[18] Giscard, P.-L., Rochet, P., Wilson, R.C.: An Hopf algebra for counting simple cycles (2016). arXiv:1607.00902
[19] Giscard, P.-L., Rochet, P., Wilson, R.C.: Evaluating balance on social networks from their simple cycles (2016). arXiv:1606.03347
[20] Grohe, M.: Descriptive and parameterized complexity. In: Flum, J., Rodriguez-Artalejo, M. (eds) Computer Science Logic, volume 1683 of Lecture Notes in Computer Science chapter 3, pp. 14-31. Springer-Verlag, Berlin, Heidelberg (1999) · Zbl 0943.03029
[21] Harary, F., Manvel, B.: On the number of cycles in a graph. Matematický časopis 21, 55-63 (1971) · Zbl 0209.55404
[22] Howbert, J.: Count all cycles in simple undirected graph. File Exchange—MATLAB Central—MathWorks (2011). https://uk.mathworks.com/matlabcentral/fileexchange/29438-count-all-cycles-in-simple-undirected-graph
[23] Impagliazzo, R., Paturi, R.: On the complexity of \[k\] k-SAT. J. Comput. Syst. Sci. 62, 367-375 (2001) · Zbl 0990.68079 · doi:10.1006/jcss.2000.1727
[24] Isella, Lorenzo, Stehlé, Juliette, Barrat, Alain, Cattuto, Ciro, Pinton, Jean-François, Van den Broeck, Wouter: What’s in a crowd? Analysis of face-to-face behavioral networks. J. Theor. Biol. 271(1), 166-180 (2011) · Zbl 1405.92255 · doi:10.1016/j.jtbi.2010.11.033
[25] Johnson, D.B.: Finding all the elementary circuits of a directed graph. SIAM J. Comput. 4, 77-84 (1975) · Zbl 0275.05112 · doi:10.1137/0204007
[26] Karakashian, S., Choueiry, B.Y., Hartke, S.G.: An Algorithm for Generating All Connected Subgraphs with \[k\] k Vertices of a Graph. University of Nebraska, student report, UNL-CSE-2013-0005, pp. 1-38 (2013)
[27] Karp, Richard M.: Dynamic programming meets the principle of inclusion and exclusion. Oper. Res. Lett. 1(2), 49-51 (1982) · Zbl 0486.90083 · doi:10.1016/0167-6377(82)90044-X
[28] Khomenko, N.P., Golovko, L.D.: Identifying certain types of parts of a graph and computing their number. Ukrainskii Matematicheskii Zhurnal 24, 385-396 (1972) · Zbl 0238.05113
[29] Khomenko, N.P., Shevchenko, E.N.: The problem of isolating and counting. Ukr. Math. J. 30(2), 152-160 (1978) · Zbl 0435.05043 · doi:10.1007/BF01085634
[30] Kunegis, Jérôme: KONECT: The Koblenz network collection. In: Proceedings of the 22nd International Conference on World Wide Web, WWW ’13 Companion, pp. 1343-1350. ACM, New York, NY, USA (2013). Available at: http://konect.uni-koblenz.de/
[31] Mateti, P., Deo, N.: On algorithms for enumerating all circuits of a graph. SIAM J. Comput. 5, 90-99 (1976) · Zbl 0331.05115 · doi:10.1137/0205007
[32] Merris, Russell: Single-hook characters and Hamiltonian circuits. Linear Multilinear Algebra 14, 21-35 (1983) · Zbl 0526.20008 · doi:10.1080/03081088308817540
[33] Merris, Russell: Immanantal invariants of graphs. Linear Algebra Appl. 401, 67-75 (2005) · Zbl 1062.05093 · doi:10.1016/j.laa.2003.11.033
[34] Movarraei, N., Boxwala, S.A.: On the number of cycles in a graph. Open J. Discrete Math. 6, 41-69 (2016) · doi:10.4236/ojdm.2016.62005
[35] Nesetril, J., de Mendez, P.O.: Sparsity—Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, Berlin (2012) · Zbl 1268.05002
[36] Perepechko, S.N., Voropaev, A.N.: The number of fixed length cycles in an undirected graph. Explicit formulae in case of small lengths. Mathematical Modeling and Computational Physics (MMCP2009), pp. 148-149 (2009)
[37] Perepechko, S.N., Voropaev, A.N.: Количество простых циклов фиксированноЙ длины в неориентированном графе. Явные формулы в случае малых длин. (The Number of Fixed Length Cycles in Undirected Graph. Explicit Formulae in Case of Small Lengths). Вестник РУДН. Серија Математика. Информатика. Физика 2 5-11 (2012)
[38] Schott, R., Staples, G.S.: Complexity of counting cycles using Zeons. Comput. Math. Appl. 62(4), 1828-1837 (2011) · Zbl 1231.05250 · doi:10.1016/j.camwa.2011.06.026
[39] Uehara, R.: The number of connected components in graphs and its applications. IEICE Technical Report, COMP99-10 (1999)
[40] Valiant, Leslie G.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189-201 (1979) · Zbl 0415.68008 · doi:10.1016/0304-3975(79)90044-6
[41] Valiant, Leslie G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8, 410-421 (1979) · Zbl 0419.68082 · doi:10.1137/0208032
[42] Wikipedia Adminship Election Data (2016). http://snap.stanford.edu/data/wiki-Elec.html
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.