少なくともkエッジが離れている2つのパスを見つけることを証明する方法はNPハードですか？

Question

$ g=（v、e）$ は、無効になっている、無向、接続されているグラフになります。 2つの開始頂点 $ s_1 $ 、および $ s_2 $ と2つのエンド頂点 $ T_1 $ と $ t_2 $ は $ s_1 $ からのパスがありますか？ $ t_1 $ と $ s_2 $ $ t_2 $ 2つのパス間の最も近いエッジ数が少なくとも $ k $ であるようになる？ 2つのパスは $ k $ が閉じている場合、2番目のパスの頂点への頂点への頂点間の最小距離の最小値が $ k $ 。

私は3SATからの減少を考慮して、最初の経路が変数を表し、2番目の経路が句を表すことを考えていましたが、そこからどこへ行くのかわからない。

Answer 1

3SATから減らすことができます。

グラフには2つの部分があります。一部は「可変」部分です。各変数 $ v_1、\ ldots、v_n $ のそれぞれについては、3つの頂点 $ v_i ^ +、v_i ^ - 、v_i $ 、およびこの部分は、 $ i \ in [n] $ ：

のための次のエッジで構成されています。

$$（v_ {i-1}、v_i ^ +）、（v_ {i-1}、v_i ^ - ）、（v_i ^ ^ +、v_i）、（ v_i ^ - 、v_i）$$

ここ $ v_0 $ は、 $ s_1 $ 、 $ v_n $ は $ t_1 $ で識別されます。

2番目の部分は "句"部分です。各句 $ c_1、\ ldots、c_m $ のそれぞれについては、4つの頂点 $ w_j ^ 1、w_j ^ 2、w_j ^ 3、w_j $ は以前のように接続されています。 $ s_2 $ 、 $ t_2 $ 。

$ v_i ^ b $ を $ w_j ^ r $ のパスを介して $ K $ （十分に大きい $ k $ の場合）math-コンテナ "> $ v_i ^ b $ （ $ v_i $ 、または $ \ overline {v_i} $ < / span>、 $ b $ ）によると、 $ j $ 'th $ c_j $ 。

また、これらのパスのすべてのマインドポイントを取り、それらをすべて接続します（それらをクリークにする）。

$（s_1、t_1）$ -pathを真理の割り当てとして考えることができ、 $ （S_2、T_2）$ 各句の満足度リテラルを識別する範囲である。最小距離は $ k $ 以上で、 $ k $ のみがそうでなければ。

部品間の交差点を渡るためのポイントがないことを確認する必要があります。一方のパスが交差する場合は、2つのパスが互いに近づく（一定の距離で、十分な大きさの $ k $ が $ k $ 。両方の十字架の場合、中点のクリークはそれらが最大の距離であることを確実にします。