次の問題が NP-HARD にあることを知っています: 単純なグラフ G=(V,E)、2 つの頂点 v、V の v'、整数 B、および非負の長さ関数 len: E-> Z+ が与えられた場合、長さが B 未満の v から v' への単純なパスはありますか?
私の質問は次のとおりです。以前と同じ条件が与えられた場合、頂点 v から v' までの G 内の必ずしも単純ではない最長のパスを見つけることに関心がある場合、問題はまだ NP-HARD にありますか?
注: ハミルトンパスをそれに還元しようとしましたが、NP に還元可能な問題があるかどうかを証明することはまだできません。ゲイリー＆ジョンソンも調べましたが、見つかりませんでした。
この問題が NP-HARD であるかどうかを証明するためのヒントを教えてください。前もって感謝します！
負のサイクルのないグラフの最短単純パスは NP 困難ではありません。Cormen の「アルゴリズム入門」を参照してください。Bellman-Ford のアルゴリズムを使用して解決できます。負のエッジの重みがない場合は、ダイクストラのアルゴリズムも使用できます。どちらも、単一のソースからグラフの他のすべてのノードへの最短パスをすべて計算します。したがって、あなたの最初の問題は、私が正しく理解しているように、NP 困難ではありません。
最長単純経路問題は、正の循環が存在しない場合、負の循環がない最短単純経路問題の双対です。また、NP 困難ではありません。
ノードへのすべての可能なパスを覚えておく必要があり、指数関数的である可能性があるため、負のサイクルを許可する最短の (単純ではない) パスは NP 困難です。正のサイクルが許可されている最長 (単純ではない) パスの問題についても同じことが言えます。
それがあなたの質問に答えることを願っています。
何か見落としていたり、記述が間違っていたりした場合は、お気軽に訂正してください。
いいえ、NP 困難ではありません。最短経路アルゴリズム (Bellman-Ford など) を使用して、エッジの長さを否定することで多項式時間で解決できます。特にすべてのエッジの重みが負でない場合、最長パスは無限になる可能性が高いことに注意してください。