Ajoutez une correspondance à un chemin hamiltonien pour réduire la distance maximale entre des paires de sommets données

Quelle est la complexité du problème suivant?

Entrée :

• unchemin hamiltonienen K n$H$$K_n$
• un sous-ensemble de paires de sommets$R \subseteq [n]^2$
• un entier positif $k$

Requête : existe-t-il un correspondant tel que pour chaque , ? (où G = ( [ n ] , M ∪ H ) )$M$$(v,u) \in R$$d_G(v,u) \leq k$
$G = ([n], M\cup H)$

J'ai eu une discussion avec un ami sur ce problème. Mon ami pense que le problème est en temps polynomial. Je pense que c'est NP-complet.

Cette réponse est incorrecte .

Votre ami a raison. Votre problème (tel qu'interprété par Sasho) ne place aucune restriction sur la cardinalité du correspondant . Par conséquent, choisir C à une mise en correspondance entre les paires de R . Alors pour tout entier positif k , la distance entre chaque paire dans R est inférieure à k .$C$$C$$R$$k$$R$$k$

Votre problème devient intéressant si vous forcez les chemins pour contenir les bords de la fois la mise en correspondance et le chemin P .$C$$P$

MISE À JOUR: la réponse ci-dessous n'est pas correcte, car j'ai supposé à tort que le chemin hamiltonien est dans un graphe arbitraire, pas dans . Je ne le supprime pas, je pourrai peut-être le réparer ou il donnera quelques indices pour une autre réponse.$K_n$

Je pense que c'est NP-complet. Ceci est une idée de réduction très informelle / rapide de 3SAT

Pour chaque variable ajouter un « gadget variable » avec:$x_i$

• trois nœuds $X_i, +X_i, -X_i$
• deux bords variables et ( X i , - X i$(X_i,+X_i)$$(X_i,-X_i)$

Ajoutez un nœud source et connectez-le à toutes les variables X i .$S$$X_i$

Pour chaque clause ajoutez un nœud C j et connectez-le aux variables correspondantes + X i ou - X i qui forment la clause.$C_j$$C_j$$+X_i$$-X_i$

L'image suivante représente: $(+x_1 \lor -x_2 \lor -x_3) \land (-x_2 \lor x_3 \lor x_4)$

L'ensemble (nœuds qui doivent être liés) contient ( S , C 1 ) , ( S , C 2 ) , . . $R$$(S, C_1), (S,C_2), ...$

Le chemin simple doit inclure toutes les arêtes "BLEUES" à l'exception des arêtes variables ( X i , + X i ) et ( X i , - X i ) (dans l'image ci-dessus, les arêtes bleues représentent les arêtes que nous incluons dans P ).$P$$(X_i, +X_i)$$(X_i, -X_i)$$P$

À ce stade, la formule initiale est satisfaisable si et seulement si le chemin le plus court de à chaque nœud de clause C j n'est pas supérieur à trois. En effet pour atteindre une clause de S en trois étapes il faut parcourir au moins une variable X i : S → X i → ± X i → C j . Il faut donc traverser l'une des deux arêtes: X i → + X i ou X i → - X i ) et l'inclure dans $S$$C_j$$S$$X_i$$S \to X_i \to \pm X_i \to C_j$$X_i \to +X_i$$X_i \to -X_i)$$C$(car par construction ça ne fait pas partie de ). Mais les deux ne peuvent pas être inclus, car ils partagent un sommet.$P$

Mais nous ne sommes pas sûrs de pouvoir construire un chemin P simple qui inclut tous les bords bleus car certains nœuds ont plus d'un bord bleu incident.$P$

Pour résoudre ce problème, nous remplaçons chaque nœud par plusieurs bords bleus incidents, par un arbre qui ne contient que des paires de bords bleus incidents qui seront inclus dans et des bords qui les séparent et qui devraient être inclus dans C pour atteindre les nœuds de la clause:$P$$C$

Le graphique d'origine devient:

$K$$C_j$$S$

$C$

$P$