Мне нужно найти сокращение для следующих задач:
Покрытие вершин - Дано (G = (V, E), k) -> G - неориентированный граф, и нам нужен S (подгруппа из V) размером k, охватывающим все ребра в E.
Hal Vertex Cover - задано (G = (V ', E'), k ') -> G - неориентированный граф. и нам нужен S '(подгруппа V') размером k ', который покрывает ровно половину ребер в E'.
Я буду рад, если вы подскажете, как это сделать и почему редукция Карпа будет верной (два направления доказательства).
Спасибо.