We generalize Biggs Theorem to the case of directed cycles of multi-digraphs allowing to compute the dimension of the directed cycle space independently of the graph representation with linear runtime complexity. By considering two-dimensional CW complex of elementary cycles and deriving formulas for the Betti numbers of the associated cellular homology groups, we extend the list of representation independent topological inavariants measuring the graph structure. We prove the computation of the 2nd Betti number to be sharp # P hard in general and present specific representation invariant sub-fillings yielding efficiently computable homology groups. Finally, we suggest how to use the provided structural measures to shed new light on graph theoretical problems as graph embeddings , discrete Morse theory and graph clustering .
KeywordsBiggs TheoremElementary and Simple CyclesCW Complexes of GraphsCellular and Singular HomologyBetti Numbers
Mcnaught, A.D. and Wilkinson, A. (1997) IUPAC. Compendium of Chemical Terminology. 2nd Edition (the “Gold Book”), Wiley Blackwell, Hoboken.
Dokholyan, N.V., Li, L., Ding, F. and Shakhnovich, E.I. (2002) Topological Determinants of Protein Folding. Proceedings of the National Academy of Sciences, 99, 8637-8641. https://doi.org/10.1073/pnas.122076099
Albert, R. (2005) Scale-Free Networks in Cell Biology. Journal of Cell Science, 118, 4947-4957. https://doi.org/10.1242/jcs.02714
Barkai, N. and Leibler, S. (1997) Robustness in Simple Biochemical Networks. Nature, 387, 913-917. https://doi.org/10.1038/43199
Anderson, J.A. (1995) An Introduction to Neural Networks. MIT Press, Cambridge. https://doi.org/10.7551/mitpress/3905.001.0001
Otte, E. and Rousseau, R. (2002) Social Network Analysis: A Powerful Strategy, Also for the Information Sciences. Journal of Information Science, 28, 441-453. https://doi.org/10.1177/016555150202800601
Hopcroft, J.E. and Wong, J.K. (1974) Linear Time Algorithm for Isomorphism of Planar Graphs (Preliminary Report). In: Proceedings of the 6th Annual ACM Symposium on Theory of Computing, STOC ‘74, ACM, New York, 172-184. https://doi.org/10.1145/800119.803896
Berge, C. (2001) The Theory of Graphs. Dover Books on Mathematics. Dover, New York.
Deı, V.G., Klinz, B., Woeginger, G.J., et al. (2006) Exact Algorithms for the Hamiltonian Cycle Problem in Planar Graphs. Operations Research Letters, 34, 269-274. https://doi.org/10.1016/j.orl.2005.04.013
Berge, C. and Ghouila-Houri, A. (1965) Programming, Games and Transportation Networks. Methuen, London.
Whitney, H. (1992) Congruent Graphs and the Connectivity of Graphs. In: Hassler Whitney Collected Papers, Springer, Berlin, 61-79. https://doi.org/10.1007/978-1-4612-2972-8_4
Arora, S. and Barak, B. (2009) Computational Complexity: A Modern Approach. Cambridge University Press, New York.
Gross, J.L. and Tucker, T.W. (1987) Topological Graph Theory. Wiley-Interscience, New York.
Biggs, N. (1993) Algebraic Graph Theory. 2nd Edition, Cambridge University Press, Cambridge.
Hatcher, A. (2002) Algebraic Topology. Cambridge University Press, Cambridge.
Tarjan, R. (1972) Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, 1, 146-160. https://doi.org/10.1137/0201010
Bang-Jensen, J. and Gutin, G.Z. (2008) Digraphs: Theory, Algorithms and Applications. 2nd Edition, Springer Publishing Company, Incorporated, Berlin.
Hopcroft, J. and Tarjan, R. (1973) Algorithm 447: Efficient Algorithms for Graph Manipulation. Communications of the ACM, 16, 372-378. https://doi.org/10.1145/362248.362272
Roberts, B. and Kroese, D. (2007) Estimating the Number of ST Paths in a Graph. Journal of Graph Algorithms and Applications, 11, 195-214. https://doi.org/10.7155/jgaa.00142
Johnson, D.B. (1977) Efficient Algorithms for Shortest Paths in Sparse Networks. Journal of the ACM (JACM), 24, 1-13. https://doi.org/10.1145/321992.321993
Hagerup, T. (2000) Improved Shortest Paths on the Word Ram. In: International Colloquium on Automata, Languages, and Programming, Springer, Berlin, 61-72. https://doi.org/10.1007/3-540-45022-X_7
Dijkstra, E.W. (1959) A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1, 269-271. https://doi.org/10.1007/BF01386390
Cheung, H.Y., Kwok, T.C. and Lau, L.C. (2013) Fast Matrix Rank Algorithms and Applications. Journal of the ACM (JACM), 60, 31. https://doi.org/10.1145/2528404
Preiss, B.R. (1999) Data Structures and Algorithms with Object-Oriented Design Patterns in C++. John Wiley & Sons Inc., New York.
Karp, R.M. (1972) Reducibility among Combinatorial Problems. In: Miller, R.E. and Thatcher, J.W., Eds., Complexity of Computer Computations, Plenum Press, New York, 85-103. https://doi.org/10.1007/978-1-4684-2001-2_9
Bron, C. and Kerbosch, J. (1973) Algorithm 457: Finding All Cliques of an Undirected Graph. Communications of the ACM, 16, 575-577. https://doi.org/10.1145/362342.362367
Gagarin, A. (2003) Graph Embedding Algorithms.
Hopcroft, J. and Tarjan, R. (1974) Efficient Planarity Testing. Journal of the ACM (JACM), 21, 549-568. https://doi.org/10.1145/321850.321852
Thomassen, C. (1989) The Graph Genus Problem Is NP-Complete. Journal of Algorithms, 10, 568-576. https://doi.org/10.1016/0196-6774(89)90006-0
Furst, M.L., Gross, J.L. and McGeoch, L.A. (1988) Finding a Maximum-Genus Graph Imbedding. Journal of the ACM, 35, 523-534. https://doi.org/10.1145/44483.44485
Hecht, M. (2017) A Generalization of the Most Common Subgraph Distance and Its Application to Graph Editing. Pattern Recognition Letters, 87, 71-78. https://doi.org/10.1016/j.patrec.2016.09.008
Forman, R. (1998) Morse Theory for Cell Complexes. Advances in Mathematics, 134, 90-145. https://doi.org/10.1006/aima.1997.1650
Hecht, M. (2018) Exact Localisations of Feedback Sets. Theory of Computing Systems, 62, 1048-1084. https://doi.org/10.1007/s00224-017-9777-6
Hecht, M., Gonciarz, K. and Horvát, S. (2021) Tight Localizations of Feedback Sets. ACM Journal of Experimental Algorithmics, 26, 1-19. https://doi.org/10.1145/3447652
Johnson, D.S. and Trick, M.A. (1996) Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11-13, 1993. Volume 26, American Mathematical Society, Boston.
Babai, L. (2016) Graph Isomorphism in Quasi-Polynomial Time. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, ACM, New York, 684-697. https://doi.org/10.1145/2897518.2897542
Grigor’yan, A., Lin, Y., Muranov, Y. and Yau, S.-T. (2012) Homologies of Path Complexes and Digraphs.
Grigor’yan, A., Lin, Y., Muranov, Y. and Yau, S.-T. (2014) Cohomology of Digraphs and (Undirected) Graphs. Asian Journal of Mathematics, 19, 887-932.
Jonsson, J. (2008) Simplicial Complexes of Graphs. Springer-Verlag, Berlin. https://doi.org/10.1007/978-3-540-75859-4