Maximal Full-mesh In A Graph - Python Code Is Very Slow

I have some python code for computing the maximal full-mesh in a graph. Each node of the graph can have a different weight (The weights of each node are given by an array). I want

Solution 1:

Here I tackle the problem in reverse- I generate the sets of nodes to exclude from the original full-mesh to make each resulting full-mesh. From this, I can easily use a few tricks- skipping over edges that aren't contained in the corresponding full mesh using set differences, and pruning sub optimal branches early as they exceed the weight threshold.

class FullMesh:
    def __init__(self, pairs, weights):
        self.pairs = pairs
        self.weights = weights
        self.elements = set(range(len(weights)))

        self.skips = {e:set() for e in self.elements}
        for i, (a, b) in enumerate(pairs):
            self.skips[a].add(i)
            self.skips[b].add(i)

    def find_max(self):
        max_score = sum(self.weights)
        val, nums = self.exclude(0, max_score + 1, set(range(len(self.pairs))))
        return max_score - val, sorted(self.elements - set(nums))

    def exclude(self, curr_score, min_score, search):
        if not search or min_score <= curr_score:
            return curr_score, []

        min_nums = []
        for e in self.pairs[next(iter(search))]:
            score, nums = self.exclude(curr_score + self.weights[e], min_score, search - self.skips[e])
            if score < min_score:
                min_score, min_nums = score, nums + [e]
        return min_score, min_nums