kernel-mis: Computing exact maximum independent sets through kernelization

The intent of this software is to provide all necessary code and scripts to reproduce the results from the following publication:

On the Power of Simple Reductions for the Maximum Independent Set Problem,
Darren Strash,
Proceedings of COCOON 2016. LNCS 9797, pp. 345-356, 2016.
doi:10.1007/978-3-319-42634-1_28
arxiv:1608.00724

##This package includes:

• C++ code for implementations of maximum independent set reduction algorithms, including:

• The critical independent set reduction by Butenko and Trukhanov
• The maximum critical independent set reduction by Larson
• "Simple" reductions: isolated clique removal by Butenko et al. and vertex folding by Chen et al.

• A small collection of test instances (sample.data.tar.gz)
• A test script to build and run algorithms on sample data sets, and generate LaTeX tables as output (./test.sh)

Please feel free to contact me with any questions!

Version

1.0

Building

$ git clone https://github.com/darrenstrash/kernel-mis.git
$ cd kernel-mis
$ make

Running

$ ./bin/kernel-mis --input-file=<input graph> --experiment=<kernel-size-simple|kernel-size-critical-set|kernel-size-maximum-critical-set|simple-mcs>

or

$ ./test.sh

to run all algorithms on all included data sets. The test script will take anywhere from 10 to 30 minutes, depending on your system. Note: this bash script calls both python and pdflatex from the command line. Please make sure you have them installed and configured.

Graph Format

Currently, the unweighted METIS format is expected:

<# vertices> <# edges> 1

followed by <#vertices> lines, where the i-th line contains a list of space-separated neighbors of i. All vertices range from 1 to <# vertices>

Data

sample.data.tar.gz contains a sampling of data sets used in experiments in the paper.

More data is available on request; however, be warned that the full data set is more than 30GB. If there's enough demand, I'll consider making scripts to automatically download/generate all data sets in the expected format.

What's missing from this package?

Right now, I only include the code that I wrote, and a few data sets. Here's what is missing, and may be added in the future:

• Advanced reductions: these were generated by the implementation by Akiba and Iwata (2016). Their code is available here, and must be modified to output the kernel size.
• Full data sets: They're just too big. Contact me if you need them.

Copyright

Copyright (c) 2016 Darren Strash.

License

This code is released under the GNU Public License (GPL) 3.0.

To read the GPL 3.0, read the file COPYING in this directory.

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/

Contact

Darren Strash (first name DOT last name AT gmail DOT com)