This is the code for Partial Optimality in Cubic Correlation Clustering, accepted at ICML'23.

You need to have the BOOST Graph Library (BGL) installed. See here: https://www.boost.org/doc/libs/1_81_0/libs/graph/doc/index.html

mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=RELEASE ..
make equilateral-triangles-persistency
make predefined-partition-persistency

./equilateral-triangles-persistency
./predefined-partition-persistency

Depending on what problem instances you want to run, execute one of the following commands. Note, that we run the computation 30 times with different random seeds for each experiment.

The default is to apply all our persistency conditions jointly to the instance of equilateral triangles with 45 nodes. For this default, run:

./equilateral-triangles-persistency -a

or

./equilateral-triangles-persistency --all

Alternatively, specify the number of elements of the geometric instance in the following way. Run

./equilateral-triangles-persistency -a <n>

where <n> should be replaced by a natural number greater or equal to 3. Here, <n> is a design parameter and leads to a geometric instance with a total of N= 9n - 9 elements, i.e. by default <n>=6.

The default is to apply all our persistency conditions separately to the instance of equilateral triangles with 45 nodes. Run:

./equilateral-triangles-persistency -i

or

./equilateral-triangles-persistency --individual

Alternatively, specify the number of elements of the geometric instance in the following way. Run

./equilateral-triangles-persistency -i <n>

where <n> should be replaced by a natural number greater or equal to 3. Here, <n> is a design parameter and leads to a geometric instance with a total of N= 9n - 9 elements, i.e. by default <n>=6.

The default is to apply all our persistency conditions jointly to the partition instances with 48 nodes.

./predefined-partition-persistency -a

or

./predefined-partition-persistency --all

To specify the size of the instance run

./predefined-partition-persistency -a <n>

where <n> is a natural number and leads to an instance of the partition dataset with N = 8 <n> elements.

The default is to apply all our persistency conditions separately to the partition instances with 48 nodes.

./predefined-partition-persistency -i

or

./predefined-partition-persistency --individual

To specify the size of the instance run

./predefined-partition-persistency -i <n>

where <n> is a natural number and leads to an instance of the partition dataset with N = 8 <n> elements.

If you want to try different configurations, you can change the parameters in the files in

• ./src/equilateral-triangles/persistency.cxx
• ./src/predefined-partition/persistency.cxx

The output of the joint application of our partial optimality criteria is a directory named

• partition_<numNodes>nodes_30seeds for the partition instances
• equilateral_<numNodes>nodes_30seeds_30distanceOfCostZero_4sigma for the geometric instances

These contain the number of eliminated nodes/variables after each step of the joint application of our criteria.

The output of the separate application of our partial optimality criteria is a directory named

• partition_individual_<numNodes>nodes_30seeds for the partition instances
• equilateral_individual_<numNodes>nodes_30seeds_30distanceOfCostZero_4sigma for the geometric instances

These contain, for each partial optimality criterion, a .csv file containing the number eliminated nodes/variables.