This package contains the source of a solver for the Maximum s-Plex
problem, based on data reduction rules and a search tree
algorithm. The solver is described in the paper:

     Algorithms and Experiments for Clique Relaxations---Finding
     Maximum s-Plexes. In Proceedings of the 8th International
     Symposium on Experimental Algorithms (SEA'09), Dortmund,
     Germany. June 2009. Volume 5526 of Lecture Notes in Computer
     Science, pages 233--244, Springer.

An extended version of this paper titled

     Exact Combinatorial Algorithms and Experiments for Finding
     Maximum k-Plexes

is to appear in the Journal of Combinatorial Optimization in 2011.

An s-plex denotes a vertex subset in a graph inducing a subgraph in
which every vertex is adjacent to all but at most s vertices. The
Maximum s-Plex problem is to find an s-plex of maximum size in a given
graph.

The current version can be obtained at

     http://fpt.akt.tu-berlin.de/splex/ .

It is distributed under the terms of the GNU General Public License
(GPL, see COPYING).

The solver is written in Objective Caml and ISO C99. To build the
program, you need Objective Caml (version 3.09 or newer) and GNU
make. Using other compilers or makes, or building on a non-Unix
system, will probably require changes to the Makefile and the source.

To compile, type "make depend; make".

It has been tested on:

* Debian GNU/Linux (x86_64) 4.0 with Objective Caml 3.09.2
* Debian GNU/Linux (x86_64) 6.0 with Objective Caml 3.11.2

The program is called "splex-solver". By default, it reads a graph
from standard input and writes the maximum s-plex to standard output
(note that on Unix systems, you can close standard input from the
keyboard with Control-d). The standard graph format is a simple text
format, where each line describes either a single vertex or one edge,
given by its two endpoints separated by whitespace:

      v0 v1
      v1 v2
      v3
      v2 v0

Vertex names can be any combination of letters, digits, and _. The
output is a set of vertices that form an s-plex of maximum
cardinality.

For a description of the possible parameters and a (brief)
introduction to the algorithms see PARAMETERS. The organization of the
source code is described in SOURCE.

-- Manuel Sorge
   9 February 2011