Решение независимой установки через крышку вершины

Question

У меня есть независимая задача задачи, в которой я должен проверить, имеет ли данный график A, имеет данный размер $ K $ .Я уже написал алгоритм крышки вершины некоторое время назад, и я надеюсь, что смогу использовать его здесь.Эти алгоритмы тесно связаны, поскольку, если график $ g= (v, e) $ имеет размер $ K $ IFF у него есть VC размера $ v - k $ .Итак, я прав, что я могу просто использовать свой алгоритм VC с $ k '= v - K $ ?

Я прочитал Это и Это Вопрос и после этого я начал сомневаться в том, что это так просто.

Answer 1

Это так просто, эти вопросы говорят о фиксированном параметре, проводят алгоритмы W.r.t.Размер $ k $ от независимого набора / крышки вершины.Ваш алгоритм будет работать просто тонкой настройкой $ k '= | v |- K $ .Очевидно, что новое значение $ K '$ также влияет на время работы вашего алгоритма.