Доказательство неприближимости покрытия минимального цикла

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

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

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


algorithm approximation graph-theory np
person gcolucci    schedule 16.06.2014    source источник
comment
Этот вопрос кажется не по теме, потому что он касается теории, а не программирования.   -  person chepner    schedule 17.06.2014
comment
ну, это не первый раз, когда я размещаю здесь вопросы по теории, и в связанных вопросах много похожих...   -  person gcolucci    schedule 17.06.2014
comment
@ user137227 Хотя я ответил на вопрос, я разделяю ваше мнение о том, что вопрос может быть не по теме, поскольку он теоретический и не связан с программированием.   -  person Codor    schedule 17.06.2014

Ответы (1)


arrow_upward
2
arrow_downward

Предположим, что существует алгоритм 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. оптимальные решения да-инстансов;
  2. субоптимальные решения да-экземпляров и допустимые решения нет-экземпляров.
person Codor    schedule 17.06.2014