This package contains the source and the test data for the paper

Falk Hüffner.
Algorithm Engineering for Optimal Graph Nipartization.
Journal of Graph Algorithms and Applications, 13(2):77–98, 2009.
http://dx.doi.org/10.7155/jgaa.00177

A slightly updated description is in the thesis

Falk Hüffner.
Algorithms and Experiments for Parameterized Approaches to Hard Graph Problems.
PhD thesis, Institut für Informatik, Friedrich-Schiller-Universität Jena, 2007.
http://hueffner.de/falk/diss-hueffner07.pdf


Graph Bipartization solver
==========================

The solver is written in ISO C99 plus a few Unix functions. To build
the program, you need the GNU gcc compiler (version 3.2 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.

It has been tested on:

* Debian GNU/Linux (i386) 3.1 with gcc 3.3.5
* Digital Unix 5.1 (Alpha) with 3.3.2
* Solaris 9 (UltraSPARC) with gcc 3.2

To compile, run "make".

The program is called "occ". By default, it reads a graph from
standard input and writes it to standard output. The graph format is a
simple text format, where each line describes one edge, given by its
two endpoints separated by whitespace:

v0 v1
v1 v2
v2 v0

Vertex names can be any combination of letters, digits, and _. Note
that this graph format cannot describe degree-0 vertices; however,
they are irrelevant for Graph Bipartization anyway.

The output is a minimum set of vertices to delete to make the graph
bipartite. Example:

# ./occ < data/afro-americans/10.graph
38
31
28
25
1
0

By default, the program executes the unmodified Reed/Smith/Vetta
algorithm (see Table 1, column "Reed"). Option -g enables the use of
Gray codes (column "OCC-Gray"), and option -b uses the "OCC-Enum2Col"
algorithm.

With -s, one gets only a single line of output containing some
statistics:

   n      m    |C|    run time [s]    augmentations
  102    307    11       0.78           671088



The test data
=============

The directory "data" contains benchmark instances assembled by
Sebastian Wernicke. They are based on data made available by the
Whitehead Institute
(http://www.broad.mit.edu/mpg/hapmap/hapstruc.html).

See

Sebastian Wernicke.
On the algorithmic tractability of single nucleotide polymorphism
(SNP) analysis and related problems.
Diplomarbeit, Universität Tübingen, 2003.

for details on the data and the file format.


-- Falk Hüffner (http://hueffner.de/falk/), March 16 2005