CluES - heuristic solver for cluster editing problem, written as an entry to the PACE 2021 challenge.

A variety of heuristics are used to find a small cluster editing set of given graph.
The main algorithm works in iterations, in each iteration a new cluster editing set is found (iterations are independent from each other, the longer the solver runs, the more iterations are done and the greater chance of finding a good set).

The main branch contains code of CluES submitted to heuristic track.
The version of CluES submitted to exact track can be found on 'exact_track' branch. Please note: there is no guarantee of finding an optimal solution.
The version of CluES submitted to kernelization track can be found on 'kernelization_track' branch. Please note: there is no guarantee, that the returned kernel meets the optimality requirements.

Requirements:

CMake VERSION 3.10.2 or higher
c++ 17 or higher

Installation:

Use cmake to obtain a binary file, e.g. in linux in the main directory (pace-2021) you can use the following commands:

mkdir build
cd build
cmake ..
make

After this, the executable file named "CluES" should be in the "build" directory

Usage:

Given a graph in a file example_input.gr, you can run CluES in the following way

./CluES < example_input.gr > example_output.out 2>example_logs.err

CluES (version from heuristic track, on main branch) will run until it receives SIGTERM signal (e.g. using "kill -s SIGTERM $pid" command in linux).
The exact and kernelization versions of CluES will terminate for itself and do not need SIGTERM to be sent to the process (but it will terminate earlier if the signal is sent before the compuation is finished).

Information on running CluES on kernelization track:

To run the first phase (create an output of kernelization), please run CluES with the following command:
./CluES --phase=kernelize < example_input.gr > kernel_output.out

In order to lift the solution, please run CluES with command:
./CluES --phase=lift-solution < lift_solution_input.in > final_output.out