Независимые множества графа

Как я понимаю, вам нужно сделать что-то хоть и не очень эффективное, но своё , а Брон и Кербош пусть отдохнут..

Перечислите все 2^n-1 непустых подмножеств графа. Это можно сделать в цикле k от 1 до указанного числа, счетчик цикла k определяет подмножество - единичный бит в k означает, что соответствующий бит входит в подмножество (например k=0b101 даёт подмножество из нулевой и второй вершины)

Проверьте, что подмножество независимое - один шаг поиска из каждой вершины (просто проверить, что ни одна другая вершина из подмножества не является смежной с данной). Сравните размер.

Идея алгоритма такова. Алгоритм работает рекурсивно, строя независимые множества для подграфов.

1. Берёте v - произвольную вершину графа G. Стираете из графа её саму и всех её соседей. Получится некоторый подграф граф G'.

2. Для G' находите множество независимых множеств.

3. В каждое из независимых множеств G' добавляете вершину v.

4. Повторояете алгоритм для всех остальных вершин G.

Очевидно, что на каждом шаге 3 получаются независимые множества графа G, так как v не смежна ни одной вершине из G'. Этот алгоритм строит максимальные независимые множества, то есть такие множества, которые не являются собственным подмножеством другого независимого множества.

После того, как получен набор всех максимальных независимых множеств, совсем нетрудно выбрать среди них одно максимального размера.

функция найти_независимые_вершины(граф G) {

    C = Vertices(G) /* множество вершин графа */
    NS = {} /* множество независимых множеств */

    пока C не пусто {
        v = произвольная вершина из C
        C = C\v

        /* Граф, из которого удалена вершина v вместе со смежными вершинами */
        G' = G \ { v и соседи v } 
        NS' = найти_независимые_вершины(G')
        
        Если NS' пусто {
            добавить в NS множество {v}
        } иначе {
            для каждого множеcтва N из NS' {
                добавить в NS множество (N + {v})
            }
        }
    }
    вернуть NS
}

На самом деле приведённый алгоритм не более, чем тривиальный обход в глубину.

Реализация на Python:

import numpy as np
from collections.abc import Sequence

class Graph:
    def __init__(self, n : int):
        self.im = np.zeros((n,n))
        self.nodes = list(range(n))
    def copy(self) -> Graph:
        res = Graph(self.im.shape[0])
        res.im = self.im.copy()
        res.nodes = self.nodes.copy()
        return res
    def add_edge(self, i : int, j : int):
        self.im[i,j] = 1
        self.im[j,i] = 1
    def neighbors(self, i : int) -> Sequence[int]:
        return  np.where(self.im[i,:])[0].tolist()        
    def del_node(self, i : int):
        if i in self.nodes:
            self.nodes.remove(i)
            self.im[i,:] = 0
            self.im[:,i] = 0
    def del_node_and_neighbors(self, i : int):
        ns = self.neighbors(i)
        self.del_node(i)
        for j in ns:
            self.del_node(j)

def maxset(g : Graph) -> set:
    result = set()
    for i in g.nodes:
        gg = g.copy()
        gg.del_node_and_neighbors(i)
        mset = maxset(gg)
        if (len(mset)) == 0:
            result.add((i,))
        else:
            for ms in mset:
                l = list(ms)
                l.append(i)
                result.add(tuple(sorted(l)))
    return result

Для проверки вычисление независимых множеств для случайного графа с десятью вершинами:

# Матрица инцидентности
# g.im == array([[0., 0., 0., 0., 0., 1., 1., 0., 1., 0.],
#        [0., 0., 0., 0., 0., 0., 1., 1., 0., 0.],
#        [0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
#        [0., 0., 0., 1., 1., 0., 0., 1., 1., 0.],
#        [0., 0., 0., 1., 0., 0., 0., 1., 0., 0.],
#        [1., 0., 0., 0., 0., 1., 0., 0., 0., 0.],
#        [1., 1., 0., 0., 0., 0., 0., 0., 0., 0.],
#        [0., 1., 0., 1., 1., 0., 0., 0., 1., 0.],
#        [1., 0., 0., 1., 0., 0., 0., 1., 1., 1.],
#        [0., 0., 0., 0., 0., 0., 0., 0., 1., 1.]])

maxset(g) == {(0, 1, 2, 3, 9),
 (0, 1, 2, 4, 9),
 (0, 2, 7, 9),
 (1, 2, 3, 5, 9),
 (1, 2, 4, 5, 8),
 (1, 2, 4, 5, 9),
 (2, 3, 5, 6, 9),
 (2, 4, 5, 6, 8),
 (2, 4, 5, 6, 9),
 (2, 5, 6, 7, 9)}