Во-первых, это касается версии оптимизации доминирующего множества, а также график не обязательно должен быть ненаправленным. Версия оптимизации доминирующего набора предназначена для выбора k узлов во входном графе G таким образом, чтобы число выбранных узлов и их соответствующих смежных узлов, обозначенное m, было максимальным. Таким образом, мы просто ищем максимально возможный «субдоминирующий набор», если хотите, для G с целью k. Если G является ориентированным графом, то узел A смежен с B, только если существует ребро от A до B (но в этом случае B не будет смежным с A ).
Теперь мы знаем, что задача Доминирующего множества является NP-полной, и я хочу, чтобы алгоритм приближения нашел решение, т. Е. m, близкое к оптимальному. Так что в моем случае я попытался сделать это жадным подходом и начать с выбора узла в G, который имеет большинство смежных узлов. Например, допустим, что узел A имеет четыре смежных узла, а затем, если я выберу A или пометить его (каким-нибудь цветом, например красным), то текущий m будет равен 5, который является суммой соседние узлы к A включаются сами. Затем я удалил бы этот узел и все ребра, связанные с ним, и получил бы подграф G, названный G'. Я бы повторил процесс для G', выбрав узел с большинством смежных узлов и удалив его, и проделал бы это k раз, получив таким образом приблизительное решение для оптимального решения.
Теперь у меня есть два вопросы об этом подходе. Во-первых, почему это не приводит к оптимальному решению? Похоже, действительно хороший алгоритм-кандидат для решения проблемы! Но это NP-жесткий, поэтому это не должно быть возможно. Второй вопрос, и это то, что я действительно застрял, как я могу получить коэффициент аппроксимации для этого алгоритма аппроксимации? Я знаю, что должен найти некоторые умные верхние границы, включая оптимальное решение, но я не могу ничего сказать об оптимальном решении, на которое это похоже. Какие умные предположения я могу сделать, чтобы получить где-нибудь? С чего начать?
Редактировать: я нашел ответ на первый вопрос в этом посте .