Поиск минимального вершинного покрытия — типичная NP-полная задача, так что можно:
а) смело строчить исчерпывающий поиск и оптимизировать перебор пока не надоест;
б) вдохновиться
вот здесь — это алгоритм эффективного перебора для задачи, которая находит все вершины, кроме тех, которые будут в ответе на вашу задачу. :-)
