Efficient implementation of Karp--Sipser reduction rules

This repository contains efficient implementations of Karp--Sipser heuristic with two reduction rules for obtaining high cardinality matchings in bipartite graphs and general undirected graphs.

The algorithms are described in:

Kamer Kaya, Johannes Langguth, Ioannis Panagiotas, and Bora Uçar. Karp-Sipser based kernels for bipartite graph matching, to be published in proc. SIAM Symposium on Algorithm Engineering and Experiments (ALENEX20), Jan 2020, Salt Lake City, Utah, US. A copy of the paper is available at HAL.

@inproceedings{kaya:hal-02350734,  
	TITLE = {{Karp--Sipser based kernels for bipartite graph matching}},  
	AUTHOR = {Kaya, Kamer and Langguth, Johannes and Panagiotas, Ioannis and U{\c c}ar, Bora},  
	URL = {https://hal.inria.fr/hal-02350734},  
	BOOKTITLE = {{SIAM Symposium on Algorithm Engineering and Experiments (ALENEX20)}},  
	ADDRESS = {Salt Lake City, Utah, United States},  
	YEAR = {2020},  
	MONTH = Jan  
}

License

See the file LICENSE. The software is under CeCILL-B license, which is a BSD-like license.

Contact

The e-mail addresses of the authors are: kamer.kaya@sabanciuniv.edu, langguth@simula.no, ioannis.panagiotas@ens-lyon.fr, and bora.ucar@ens-lyon.fr.

Build

A C and a C++ (with c++11 support) compiler are needed. There is a Makefile, where these compilers can be defined. Upon which, simply issueing a make command shuld build the executable.

Usage and arguments

• expBasicKS12 -h: for obtaining help.
• -f filename: for specifying the input file.
• -i 0 | 1: input as bipartite graph (0) or general undirected (1), default = 0.
• -o 0 | 1: write matching into the file filename_mtch (0--no, by default).
• Example use (bipartite graph): expBasicKS12 -f example.mtx -i 0 -o 1
• Example use (general undirected): expBasicKS12 -f example.mtx -i 1 -o 0

The main driver expBasicKS12 reads the matrix given in the file "filename", which specifies a matrix in the MatrixMarket format.

Depending on the value of the -i parameter x expBasicKS12 considers the matrix as a bipartite graph (-i 0) or undirected general graph (-i 1). In the latter case, the matrix must be symmetric (the diagonal is zeroed during the preprocessing step). Default setting is -i 0 and this argument does not need to be set at the command prompt.

The program expBasicKS12 outputs the cardinality of the matching found. If the option -o 1 is specified, then the matching is written into the file filename_mtch. In this file, each line contains two vertex ids, say i1,i2. For a bipartite graph, row vertex i1 is matched to column vertex i2. If the input matrix has M rows and N columns, then i1 is in [1,...,M], and i2 is in [1,...,N].

If the input graph has dangling vertices (degree 0 vertices, empty rows/cols), they are removed. In this case, new ids are assigned to the vertices and the output (the matching) refers to the new graph.

Files

• LICENSE: Describes the CeCILL-B license.
• Makefile: A sample makefile with g++-9 and gcc-9.
• README.md: This file.
• basicKS2.cpp: The file containing the implementations.
• example.mtx: A sample matrix in the MatrixMarket format.
• expBasicKS12.cpp: A driver routine for reading a matrix, cleaning it, preparing a graph from it and calling the implementation.
• graph.h: This file contains only the vertex and edge types (a superset of what we use).
• graphio.c: The I/O routines for graphs (a superset of what we use).
• mmio.h and mmio.c: These are from the MatrixMarket.
• utils.h: This file contains some utility functions.

Versions

This is version v1.1 (December 2019), and handles bipartite graphs and general undirected graphs. The version v1.0 (used in the paper above) handles bipartite graphs only.