A Heuristic for Direct Product Graph Decomposition

DOI10.7155/JGAA.00635MaRDI QIDQ6075715zbMATH OpenOpenAlexFDO

Authors Luca Calderoni, Luciano Margara, Moreno Marzolla

Publication date 20 September 2023

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2107.03133

zbMATH Keywords

directed, unweighted graphsgraph isomorphismpolynomial-time algorithm

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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 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.

Recommendations

• Finding the prime factors of strong direct product graphs in polynomial time
• A local prime factor decomposition algorithm
• Fast recognition of direct and strong products
• Factoring directed graphs with respect to the cardinal product in polynomial time II
• Factoring directed graphs with respect to the cardinal product in polynomial time

Cites work

• A finite automata approach to modeling the cross product of interconnection networks.
• Direct product primality testing of graphs is GI-hard
• Factoring cardinal product graphs in polynomial time
• Handbook of product graphs
• scientific article; zbMATH DE number 5077154 (Why is no real title available?)
• scientific article; zbMATH DE number 741107 (Why is no real title available?)
• Independent sets in tensor graph powers
• Kronecker graphs: an approach to modeling networks
• Logspace computations in graph products
• The Kronecker Product of Graphs
• The ubiquitous Kronecker product

Cited in

(2)

• Projection heuristics for binary branchings between sum and product
• A unified method for eigendecomposition of graph products

This page was built for publication: A Heuristic for Direct Product Graph Decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075715)