Нахождение минимального независимого доминирующего множества с использованием жадного алгоритма

Question

Я разработал алгоритм, который находит минимальный независимый доминирующий набор графа на основе ограничения расстояния. (Я использовал Python и NetworkX для генерации графиков и получения пар)

Алгоритм использует метод грубой силы:

• Найти все возможные пары ребер
• Проверьте, какие узлы удовлетворяют ограничению расстояния
• Найти все возможные независимые доминирующие множества
• Сравните найденные независимые доминирующие множества и найдите минимальный доминирующий набор

Для небольшого количества узлов это не будет иметь значения, но для больших чисел программа действительно медленная.

Есть ли способ, чтобы я мог работать быстрее, используя другой подход?

Спасибо

Answer 1

К сожалению, проблема нахождения минимального независимого доминирующего множества является NP-полной. Следовательно, любой известный алгоритм, который является надежным и полным, будет неэффективным.

Возможный подход заключается в использовании неполного алгоритма (он же локальный поиск). Например, известно, что следующий алгоритм имеет приближение фактора (1 + log|V|):

1. Выберите узел с максимальным количеством соседей и добавьте его в доминирующий набор.
2. Удалите узел и все его соседи из графа.
3. Повторяйте до тех пор, пока в графе не останется больше узлов.