Parallel greedy graph matching using an edge partitioning approach

Abstract

We present a parallel version of the Karp-Sipser graph matching heuristic for the maximum cardinality problem. It is bulksynchronous, separating computation and communication, and uses an edge-based partitioning of the graph, translated from a twodimensional partitioning of the corresponding adjacency matrix. It is shown that the communication volume of Karp–Sipser graph matching is proportional to that of parallel sparse matrix–vector multiplication (SpMV), so that efficient partitioners developed for SpMV can be used. The algorithm is presented using a small basic set of 7 message types, which are discussed in detail. Experimental results show that for most matrices, edge-based partitioning is superior to vertex-based partitioning, in terms of both parallel speedup and matching quality. Good speedups are obtained on up to 64 processors.