Как получить минимальное покрытие вершин, когда вы можете решить, содержит ли граф покрытие вершин определенного размера?

Question

У кого-нибудь есть идеи, как решить этот вопрос?

Предположим, что в O (2 ^ k kn) можно решить, содержит ли граф с n узлами покрытие вершин максимального размера k> = 0. Покажите, что вы можете решить вариант оптимизации типа 1 задачи в O (2 ^ k n log (n)). (Вариант оптимизации типа 1 ищет размер минимальных покрытий вершин)

Большое спасибо!

Answer 1

Я дам вам несколько советов в правильном направлении.

Представьте данный алгоритм оракулом, чтобы вы могли спросить: есть ли размер вершинного покрытия k? И он ответит либо да, либо нет. Теперь вы хотите узнать минимальное значение k за что все равно отвечает да.

Подумайте о методе, чтобы найти это k, а затем подумайте о самом быстром способе сделать это (с наименьшим количеством вопросов).