A Heuristic for Direct Product Graph Decomposition

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.