This package contains the source and the test data for a solver for
the Highly Connected Deletion problem. It is described in the paper:

  Falk Hüffner, Christian Komusiewicz, Adrian Liebtrau, and
  Rolf Niedermeier:
  Partitioning Networks into Highly Connected Clusters with Maximum
  Edge Coverage
  Manuscript, 2012.

The Highly Connected Deletion problem is, given a graph, to delete a
minimum number of edges such that each remaining connected component
is highly connected. Here, a graph with n vertices is highly connected
if more than n/2 edges need to be deleted to make it disconnected, or
equivalently each vertex has degree larger than n/2.
  
The current version can be obtained at
http://www.user.tu-berlin.de/hueffner/hcd. It is distributed under the
terms of the GNU General Public License (GPL); either version 2 (see
COPYING), or (at your option) any later version. It uses the min-cut
routines by Chandra Chekuri, Andrew Goldberg, David Karger, Matthew
Levine, and Cliff Stein (see mincut/README).

The solver is written in Objective Caml and C++. To build the
program, you need

* Objective Caml (version 3.10 or newer)
* the GNU gcc compiler (version 3.4 or newer)
* GNU make
* CPLEX 12.3 or newer.

Using other compilers or makes, building on a non-Unix system, or
compiling without CPLEX support will require changes to the Makefile
and the source.

It has been tested on:

* Debian GNU/Linux (amd64) 7 with Objective Caml 3.12.1, gcc 4.7.1
 (Debian 4.7.1-7), and CPLEX 12.4.

To build, type make in the mincut directory and then make in the main
directory.


Highly Connected Deletion solver
================================

The program is called "hcd". 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. Edges are
given by two vertex lables divided by whitespace. Comment text
starting with '#' will be ignored up to the next newline. Example:

# graph
v0 v1
v1 v2
v2 v0

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

The output is a minimum set of edges to delete to make every remaining
connected component highly connected. Example:

$ ./hcd < BB11001.graph
3_33 0_35
0_34 3_32
1_62 2_75
2_90 3_80
0_74 1_69
[...]

A list of options can be obtained with

./hcd --help


Data
====

The directory "data" contains the test instances and clusters found as
described in the paper.


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

1.0	2012-10-16	initial release


-- Falk Hüffner (http://www.user.tu-berlin.de/hueffner/)