Fast factorization of Cartesian products of (directed) hypergraphs

In this contribution, we focus on the algorithmic aspects for determining the Cartesian prime factors of a finite, connected, directed hypergraph and present a first polynomial time algorithm to compute its PFD. In particular, the algorithm has time complexity O(|E||V|r2) for hypergraphs H=(V,E), where the rank r is the maximum number of vertices contained in a hyperedge of H. If r is bounded, then this algorithm performs even in O(|E|log2⁡(|V|)) time. Thus, our method additionally improves also the time complexity of PFD-algorithms designed for undirected hypergraphs that have time complexity O(|E||V|r6Δ6), where Δ is the maximum number of hyperedges a vertex is contained in.