Существует довольно приятное и хорошо известное сокращение: (Только для связанных графов)
С учетом экземпляра (G, k) Vertex Cover создать экземпляр Доминирующего множества (H, k), где дляH вы берете G и для каждого ребра (u, v) добавляете дополнительную вершину x, связанную с u и v.
Сначала поймите, что покрытие вершин G является доминирующим множеством H (это явно DS изG и новые вершины также доминируют).Поэтому, если G имеет VC меньшего k, то H имеет DS меньшего k.
Для обратного рассмотрим D, доминирующий набор H.
Обратите внимание, что если одна из новых вершиннаходится в D, мы можем заменить его одним из двух его соседей и все же получить Доминирующий набор: это только соседи, это две исходные вершины, и они также связаны - во всем, что может доминировать x, также преобладают u или v.
Таким образом, мы можем предположить, что D содержит только вершины из G. Теперь для каждого ребра (u, v) в G в новой вершине x доминирует D, поэтому либо u, либо v находится в D. Но это означает, что Dявляется покрытием вершин G.
И вот оно: G имеет покрытие вершин меньшего k тогда и только тогда, когда H имеет доминирующий набор меньшего k.