Совместная NP-полнота минимального тура TSP?

Эта проблема возникла из моего недавнего поста в блоге. Предположим, у вас есть тур по TSP. Является ли он совместным с NP, чтобы определить, является ли он минимальным?

Точнее следующая задача NP-полная:

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

Вопрос: существует ли простой цикл D, который посещает все узлы группы G, так что общий вес всех ребер D в G строго меньше, чем общий вес всех ребер C в G?

Эскиз возможного сокращения, чтобы доказать, что оно NP-завершено.

Неофициально он начинается с модифицированной формулы 3SAT, используемой для демонстрации того, что 3SAT является ASP-завершенной (еще одна проблема решения), и «следует» стандартной цепочке сокращений 3SAT => DIRECTED HAMCYCLE => UNIRIRED HAMCYCLE => TSP

• Начнем с 3SAT формулы с п переменных х 1 , . , , х п и м caluses C 1 , . , , , С м ;$\varphi$$n$$x_1,...x_n$$m$$C_1,...,C_m$
• Trasform его к новой формуле , добавив новую переменную т ...;$\varphi'$$t$
• ... и расширяя каждый пункт к ( х я 1 ∨ х я 2 ∨ х я 3 ∨ т ) ;$(x_{i_1} \lor x_{i_2} \lor x_{i_3})$$(x_{i_1} \lor x_{i_2} \lor x_{i_3} \lor t)$
• Из строят граф структуры алмазов G = { V , E }, используемый для доказательства того, что НАПРАВЛЕННЫЙ ГАМИЛЬТОНОВЫЙ ЦИКЛ является NP-полным; предположим, что каждое предложение C j соответствует узлу N j в G ;$\varphi'$$G = \{V,E\}$$C_j$$N_j$$G$
• Измените на граф G ′ = { V ′ , E ′ }, заменив каждый узел u тремя связанными узлами u 1 , u 2 , u 3 и измените ребра в соответствии со стандартным сокращением, используемым для доказательства NP-полноты НЕПРАВИЛЬНОГО ГАМИЛЬТОНОВОГО ЦИКЛА из НАПРАВЛЕННОГО ГАМИЛЬТОНОВОГО ЦИКЛА, т.е. u 1 - узел, используемый для входящих ребер, u 3 - узел, используемый для исходящих ребер;$G$$G' = \{V',E'\}$$u$$u_1, u_2, u_3$$u_1$$u_3$
• Преобразуйте экземпляр НЕПРАВИЛЬНОГО ГАМИЛЬТОНОВОГО ЦИКЛА на в экземпляр TSP T, в котором все ребра G ′ имеют вес w = 1 , кроме (уникального) ребра в ромбе, переходящего в «положительное» назначение t, имеющее вес w = 2 (красный край на рисунке ниже); наконец, ребра, добавленные для полноты G , имеют вес w = 3 .$G'$$T$$G'$$w = 1$$t$$w = 2$$G'$$w = 3$

Ясно, что экземпляр TSP имеет простой циклкоторый посещает все узлыкоторые соответствуют заданиюудовлетворяющему ф ' , в которой т = т т у е (и этот тур можно легко построить за полиномиальное время), но он имеет общий вес | V ′ | + 1 (поскольку он использует преимуществочто соответствует присваивания т = т т у д , который имеет вес 2). У T есть еще один простой цикл, который посещает все узлы с меньшим общим весом | V ′ $T$$\varphi'$$t = true$$|V'|+1$$t = true$$T$$|V'|$тогда и только тогда, когда ребро веса , соответствующее назначению t = t r u e , не используется; или эквивалентно тогда и только тогда, когда существует другое удовлетворяющее присвоение φ ′, в котором t = f a l s e ; но это может быть правдой тогда и только тогда, когда исходная формула φ выполнима.$2$$t = true$$\varphi'$$t = false$$\varphi$

Я подумаю об этом больше и напишу формальное доказательство (если оно не окажется неправильным :-). Дайте мне знать, если вам нужна дополнительная информация об одном или нескольких из приведенных выше отрывков.

Как отметил domotorp, интересным следствием является то, что следующая задача является NP-полной: если дан граф и гамильтонов путь в нем, имеет ли G гамильтонов цикл?$G$$G$

Papadimitriou & Steiglitz (1977) показали NP-полноту этой проблемы.