Такое решение набирает 30 баллов.

Вариант 3

Заметим, что истинно следующее утверждение:

Пусть \(v\) — вершина графа. Тогда в вершинном покрытии лежит либо вершина \(v\), либо все соседи вершины \(v\).

Будем повторять следующий процесс:

Как только количество добавленных вершин станет равным \(k\), проверим, получили ли мы вершинное покрытие. Если нет, то вернёмся на шаг назад и продолжим перебор.

Мы сделаем не более \(k\) шагов в глубину, а на каждом шаге будем перебирать 2 варианта. Сложность такого алгоритма — \(O(2^k)\).

Это решение набирает 60 баллов.

Различные оптимизации

Заметим, что:

Если провести описанные действия, то в графе останутся вершины со степенью не меньше одного и не больше \(k-1\). Тогда описанный выше перебор будет работать за \(O(1,6^k)\).

В процессе перебора выгодно сначала рассматривать вершины с максимальным количеством соседей. В этом случае, при добавлении всех соседей в покрытие, количество оставшихся вершин, которые нужно добавить в покрытие, резко сокращается. Если же в графе остались только вершины степени 2, то этот граф представляет собой несколько простых циклов, а значит, мы можем не перебирать два варианта, а всегда добавлять в покрытие саму вершину, а не её соседей.

Если воспользоваться описанной эвристикой, то сложность алгоритма будет составлять уже \(O(1,466^k)\).

Это решение получает 100 баллов.