Solver is a java-program
for finding the maximum independent set or the maximum clique
in an undirected graph

Summary

Solver is a java-program for exact finding the maximum independent set or the maximum clique in an arbitrary undirected graph. It uses an polynomial-time algorithm developed by Anatoly Plotnikov. It is designed with the aim of examining the validity of Plotnikov's hypothesis about properties of vertex-saturated digraphs and of algorithm researching.

Solver can be used on any operating systems.

Features

The main features of Solver include:

• support for undirected graphs;
• finding the maximum independent set;
• finding the maximum clique;
• determine the running-time;

User's Guide

The program works in a different way. Just use the jar-file by typing

java -jar mmisfinder.jar <'inputfile'> [-out <'outputfile'>] [-progress] [-time] [-dVS] [-dMIS] [-dCutting] [-dPart] [-dLayer],

where instead <'inputfile'> you have to insert the filename (or path) of the input graph. If the input file has filename extension " .mis", the program finds the maximum independent set. If the input file has filename extension ".clq", the program finds the maximum clique. An input file must use the DIMACS format (see, for example,
ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique
and
http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm).

By appending the option "-out <'outputfile'>" you can specify the name of the solution-file. If you don't give a solution-file, the name of the input-file will be used with extension ".sol".

By appending the option "-progress" you can see short information about what the algorithm is doing presently. This is only interesting for running big instances.

By appending the option "-time" you can see the running time in sol-file.

By appending the option "-dVS" you can see infomation about how the program creates vertex-saturated graphs.

By appending the option "-dMIS" you can see information about the main algorithm.

By appending the option "-dCutting" you can see information about performing the "cutting" operation.

By appending the option "-dPart" you can see information about calculating the chain partitioning.

By appending the option "-dLayer" you can see information about how the layering is created.

See used graph terminology in Anatoly Plotnikov.

Download

The current version of the program is released in 2008.

You can download the program here:

If you have any problems to use this program, feel free to ask its author.

You may refer to this page if you use Solver in your scientific work. If you want a printed copy of it, please contact Thomas Karbe (e-mail address see below in the section "Author").

License

Solver is licensed under the GNU General Public License. Basically, you can use Solver for any purpose, provided that any programs or modifications you make and distribute are also licensed under the GNU GPL.

Absolutely no guarantees or warranties are made concerning the suitability, correctness, or any other aspect of this program.

Copyright © 2008 Thomas Karbe, Anatoly Plotnikov.

Author

Solver was written by Thomas Karbe, Technical University of Berlin, karbePcs.tu-berlin.de (P=@)).

For bug-fixes, feedback for any important information regarding Solver, please contact the author.