A Heuristic for Direct Product Graph Decomposition
Vol. 27, no. 7, pp. 581-601, 2023. Regular paper.
Abstract In this paper we describe a heuristic for decomposing a directed graph into factors according to the direct product (also known as Kronecker, cardinal or tensor product). Given a directed, unweighted graph $G$ with adjacency matrix $\mathbf{Adj}(G)$, our heuristic aims at identifying two graphs $G_1$ and $G_2$ such that $G = G_1 \times G_2$, where $G_1 \times G_2$ is the direct product of $G_1$ and $G_2$. For undirected, connected graphs it has been shown that graph decomposition is "at least as difficult" as graph isomorphism; therefore, polynomial-time algorithms for decomposing a general directed graph into factors are unlikely to exist. Although graph factorization is a problem that has been extensively investigated, the heuristic proposed in this paper represents - to the best of our knowledge - the first computational approach for general directed, unweighted graphs. We have implemented our algorithm using the MATLAB environment; we report on a set of experiments that show that the proposed heuristic solves reasonably-sized instances in a few seconds on general-purpose hardware. Although the proposed heuristic is not guaranteed to find a factorization, even if one exists; however, it always succeeds on all the randomly-generated instances used in the experimental evaluation.

 This work is licensed under the terms of the CC-BY license.
Submitted: December 2022.
Reviewed: June 2023.
Revised: August 2023.
Accepted: August 2023.
Final: August 2023.
Published: August 2023.
Communicated by Giuseppe Liotta
article (PDF)