A Heuristic for Direct Product Graph Decomposition

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 aims at identifying two graphs G 1 and G 2 such that G = G 1 × G 2 , where G 1 × 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.