Вершинное покрытие

Задача состоит в том, что нужно найти в графе размера N(кол-во вершин) вершинное покрытие размера K. Алгоритм работает следующим образом:

1) Запускаем цикл на конечное число итераций(например, 25000)

2) Выбираем случайное покрытие размера > K и < N;

3) Проверяем его на корректность;

3.1) Если некорректно, то 2);

3.2) Если корректно, то 4);

4) Запускаем цикл по всем вершинам в выбранном покрытии;

4.1) Удаляем i вершину;

4.2) Если после удаления размер покрытия равен K и покрытие корректно, то это ответ;

4.3) Если оказалось верным, но размер > K, то продолжаем;

4.4) Иначе(покрытие оказалось некорректным), значит нужно вернуться к предыдущей версии покрытия(до удаления)

Если в кратце, то выбираем случайное покрытие размера больше K и спускаемся от него в соседние решения(т.е. удаляя вершины, при этом следя за корректностью) и смотрим, сойдется ли он за некоторое кол-во итераций.

На вход принимаются N, M, K - количество вершин, ребер и размер покрытия.

Написанный мной код работает на некоторых входах, например: 9 12 4

1 2 2 3 1 4 4 5 1 6 6 7 1 8 8 9 2 5 4 7 6 9 8 3

Но не работает на: 8 17 5

2 1 4 3 3 5 7 8 2 8 1 7 8 1 7 4 6 1 3 6 8 4 8 5 5 2 5 7 6 4 2 6 2 7

Я просто не могу понять, почему алгоритм не останавливается на некоторых входах (например, для 2) даже за 1000000 итераций.

Вот сам код

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
struct Node {
 public:
    int first = -1;
    int second = -1;
    mutable bool used = false;
    Node(size_t _first, size_t _second, bool _used) : first(_first), second(_second), used(_used) {}
    const void visited() const {
        used = true;
    }
    void print() const {
        std::cout << "first = " << first
                  << " | second = " << second << " | used = " << used << "\n";
    }
};
bool operator<(const Node &mine, const Node &other) {
    return (mine.first < other.first)
           || (mine.first == other.first && mine.second < other.second);
}
// генерируем покрытие с sizeOfCover единиц и длины N
std::vector<bool> makeCover(size_t sizeOfCover, size_t N) {
    size_t countOnes = 0;
    std::vector<bool> cover(N);
    while (countOnes != sizeOfCover) {
        size_t bit = rand() % sizeOfCover;
        if (cover[bit] != 1) {
            cover[bit] = 1;
            ++countOnes;
        }
    }
    return cover;
}
// проверяем, корректно ли покрытие
bool isCover(std::set<Node> graph, const std::vector<bool> &vertexCover) {
    size_t count = 0;
    for (size_t i = 0; i != vertexCover.size(); ++i) {
        if (vertexCover[i] == 1) {
            for (auto edge = graph.begin(); edge != graph.end(); ++edge) {
                if (!(*edge).used && ((*edge).first == i || (*edge).second == i)) {
                    (*edge).visited();
                    ++count;
                }
            }
        }
    }
    return count == graph.size();
}
// подсчитываем кол-во вершин в покрытии
size_t count_vertices(const std::vector<bool> &vertex) {
    size_t count = 0;
    for (size_t i = 0; i != vertex.size(); ++i) {
        if (vertex[i] == 1)
            ++count;
    }
    return count;
}
int main() {
    size_t N = 0;
    std::cin >> N;
    size_t M = 0;
    std::cin >> M;
    size_t K = 0;
    std::cin >> K;
    // graph
    std::set<Node> graph;
    for (size_t i = 0; i != M; ++i) {
        size_t first = 0;
        size_t second = 0;
        std::cin >> first >> second;
        --first;
        --second;
        graph.insert(Node(first, second, false));
    }
    size_t maxIterates = 0;
    while (maxIterates != 1000000) {
        // генерируем случайный размер множества от K(включительно)
        // до N(то есть кол-во вершин в покрытии, т.е. единиц в слове)
        size_t sizeOfCover = K + rand() % (N - K);
        // генерируем случайный cover размера от K + 1 до N
        std::vector<bool> cover = makeCover(sizeOfCover, N);
        // и его копию, чтобы возвращаться назад, если покрытие испорчено
        std::vector<bool> oldCover = cover;
        // покрытие некорректно, значит выбираем другое
        if (!isCover(graph, cover)) continue;
        ++maxIterates;
        // пока покрытие корректно, убираем одну из вершин из покрытия
        for (size_t i = 0; i != N; ++i) {
            // удаляем i-ую вершину
            cover[i] = 0;
            // если покрытие корректно и кол-во вершин в покрытии равно K, то это ответ
            if (isCover(graph, cover) && count_vertices(cover) == K) {
                std::cout << "YES\n";
                for (size_t z = 0; z != N; ++z) {
                    if (cover[z] == 1) {
                        std::cout << z + 1 << " ";
                    }
                }
                return 0;
                // покрытие корректно, но его размер больше K
            } else if (isCover(graph, cover) && count_vertices(cover) > K) {
                oldCover = cover;
                // покрытие некорректно, значит возвращаемся назад и пробуем удалить следующую вершину
            } else {
                cover = oldCover;
            }
        }
    }
    std::cout << "NO";
}