  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
Adj($G$), our heuristic searches for a pair of graphs~$G_1$ and~$G_2$ such that
$G = G_1 \otimes G_2$, where $G_1 \otimes 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.
