着色最適化または着色決定を使用して着色検索を解決する

Question

どうすればそれを示すことができますか 着色検索 ソリューションに多項式数の呼び出しを行うことで解決できます 着色最適化 また 着色決定? (着色検索 グラフの頂点を色付けするアルゴリズムは、隣接する頂点が異なる色を持つように色付けしています。

私はそれを解決する方法がわかりませんでしたが、ここに私が試みたものがあります（私は使用することを選びました 着色最適化):

着色検索 呼び出すことで解決できます 着色最適化 値$ m $を見つけます。これは、2つの隣接する頂点が同じ色を持たないように必要な色の量です。 $ m $が見つかると、 着色検索 各頂点に対して$ m $の異なる色を回転させることにより、グラフの頂点を色付けできます。

私は正しい軌道に乗っていますか？

Answer 1

グラフ$ g $を与えられた場合、2つのことをしたい：

1. $ g $が$ k $ colourableであるように、最小の$ k $を見つけてください。
2. そのような$ k $を考えると、$ k $の色で$ g $の色を見つけます。

着色問題の決定バージョン用のOracleがある場合、両方を行うことができます。

最初の部分では、最適な$ k $を見つけるために検索を実行できます。ここでの素朴なアプローチでさえ大丈夫です。$ g $が$ k = 1,2、 ldots、n $に対して$ k $ -colourableであるかどうかを順次尋ねることができます。次に、最大で$ n $ callsをOracleに送信します。もちろん、バイナリ検索を実行して、これを$ log n $コールまで削減できます。 （これは、決定バージョンで最適化バージョンを解決する方法でもあることに注意してください）。

次に、$ k $が最適なものを解決したことを考えると、決定Oracleを使用して$ k $ g $の$ k $ -Colouringを見つけることができます。唯一のしわは、オラクルが部分的な着色を服用していないことです。そのため、特定の頂点が特定の色に色付けされているというグラフでエンコードする方法が必要です。

これを行うには、実際に補助グラフでOracleを使用します。これは、$ g^{+} $を呼び出します。これは、$ g $と追加のエッジを備えた$ k_ {k} $です。もちろん、$ k_ {k} $は正確に$ k $の色を必要とするため、その頂点を使用して、頂点に使用できる色を示すことができます。 $ {k_ {1}、 ldots、k_ {k} } $の$ {k_ {k} $は、$ {c_ {1}、 ldots、c_ {k} }の色に対応します。 $。次に、vertex $ v $ in $ g $を示します できません $ k_ {i} $に隣接するようにすることにより、$ c_ {i} $の色で着色されます。さらに、$ c_ {j} $の色で頂点を色付けすると、に隣接します 毎日 $ k_ {i} $ with $ i neq j $（および いいえ $ k_ {j} $）に隣接します。

次に、次のことを繰り返し行います。

1. v（g）$ in 'oloured' vertex $ v を選択します。
2. すべてのvertex $ u in n（v）$について、$ u $が色付けされている場合、$ k_ {i} $が$ uk_ {i} notin e（g）$である1つの$ k_ {i} $があります。エッジ$ vk_ {i} $を$ e $に追加します。
3. 残りの頂点$ k_ {j} $の場合、$ vk_ {j} $がまだ$ e $にないように、すべてを追加します 他の $ v $と$ k_ {k} $の間のエッジと、新しいグラフが$ k $ colourableのかどうかをOracleに尋ねます。もしそうなら、このグラフを保持して次の頂点に移動します。回答がNOの場合は、ステップ3を元に戻し、次の$ k_ {j} $を試してみます。

$ g $は$ k $ -Colourableであるため、ステップ3が動作する$ k_ {j} $があることに注意してください。次に、すべての頂点を処理したとき、$ g $の各頂点は いいえ $ k_ {k} $の1つの頂点に隣接して、これは色を取得するために頂点を色付けできる色を示します。ステップ2から、これはその隣人と同じ色になることはできないことがわかります。

ステップ3では、最大で$ K $コールをOracleに通し、各頂点に対して$ g $でこれを行います。 $ k $）。