Efficient Matching for Column Intersection Graphsby B. O. Fagginger Auer, R. H. Bisseling

J. Exp. Algorithmics


Theoretical Computer Science


Matching graphs

Linda Eroh, Michelle Schultz

Matchings in graphs II

P.J. McCarthy

Matchings in infinite graphs

Ron Aharoni


Efficient Matching for Column Intersection Graphs

B. O. FAGGINGER AUER and R. H. BISSELING, Utrecht University

To improve the quality and efficiency of hypergraph-based matrix partitioners, we investigate high-quality matchings in column intersection graphs of large sparse binary matrices. We show that such algorithms have a natural decomposition in an integer-weighted graph-matching function and a neighbor-finding function and study the performance of 16 combinations of these functions. We improve upon the original matching algorithm of theMondriaanmatrix partitioner: by using PGA’, we improve the averagematching quality from 95.3% to 97.4% of the optimum value; by using our new neighbor-finding heuristic, we obtain comparable quality and speedups of up to a factor of 19.6.

Categories and Subject Descriptors: G.2.2 [Discrete Mathematics]: Graph Theory—Hypergraphs; Matchings and factors; Graph algorithms; Approximation algorithms

General Terms: Algorithms, Experimentation, Performance

Additional Key Words and Phrases: Column intersection graphs, heuristic algorithms, weighted graph matching

ACM Reference Format:

B. O. Fagginger Auer and R. H. Bisseling. 2014. Efficient matching for column intersection graphs. ACM J.

Exp. Algor. 19, 1, Article 1.3 (May 2014), 22 pages.

DOI: http://dx.doi.org/10.1145/2616587 1. INTRODUCTION

In this article, we investigate efficient matching algorithms that can be used for highquality coarsening of hypergraphs to improve the performance and quality of matrix partitioners such as Mondriaan [Vastenhouw and Bisseling 2005], PaToH [C¸atalyu¨rek and Aykanat 1999], and Zoltan [Devine et al. 2006]. Internally, these matrix partitioners represent the matrix that is to be partitioned as a hypergraph. To partition this hypergraph, they use a multilevel coarsening strategy based on merging matched vertices, together with refinement during uncoarsening (e.g., [Kernighan and Lin 1970;

Fiduccia and Mattheyses 1982]). Generating a matching within the hypergraph for coarsening is a costly operation1 and the quality of the matching has a direct influence on the quality of the partitioning, which is why we are interested in investigating this problem. 1When partitioning the sparse matrix rhpentium from our test set into two parts with imbalance 0.03 for the row-net hypergraph model, the Mondriaan 3.11 hypergraph bipartitioner can spend as much as 91% of its time on generating matchings for the coarsening; the remaining 9% is then spent on coarsening and refinement.

Authors’ addresses: R. H. Bisseling, Mathematics Institute, Utrecht University, PO Box 80010, 3508 TA

Utrecht, the Netherlands; email: r.h.bisseling@uu.nl. (Current address) B. O. Fagginger Auer, Development and Engineering Department, ASML, PO Box 324, 5500 AH Veldhoven, the Netherlands; email: basfaggingerauer@gmail.com.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on the first page or initial screen of a display alongwith the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted.

To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from

Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, or permissions@acm.org. c© 2014 ACM 1084-6654/2014/05-ART1.3 $15.00

DOI: http://dx.doi.org/10.1145/2616587

ACM Journal of Experimental Algorithmics, Vol. 19, No. 1, Article 1.3, Publication date: May 2014. 1.3:2 B. O. Fagginger Auer and R. H. Bisseling

The presented algorithms can be viewed as methods to efficiently generate heavy graph matchings if the graph’s weighted adjacency matrix can be factorized as AT A for a sparse binary matrix A. Even though maximum-weight graph matching can be solved in polynomial time [Edmonds 1965a, 1965b], the size of the matrices that need to be partitioned in practice precludes the use of exact solution methods.

An (undirected) weighted graph G is a triplet (V, E, ω) with vertices V , edges E (every e ∈ E is of the form e = {u, v} for u, v ∈ V with u = v), and edge weights ω(e) > 0 for all e ∈ E. We consider only integer edge weights, ω : E → Z>0. The symmetric |V | × |V | matrix Bwith entries

Buv = { ω({u, v}) {u, v} ∈ E 0 {u, v} /∈ E is the weighted adjacency matrix of G.

A matching of G is a set M ⊆ E of edges that are mutually disjoint (i.e., for all d, e ∈ M, d ∩ e = ∅ → d = e). The weight of M is defined as the sum of the weights of all edges in the matching: G(M) := ∑ e∈M ω(e).

PROBLEM 1.1 (WGM). Let G = (V, E, ω) be a weighted graph with integer edge weights.

We call finding a matching M of G with maximum weight G(M) the weighted graphmatching problem.

We say that a graph-matching algorithm is an α-approximation algorithm, for α ∈ [0,1], if for every graph G the algorithm generates a matching M such that G(M) ≥ α G(M∗), where M∗ is a matching of G with the largest possible weight. We call an algorithm optimal or exact if it is a 1-approximation algorithm. There is a large number of exact and approximation algorithms available to solve WGM; for an overview, we refer the reader to Duan et al. [2011, Tables I–IV].

We now turn to the primary problem that we want to solve: AT A-matching. Let

A∈ {0,1}m×n be a binary matrix (i.e., with only zeros and ones as entries) with m rows and n columns. We consider only binary matrices because we are interested in partitioning the matrix nonzeros, which is only influenced by the row-column position of the nonzeros and not their numerical values. There is a direct correspondence between binarym×nmatrices Aand hypergraphs with n vertices andmnets (hyperedges), where each column of A corresponds to a vertex in the hypergraph, and each row of A corresponds to a net containing all vertices of which the corresponding column possesses a nonzero in that row. This is the row-net hypergraph model [C¸atalyu¨rek and Aykanat 1999] and we view A both as a matrix and as a hypergraph with respect to this model.