Comment prouver la recherche de deux chemins qui sont au moins k bords d'accueil sont np-dur?

Question

let $ g= (v, e) $ être un graphique non déroulé, non dirigé et connecté. Donné deux sommets de démarrage $ S_1 $ et $ s_2 $ et deux sommets de bout $ t_1 $ et $ t_2 $ y a-t-il un chemin de $ S_1 $ $ t_1 $ et $ s_2 $ to $ t_2 $ tel que le nombre le plus proche de bords entre les deux chemins est au moins $ k $ ? Deux chemins sont $ k $ Fermer si le minimum des distances les plus courtes entre tous les sommets du premier chemin sur n'importe quel sommet sur n'importe quel sommet sur le deuxième chemin est $ K $ .

Je pensais à réduire à partir de 3SAT et à laisser le premier chemin représenter les variables et le deuxième chemin représente les clauses, mais je ne suis pas sûr où aller de là.

Answer 1

Vous pouvez réduire à partir de 3SAT.

Le graphique a deux parties. Une partie est la partie "variable". Pour chacune des variables $ v_1, \ ldots, v_n $ Il y a deux sommets $ v_i ^ +, v_i ^ - , v_i $ , et cette partie est constituée des bords suivants, pour $ i \ in [n] $ :

$$ (v_ {i-1}, v_i ^ +), (v_ {i-1}, v_i ^ -), (v_i ^ +, v_i), ( v_i ^ -, v_i) $$

ici $ v_0 $ est un nouveau sommet, identifié avec $ s_1 $ et $ v_n $ est identifié avec $ t_1 $ .

.

La deuxième partie est la partie "Clause". Pour chacun des clauses $ C_1, \ ldots, c_m $ là quatre sommets $ w_j ^ 1, w_j ^ 2, w_j ^ 3, w_j $ , connecté beaucoup comme avant, avec $ s_2 $ et $ t_2 $ .

Nous connectons $ v_i ^ b $ avec $ w_j ^ r $ via un chemin de longueur < span class="math-conteneur"> $ k $ (pour une certaine constante assez constante $ k $ ) si le littéral $ v_i ^ b $ ( $ v_i $ ou $ \ ui} $ {V_I} $ / span>, selon $ B $ ) est le opposé de $ j $ 'Th littéral dans $ C_J $ .

En outre, nous prenons toutes les mémoires de ces chemins et nous les connectons tous (en les faisant dans une clique).

Nous pouvons penser à une $ (s_1, t_1) $ -Path comme une affectation de vérité et d'une $ (S_2, T_2) $ -Path comme identifiant un littéral satisfait dans chaque clause. La distance minimale est plus que $ k $ s'il s'agit bien du cas, et seulement $ k $ sinon .

Vous devez également vérifier qu'il n'ya aucun point pour les chemins pour traverser entre les pièces. Si seulement l'un des chemins croise, les deux chemins seront rapprochés (à une distance constante, qui pour suffisamment de $ k $ sera plus petit que $ K $ ) immédiatement après la traversée. Si les deux cross, alors la clique de milieu du point de midi s'assurera qu'ils sont à distance au plus 1.