最長経路問題

グラフ理論と理論計算機科学において、最長経路問題とは、与えられたグラフ内で長さが最大となる単純な経路を見つける問題である。経路が単純であるとは、重複する頂点を持たない場合である。経路の長さは、辺の数、または (重み付きグラフでは) 辺の重みの合計で測定される。負の重みの閉路がないグラフでは多項式時間で解ける最短経路問題とは対照的に、最長経路問題はNP 困難であり、少なくともある長さの経路が存在するかどうかを問う問題の決定バージョンはNP 完全である。つまり、P = NPでない限り、任意のグラフでは決定問題は多項式時間で解くことができない。近似するのが難しいことを示す、より困難な結果も知られている。しかし、有向非巡回グラフでは線形時間で解けるため、スケジューリング問題でクリティカルパスを見つける際に重要な用途がある。

重み付けなし最長経路問題の NP 困難性は、ハミルトン経路問題の簡約を使用して示すことができます。グラフG には、最長経路の長さがn  − 1である場合にのみハミルトン経路があります( nはGの頂点の数) 。ハミルトン経路問題は NP 完全であるため、この簡約により、最長経路問題の決定バージョンも NP 完全であることがわかります。この決定問題では、入力はグラフGと数kです。望ましい出力は、 G にk以上の辺の経路が含まれている場合はyes、そうでない場合はnoです。^[1]

最長経路問題が多項式時間で解けるのであれば、最長経路を見つけ、その長さを数 kと比較することで、この決定問題を解くことができます。したがって、最長経路問題は NP 困難です。「与えられたグラフに少なくともk 個の辺を持つ単純な経路が存在するか」という問題は NP 完全です。^[2]

非負の辺重みを持つ重み付き完全グラフでは、最長経路には常にすべての頂点が含まれるため、重み付き最長経路問題は巡回セールスマン経路問題と同じである。^[3]

重み付きグラフG内の与えられた2つの頂点sとt間の最長経路は、Gのすべての重みをその否定に変更することによって得られるグラフ − G内の最短経路と同じものである。したがって、 − G内で最短経路が見つかる場合は、 G内で最長経路も見つかる可能性がある。^[4]

ほとんどのグラフでは、この変換は − Gに負の長さのサイクルを作成するため有用ではありません。しかし、 G が有向非巡回グラフ(DAG)である場合、負のサイクルは作成されず、有向非巡回グラフでもある − Gの最短経路に線形時間アルゴリズムを適用することで、 G内の最長経路を線形時間で見つけることができます。^[4] DAG の場合、ソース頂点から他のすべての頂点への最長経路は、 − Gに対して最短経路アルゴリズムを実行することで取得できます。

同様に、特定の DAG 内の各頂点vについて、 vで終わる最長パスの長さは次の手順で取得できます。

1. 指定された DAG の位相順序を見つけます。
2. DAG の各頂点vについて、位相順序で、その頂点に入力される隣接頂点を調べ、それらの隣接頂点に記録されている最大長に 1 を加算して、v で終わる最長パスの長さを計算します。v に入力される隣接頂点がない場合は、vで終わる最長パスの長さを 0 に設定します。いずれの場合も、アルゴリズムの後のステップでアクセスできるように、この数値を記録します。

これが完了すると、最大の記録値を持つ頂点vから開始し、最大の記録値を持つその隣の頂点まで繰り返し後退し、このようにして見つかった頂点のシーケンスを逆にすることで、DAG 全体で最も長いパスを取得できます。

これは、 − G上で最短経路アルゴリズムを実行することと同じです。

一連のアクティビティをスケジュールするためのクリティカルパス法では、頂点がプロジェクトのマイルストーンを表し、辺が 1 つのマイルストーンの後、別のマイルストーンの前に実行する必要があるアクティビティを表す有向非巡回グラフを構築します。各辺には、対応するアクティビティが完了するまでにかかる時間の見積もりによって重み付けされます。このようなグラフでは、最初のマイルストーンから最後のマイルストーンまでの最長パスがクリティカル パスであり、プロジェクトを完了するために必要な合計時間を表します。^[4]

有向非巡回グラフの最長経路は、階層グラフの描画にも適用できます。有向非巡回グラフGの各頂点vを、 vで終わる最長経路の長さと同じ番号の層に割り当てると、 Gの層割り当ては可能な限り最小の層数になります。^[5]

Björklund、Husfeldt、Khanna (2004) は、重み付けされていない無向グラフにおける最長経路問題は「近似困難性の理解が難しいことで有名である」と書いている。^[6] この場合に知られている最良の多項式時間近似アルゴリズムは、非常に弱い近似比しか達成しない。[ ^7]すべての${\displaystyle n/\exp(\Omega ({\sqrt {\log n}}))}$${\displaystyle \epsilon >0}$、NPが準多項式決定論的時間内に含まれない限り、最長経路を の係数以内に近似することは不可能である。しかし、この近似不可能性の結果とこの問題の既知の近似アルゴリズムとの間には大きなギャップがある。^[8]${\displaystyle 2^{(\log n)^{1-\epsilon }}}$

重み付けされていないが有向グラフの場合、強い近似不可能性の結果が知られています。任意のに対して、P = NPでない限り、問題を の係数以内に近似することはできません。また、より強力な複雑性理論的仮定では、問題を の係数以内に近似することはできません。 ^[6]色分け技術は、対数長のパスが存在する場合にそれを検出するために使用できますが、これにより得られる近似率は のみです。^[9]${\displaystyle \epsilon >0}$${\displaystyle n^{1-\epsilon }}$${\displaystyle n/\log ^{2+\epsilon }n}$${\displaystyle O(n/\log n)}$

最長経路問題は、経路の長さでパラメータ化されている場合、固定パラメータで扱いやすくなります。たとえば、次の手順を実行するアルゴリズムによって、入力グラフのサイズに比例した時間 (ただし、経路の長さに比例した時間) で解決できます。

1. グラフの深さ優先探索を実行します。 が結果として得られる深さ優先探索木の高さであるとします。${\displaystyle d}$
2. 深さ優先探索ツリーのルートからリーフへのパスのシーケンスを、探索によって走査された順序で使用して、パス幅を持つグラフのパス分解を構築します。${\displaystyle d}$
3. このパス分解に動的プログラミングを適用して、時間 内に最長パスを見つけます。ここで、 はグラフ内の頂点の数です。${\displaystyle O(d!2^{d}n)}$${\displaystyle n}$

出力パスの長さは少なくとも であるため、実行時間も によって制限されます。ここで は最長パスの長さです。^[10]色分けを使用すると、パスの長さへの依存性を単指数関数に減らすことができます。^{[9] [11] [12] [13]}同様の動的計画法の手法により、最長パス問題は、グラフの ツリー幅によってパラメータ化されている場合、固定パラメータで扱いやすいことも示されています。${\displaystyle d}$${\displaystyle O(\ell !2^{\ell }n)}$${\displaystyle \ell}$

クリーク幅が制限されたグラフの場合、最長経路は多項式時間動的計画法アルゴリズムによっても解くことができます。しかし、多項式の指数はグラフのクリーク幅に依存するため、このアルゴリズムは固定パラメータでは扱いにくいです。クリーク幅でパラメータ化された最長経路問題は、パラメータ化された複雑性クラスでは困難であり、固定パラメータで扱いやすいアルゴリズムが存在する可能性は低いことを示しています。^[14]${\displaystyle W[1]}$

木の中で最長経路を見つけるための線形時間アルゴリズムは、1960年頃にエドガー・ダイクストラによって提案され、このアルゴリズムの正式な証明は2002年に発表されました。 ^{[15]さらに、重み付き木、}ブロックグラフ、サボテン、^[16]二部 順列グラフ、^[17] およびプトレマイオスグラフで は、 最長経路を多項式時間で計算できます。^[18]

区間グラフのクラスについては、動的計画法のアプローチを使用する - 時間アルゴリズムが知られています。^[19] この動的計画法のアプローチは、円弧グラフ^[20] や共比較グラフ（つまり、比較グラフの補集合で、置換グラフも含む）のより大きなクラスに対する多項式時間アルゴリズムを得るために利用されてきました。 ^[21] どちらも同じ実行時間です。後者のアルゴリズムは、共比較グラフの辞書式深さ優先探索（LDFS）頂点順序付け^[22]の特殊な特性に基づいています 。共比較グラフについては、より実行時間の長い代替多項式時間アルゴリズムも知られています。これは、入力共比較グラフの補集合によって定義される部分順序集合のハッセ図に基づいています。^[23]${\displaystyle O(n^{4})}$${\displaystyle O(n^{4})}$${\displaystyle O(n^{7})}$

さらに、最長経路問題は、距離遺伝グラフなど、木幅またはクリーク幅が制限された任意のグラフクラス上で多項式時間で解くことができます。最後に、分割グラフ、円グラフ、平面グラフなど、ハミルトン経路問題が NP 困難であるすべてのグラフクラス上では、明らかに NP 困難です。

有向非巡回グラフの単純なモデルは、引用ネットワークを表現するためにデレク・J・デ・ソラ・プライスが開発したプライスモデルである。このモデルは単純なので、いくつかの特性について解析的な結果が得られる。例えば、ネットワークに追加されたn番目のノードからネットワークの最初のノードまでの最長パスの長さは、^[24]のように比例する。 ${\displaystyle \ln(n)}$

• ガライ・ハッセ・ロイ・ヴィタバー定理、最長経路とグラフ彩色の双対関係
• 最も長い交差していない騎士の道
• スネーク・イン・ザ・ボックス、超立方体グラフにおける最長誘導経路
• プライスモデルは、最も長いパスの長さを解析的に見つけることができる単純な引用ネットワークモデルである。

• 「Find the Longest Path」ダン・バレットの歌