Блог

Рассмотрим проблему покрытия цикла: учитывая граф G, мы ищем множество C циклов, таких, что все вершины V (G) находятся по крайней мере в одном цикле C, а количество циклов в C минимально.

Моя задача — показать, что эта задача не допускает абсолютного приближения, т. Е. Не может быть алгоритма H такого, чтобы для всех экземпляров I задачи H (I) <= OPT(I) k, где OPT (I) — оптимальное значение для I, а k -число, большее или равное 1. Обычный метод состоит в том, чтобы показать, что если бы этот алгоритм существовал, мы могли бы решить за полиномиальное время некоторую NP-сложную задачу.

Кто-нибудь знает, какая проблема может быть использована для этого?

Предположим, что существует алгоритм H , такой, что существует положительное целое k число, такое, что для каждого графа G H(G)<=OPT(G) k выполняется, где OPT(G) обозначает минимальное количество циклов, необходимое для покрытия всех узлов G , а время выполнения H полиномиально ограничено в n , где n — количество узлов G .

Учитывая любой граф G , создайте граф G' , состоящий из k 1 изоморфных копий G ; обратите внимание, что число узлов в G' равно (k 1)n , которое полиномиально ограничено n . Могут возникнуть следующие два случая:

1. Если G содержит гамильтонов цикл, то OPT(G')=k 1 и H(G')<=OPT(G') k=k 1 k=2k 1 .

2. Если G не содержит гамильтонова цикла, то OPT(G')>=2k 2>2k 1 , следовательно H(G')>2k 1 .

В целом, H может использоваться для принятия решения в среде выполнения, ограниченной линейно, ограниченной в n том G , содержит ли гамильтонов цикл; однако, поскольку решение о том, имеет ли G гамильтонов цикл, является NP проблемой полного решения, это невозможно, если P=NP не выполняется.

Примечание: Этот подход называется «созданием пробелов», поскольку экземпляры преобразуются таким образом, что в целевом значении

1. оптимальные решения yes-экземпляров;
2. неоптимальные решения экземпляров «да» и допустимые решения экземпляров «нет».