Ce problème est sorti de mon récent article de blog , supposons que l'on vous donne une visite TSP, est-il co-NP-complet pour déterminer s'il est minime?
Plus précisément, le problème suivant est NP-complet:
Instance: étant donné un graphe complet G avec des arêtes pondérées par des entiers positifs et un cycle C simple qui visite tous les nœuds de G.
Question: Existe-t-il un cycle D simple qui visite tous les nœuds de G de telle sorte que le poids total de toutes les arêtes de D dans G soit strictement inférieur au poids total de toutes les arêtes de C dans G?
Un croquis d'une réduction possible pour prouver qu'il est NP-complet.
De manière informelle, il part d'une formule 3SAT modifiée utilisée pour montrer que 3SAT est ASP-complet (un autre problème de solution) et "suit" la chaîne standard de réductions 3SAT => DIRECTED HAMCYCLE => UNDIRECTED HAMCYCLE => TSP
Commencez avec une formule 3SAT avec variables et calus ;φnx1,...xnmC1,...,Cm
Transformez-le en une nouvelle formule ajoutant une nouvelle variable ...;φ′t
... et en développant chaque clause en ;(xi1∨xi2∨xi3)(xi1∨xi2∨xi3∨t)
A partir de construisez le graphe de structure des diamants utilisé pour prouver que le CYCLE HAMILTONIEN DIRECTE est NP-Complet; supposons que chaque clause correspond au nœud dans ;φ′G={V,E}CjNjG
Modifiez en graphique G ′ = { V ′ , E ′ } en remplaçant chaque nœud u par trois nœuds liés u 1 , u 2 , u 3 et modifiez les arêtes selon la réduction standard utilisée pour prouver l'exhaustivité NP du CYCLE HAMILTONIEN NONDIRECTE de DIRECTED HAMILTONIAN CYCLE ie u 1 est le nœud utilisé pour les bords entrants, u 3 est le nœud utilisé pour les bords sortants;GG′={V′,E′}uu1,u2,u3u1u3
Convertissez l'instance UNDIRECTED HAMILTONIAN CYCLE sur en une instance TSP T dans laquelle toutes les arêtes de G ′ ont le poids w = 1 , à l'exception de l'arête (unique) du diamant qui passe à l'affectation "positive" de t qui a le poids w = 2 (bord rouge sur la figure ci-dessous); enfin les arêtes ajoutées pour rendre G ' complet ont un poids .G′TG′w=1tw=2G′w=3
Il est clair que l'instance TSP a un cycle simple qui visite tous les nœuds qui correspond à l'affectation satisfaisante de dans laquelle (et ce tour peut être facilement construit en temps polynomial), mais il a un poids total (car il utilise l'arête correspondant à l'affectation qui a le poids 2). a un autre cycle simple qui visite tous les nœuds avec un poids total inférieursi et seulement si l'arête de poids qui correspond à l'affectation n'est pas utilisée; ou de manière équivalente si et seulement s'il existe une autre affectation satisfaisante deφ ′ t = t r u e | V ′ | + 1 t = t r u e T | V ′ | 2 t = t r u e φ ′ t = f a l s e φTφ′t=true|V′|+1t=trueT|V′|2t=trueφ′où
; mais cela peut être vrai si et seulement si la formule d'origine est satisfaisable.t=falseφ
J'y réfléchirai davantage et j'écrirai une preuve formelle (si cela ne s'avère pas faux :-). Faites-moi savoir si vous avez besoin de plus de détails sur un ou plusieurs des passages ci-dessus.
Comme l'a noté domotorp, une conséquence intéressante est que le problème suivant est NP-complet: étant donné un graphe et un chemin hamiltonien, G a-t-il un cycle hamiltonien?GG
Donc, vous montrez essentiellement que compte tenu d'un graphique et d'un chemin H, c'est NPc de décider s'il a un cycle H, non?
domotorp
Ça a l'air super. Merci d'avoir mis l'effort dans la rédaction. Quelques changements pour répondre directement à ma question: les bords du graphique doivent être pondérés 1 à l'exception de ce bord spécial qui doit être pondéré 2 et les non-bords doivent être pondérés 3.
Lance Fortnow
1
Si vous supprimez cette arête spécifique de , alors H 1 devient un chemin H et H 2 resterait un cycle H, donc vous montrez essentiellement ce que j'ai écrit, non? Pour moi, cette déclaration semble plus intéressante que la question d'origine. gH1H2
Papadimitriou et Steiglitz (1977) ont montré que NP est complet sur ce problème.
la source