Gomory-Hu Tree Hypergraph K-cut Solver

This program heuristically solves the k-cut problem in a hypergraph using a Gomory-Hu Tree.

Compilation

makefile

1. Download the source code
2. Unzip it and open the directory
3. Compile using the make command

Usage

The program takes 3 input parameters:

• The name of the file to read (containing the hypergraph)
• k (for the k-cut)
• 0 or 1 (1 if you want to launch local search)

Example of usage:

./ght data/example2.txt 3 1

Input File Format

Number of vertices (indexed from 0)

Number of hyperedges

List of hyperedges (one per line)

Weight of hyperedges (one per line)

Example:

Example of a hypergraph with 5 vertices and 4 hyperedges.

• First hyperedge: 0,1,2 with weight 6;
• Second hyperedge: 0,3 with weight 5;
• Third hyperedge: 4,3,2 with weight 2;
• Fourth hyperedge: 1,3,4 with weight 10;

The data file contains:

5
4
0 1 2
0 3
4 3 2
1 3 4
6
5
2
10