再帰最大優先アルゴリズム

再帰最大優先（RLF ）アルゴリズムは、 NP困難なグラフ彩色問題に対するヒューリスティックです。このアルゴリズムは、1979年にフランク・レイトンによって最初に提案されました。^[1]

RLF アルゴリズムは、各カラー クラスを 1 つずつ構築して、グラフの頂点に色を割り当てます。これは、グラフ内の頂点の最大独立セットを識別し、これらに同じ色を割り当て、これらの頂点をグラフから削除することによって行われます。これらのアクションは、頂点がなくなるまで残りのサブグラフで繰り返されます。

高品質の解（少ない色数で解く）を形成するために、RLFアルゴリズムは特殊なヒューリスティックルールを使用して「良質」の独立集合を識別しようとします。これらのヒューリスティックにより、RLFアルゴリズムは二部グラフ、サイクルグラフ、ホイールグラフに対して正確になります。^[2]ただし、一般に、このアルゴリズムは近似値であり、グラフの彩度数よりも多くの色を使用する解を返す可能性があります。

このアルゴリズムは、次の 3 つのステップで説明できます。このプロセスの最後に、グラフの実行可能な -色付けを表す頂点の分割が与えられます。 ${\displaystyle {\mathcal {S}}}$${\displaystyle |{\mathcal {S}}|}$${\displaystyle G}$

1. を空の解とします。また、を頂点集合と辺集合で構成される色付けしたいグラフとします。${\displaystyle {\mathcal {S}}=\emptyset }$${\displaystyle G=(V,E)}$${\displaystyle V}$${\displaystyle E}$
2. 最大の独立集合 を特定します。これを行うには、次の手順を実行します。 ${\displaystyle S\subseteq V}$
   1. に追加される最初の頂点は、内で最も多くの隣接頂点を持つ頂点である必要があります。${\displaystyle S}$${\displaystyle G}$
   2. に追加される後続の頂点は、(a) 現在 内のどの頂点にも隣接しておらず、(b) 内の頂点に隣接する隣接頂点の数が最大である頂点として選択する必要があります。条件 (b) の同点の場合は、 内にない隣接頂点の数が最小の頂点を選択することで解決できます。頂点は、これ以上頂点を追加できなくなるまで、このようにして に追加されます。${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$
3. 次に、の頂点を設定してから削除します。にまだ頂点が含まれている場合は、手順 2 に戻ります。含まれていない場合は終了します。${\displaystyle {\mathcal {S}}={\mathcal {S}}\cup \{S\}}$${\displaystyle S}$${\displaystyle G}$${\displaystyle G}$

右に示すグラフを考えてみましょう。これはホイール グラフなので、RLF によって最適に色付けされます。アルゴリズムを実行すると、次の順序で頂点が選択され、色付けされます。 ${\displaystyle G=(V,E)}$

1. 頂点（色1）${\displaystyle g}$
2. 頂点、そして（色2）${\displaystyle a}$${\displaystyle c}$${\displaystyle e}$
3. 頂点、、そして（色3）${\displaystyle b}$${\displaystyle d}$${\displaystyle f}$

これにより、最終的な 3 色のソリューションが得られます。 ${\displaystyle {\mathcal {S}}=\{\{g\},\{a,c,e\},\{b,d,f\}\}}$

をグラフの頂点の数、を辺の数とします。ビッグオー記法 を用いて、レイトンは最初の論文で RLF の複雑度は であると述べていますが、これは改善の余地があります。このアルゴリズムのコストは、ステップ 2 で上記のヒューリスティック ルールに従って頂点を選択することに大きく起因します。実際、独立集合 に追加する頂点が選択されるたびに、各未着色頂点について近傍に関する情報を再計算する必要があります。これらの計算は時間内に実行できるため、RLF の全体的な複雑度は です。^[2]${\displaystyle n}$${\displaystyle m}$${\displaystyle {\mathcal {O}}(n^{3})}$${\displaystyle S}$${\displaystyle {\mathcal {O}}(m)}$${\displaystyle {\mathcal {O}}(mn)}$

ステップ2のヒューリスティックをランダム選択に置き換えると、このアルゴリズムの複雑さは に減少します。ただし、結果として得られるアルゴリズムは通常、RLFに比べて品質の低いソリューションを返します。^[2]また、二部グラフ、サイクルグラフ、ホイールグラフに対しても不正確になります。 ${\displaystyle {\mathcal {O}}(n+m)}$

2021年にルイスが行った実験的比較では、RLFはランダムグラフ上で貪欲アルゴリズムやDSaturアルゴリズムなどの代替ヒューリスティックよりも大幅に優れた頂点カラーリングを生成することが示されました。しかし、RLFは全体的な複雑さが高いため、実行時間もこれらの代替手段よりも長くなることがわかりました。^[2]${\displaystyle {\mathcal {O}}(n+m)}$ ${\displaystyle {\mathcal {O}}((n+m)\lg n)}$

• 高性能グラフカラーリングアルゴリズム 書籍『A Guide to Graph Colouring: Algorithms and Applications』 (Springer International Publishers、2021 年) で使用されているグラフカラーリングアルゴリズムのスイート (C++ で実装)。