Seeking Efficient Enumeration Strategies for Graph Partitioning

Question

I am currently working on a class project that involves partitioning a non-directed graph, possibly weighted, into p classes. The objective is to minimize the sum of the weights of the edges between vertices not belonging to the same class. Additionally, it's crucial to ensure that the vertices are distributed approximately equally across the pp classes.

For my initial approach, I am focusing on the explicit enumeration ("generate and test") method to find the optimal partitioning. The project's requirements include to find the optimal solution for small graphs (25 vertices)

To approach this, I've developed a function that explicitly enumerates the entire brute search space. However, this method has proven to be less than ideal. For instance, when setting n=16 (vertices) and p=5 (classes), generating all possible partitions already takes more than 10 minutes. Given that I need to find the optimal solution for graphs up to 25 vertices, I cannot begin to imagine the time it would take for even larger instances. This has led me to conclude that before evaluating the current solution from my brute search space, I must first find a way to effectively reduce the possibilities within my search space.

How can I pre-reduce the enumeration process's search space effectively? Are there known strategies or criteria that can help eliminate non-viable partitions early on?

Here is an example of a small instance number vertices | number of edges 5 8 min degree max degree 3 4 source destination weigth 1 2 1 1 5 1 1 3 1 2 3 1 2 4 1 2 5 1 3 4 1 4 5 1 degree of each vertices 1 3 2 4 3 3 4 3 5 3

`void generate(int n, int p) { vector vecteur(n, 1);

unsigned long long int total_combinations = pow(p, n);
for (unsigned long long int i = 0; i < total_combinations; i++) {
    //printVector(vecteur);
    for (int j = n - 1; j >= 0; --j) {
        if (vecteur[j] < p) {
            vecteur[j]++;
            break;
        } else {
            vecteur[j] = 1;
        }
    }
}

}`