Алгоритм / аппроксимация для комбинированного независимого набора / расстояния Хэмминга

Входные данные: График G Вывод: несколько независимых наборов, так что принадлежность узла ко всем независимым наборам уникальна. Следовательно, узел не имеет соединений с каким-либо узлом в своем собственном наборе. Вот пример пути.

Поскольку здесь потребовалось прояснение еще одной перефразировки:

Разделите данный граф на наборы, чтобы

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

   , если узел j присутствует в наборах A и B, то никакой другой узел не должен присутствовать только в наборе A и B. если принадлежность узлов кодируется битовой комбинацией, то эти битовые комбинации имеют расстояние Хэмминга, по крайней мере, одно

2. , если два графа смежны в графе, они не должны присутствовать в одном и том же наборе, следовательно, быть независимым набором

Пример: B не имеет смежных узлов D => A, A => D

Решение:

1. AB /
2. / BD

A имеет битовую комбинацию 10 и в ее наборе нет смежного узла. B имеет битовую комбинацию 11 и не имеет соседнего узла, D имеет 01 следовательно, все узлы имеют расстояние Хэмминга не менее 1 и нет соседних узлов => правильно

Неверно, поскольку D и A связаны:

1. ADB
2. / DB

A имеет битовую комбинацию 10 и D в своем наборе они смежные. B имеет битовую комбинацию 11 и не имеет смежного узла, D имеет 11, как и B, поэтому в этом решении есть две ошибки, и поэтому оно не принимается.

Конечно, это должно быть расширено на большее количество наборов, так как количество узлов в График увеличивается, так как вам нужно как минимум log (n) наборов .

Я уже написал преобразование в MAX-SAT, чтобы использовать для этого спутниковый решатель. но количество пунктов просто слишком велико. Более прямой подход был бы хорош. Пока у меня есть приближение, но я бы хотел точное решение или хотя бы лучшее приближение.

Я испробовал подход, в котором я использовал рой частиц, чтобы перейти от произвольного решения к лучшему. Однако время работы довольно ужасное, а результаты далеки от хороших. Я ищу динамический алгоритм или что-то, однако я не могу понять, как разделить и победить эту проблему.