Collapse and Persistence of Directed Filtered Graphs

Pritam et al. initiated a line of work that introduces the concept of dominated edges and vertices to reduce the size of (bi)filtered undirected graphs, without compromising their topological features. In this article, we extend these ideas to the setting of directed filtered graphs. We provide a characterization of vertex and edge domination in terms of the local neighborhood structure of the directed graph. Building on this, we adapt the filtration reduction algorithm of [17] to the directed case, and demonstrate through experiments that this often yields considerable improvements in both runtime and memory consumption in the computational pipeline for homology and persistent homology. As with its undirected counterpart, our algorithm operates directly on the filtered directed graph.