This package contains the source and the test data for a solver for
the Balanced Subgraph problem, based on data reduction rules and
iterative compression. It is described in the paper:

  Falk Hüffner, Nadja Betzler, and Rolf Niedermeier:
  Separator-based data reduction for signed graph balancing.
  Journal of Combinatorial Optimization 20(4):335–360, 2010.
  http://dx.doi.org/10.1007/s10878-009-9212-2
  http://falk.hueffner.de/separator-data-reduction-joco10.pdf

A signed graph is a graph whose edges are labelled positive or
negative. A signed graph is said to be balanced if the set of negative
edges form a cut. The Balanced Subgraph problem is to find a minimum
cardinality set of edges whose deletion makes the graph balanced.

Further it contains the source for a solver for the Tanglegram Layout
problem, based on a reduction to Balanced Subgraph. The Tanglegram
Layout problem is, given two binary phylogenetic trees covering the
same species, to arrange them leaves side-by-side such that a minimum
number of crossings is induced by connecting pairs of identical
species. This is described in the paper:

  Sebastian Böcker, Falk Hüffner, Anke Truss, and Magnus Wahlström:
  A faster fixed-parameter approach to drawing binary tanglegrams.
  In Proceedings of the 4th International Workshop on Parameterized
  and Exact Computation (IWPEC ’09), 2009.
  Volume 5917 in Lecture Notes in Computer Science, pages 38–49, Springer.

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.08 or newer), 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 Objective Caml 3.08.3 and gcc 3.3.5
  (Debian 1:3.3.5-13)
* Debian GNU/Linux (alpha) 4.0 with Objective Caml 3.09.2 and gcc 4.2.0
* Sun Solaris 10 (i386) 8/07 with Objective Caml 3.11.1 and gcc 3.4.3


Balanced Subgraph solver
========================

The program is called "bsg". It reads a graph from standard input and
writes it to standard output (note that on Unix systems, you can close
standard input from the keyboard with Control-d). The graph format is
a simple text format, where each line describes one edge, given by its
two endpoints separated by whitespace, plus an optional edge label (0
or 1). Comment text starting with '#' will be ignored up to the next
newline. Example:

# graph
v0 v1 1
v1 v2
v2 v0 0

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 the Balanced Subgraph poblem anyway. Label "0"
indicates an edge that demands that the coloring of its endpoints are
equal, and "1" demands that the coloring of its endpoints are
unequal. Default is "1". This means that when no edge labels are given
at all, the input instance is treated as an Edge Bipartization
instance.

The output is a minimum set of edges C to delete to make the graph
sign consistent. Example:

$ ./bsg < test/rand02.graph
0 10 1
1 8 0
4 6 0
5 16 1
9 10 0
11 14 0
11 17 0

Option "-c" controls the size of cuts sought for in the data reduction
rules. Default is 4.

Option "-d" starts the iterative compression solver with a heuristic
solution instead of building up the graph inductively. This forfeits
the worst-case bound, and is often slower, but gives good results for
certain types of input (in particular, with many parallel edges).

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

   n      m     k     runtime [s]   n'
  193    493    12       0.26       34


Here, k is size of solution and n' the number of vertices of the
largest remaining component after data reduction.

With "-v" you get some information about the progress of the programm..

ILP based Balanced Subgraph solver
==================================

The Python script "bsg-lp" solves the Balanced Subgraph problem by
calling the ILP solver "glpsol" from the glpk package
(http://www.gnu.org/software/glpk/glpk.html). It has been tested with
glpk 4.8. It is typically much slower than "bsg" and only included for
verification purposes.


Tanglegram Layout solver
========================

The program is called "tanglegram". By default, it reads a pair of
trees from standard input and writes the solution to standard output
(note that on Unix systems, you can close standard input from the
keyboard with Control-d). The input format is a simple text format,
where each of the two trees is on one line, with tree structure
indicated by nesting brackets. Comment text starting with '#' will be
ignored up to the next newline. Example:

# tree
(a, (b, c))
((b, a), c)

Vertex names can be any combination of letters, digits, and _.

The output is a rearrangement of the two trees that minimizes the
number of crossings when connecting identical species. Example:

$ printf "(a, (b, c))\n((b, a), c)\n" | ./tanglegram
((a,b),c)
(a,(b,c))

Options "-c", "-s", and "-v" are as for the Balanced Subgraph solver.
Option "-d" is default, since it often speeds up computation
considerably; the original behavior can be restored with "-u".


Test data
=========

The directory "test" contains some assorted test instances.


Version history
===============

1.0	2007-04-11	initial release
2.0	2009-06-23	tanglegram solver, new reduction rules, "-d" option


-- Falk Hüffner (http://hueffner.de/falk/)