Biggs Theorem for Directed Cycles and Topological Invariants of Digraphs

Michael Hecht, Ivo F. SbalzariniAdvances 2021 · DOI

Abstract: 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.

Introduction

In graph theory, comparing complex networks or measuring their inherent structural complexity is a persistent challenge. Traditional metrics often depend heavily on a graph’s specific representation, making it difficult to determine if two differently drawn graphs share the same underlying topology—a problem central to the Graph Isomorphism Problem. While topological invariants like the Euler characteristic are well-established for surfaces, their application to directed graphs (digraphs) has historically been limited.

The original Biggs Theorem provided a method to calculate the dimension of the cycle space for simple digraphs. However, it failed to account for directed cycles or "multi-edges" (multiple connections between identical nodes), which are ubiquitous in real-world systems such as metabolic pathways or social networks. This research bridges that gap by generalizing Biggs Theorem to multi-digraphs and introducing robust, representation-independent topological invariants.

Generalizing Biggs Theorem and CW Complex Construction

The core of this work lies in extending Biggs Theorem to cover directed elementary cycles in multi-digraphs. The authors prove that the dimension of the directed cycle space can be determined solely by examining the union of all strongly connected components (SCCs). This theoretical advancement allows for the transition from a "flat" 1D graph to a 2D topological space.

To achieve this, the graph is treated as a 1-dimensional skeleton. By "filling" selected elementary cycles with 2-dimensional "cells"—analogous to stretching a membrane over a wire loop—the researchers construct a 2D Cellular (CW) Complex. This transformation allows for the application of cellular homology to calculate Betti numbers ($b_0, b_1, b_2$), which serve as pure measures of the underlying structure:

  • $b_0$: The number of connected components.
  • $b_1$: The number of 1D loops not filled by 2D cells.
  • $b_2$: The number of 2D "voids" or enclosed shells.
Figure 5: A multi-digraph G and its decomposition into elementary cycles c1 and c2, which serve as the basis for the 2D CW complex construction.

Computational Complexity and Key Insights

One of the most significant practical outcomes of this research is the SCC Shortcut. The authors demonstrate that the dimension of the directed cycle space can be computed in linear time $O(|E|)$ by identifying strongly connected components. This efficiency makes the theory applicable to massive, real-world datasets.

However, the research also identifies a "#P-Hardness Wall." Calculating the 2nd Betti number ($b_2$) when all elementary cycles are filled is #P-hard, as it requires counting every cycle in the graph—a known computationally intensive problem. To circumvent this, the authors propose using "sub-fillings." By filling only specific sets of cycles, such as shortest cycles or those forming cliques, researchers can maintain representation invariance while achieving polynomial-time computation (e.g., $O(\Delta |E|^2)$ for shortest cycles).

Key Results and Future Directions

The paper successfully generalizes Biggs Theorem (Theorems 1 & 5), establishing that the directed cycle space dimension is $dim_R \langle O_{el}(G) \rangle = |E| - |V| + \#G$ within the union of SCCs. Furthermore, it provides explicit formulas for Betti numbers and introduces a "homological distance" metric. This metric offers a theoretically sound method for clustering graphs based on topological similarity rather than visual representation.

While the current work focuses on 2D complexes, future research may explore higher-dimensional 3-cells. Although defining boundaries for 3D volumes is combinatorially more complex, it represents the next frontier in topological graph analysis. Additionally, determining the optimal "filling" strategy for specific domains, such as neuroscience or social network analysis, remains an open and promising area of study.

Summary updated

Abstract

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.
BibTeX
@inproceedings{hecht2021biggs,
  author = {Michael Hecht and Ivo F. Sbalzarini},
  title = {{Biggs Theorem for Directed Cycles and Topological Invariants of Digraphs}},
  booktitle = {Advances},
  year = {2021},
  doi = {10.4236/apm.2021.116037},
}
Figure