Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00635
A Heuristic for Direct Product Graph Decomposition
Vol. 27, no. 7, pp. 581601, 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, polynomialtime 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 reasonablysized instances in a few seconds on generalpurpose hardware. Although the proposed heuristic is not guaranteed to find a factorization, even if one exists; however, it always succeeds on all the randomlygenerated instances used in the experimental evaluation.
This work is licensed under the terms of the CCBY license.

Submitted: December 2022.
Reviewed: June 2023.
Revised: August 2023.
Accepted: August 2023.
Final: August 2023.
Published: August 2023.
Communicated by
Giuseppe Liotta

Journal Supporters
