グラフ3色性は自己還元可能です

Question

私は、グラフ3-コロラリビティの問題の自己緩和性に興味があります。

グラフ3-コロラリビティ問題の定義。

無向グラフを考えると、$ g $が存在しますか？ノードを赤、緑、青に着色する方法があります。

自己抑制の定義。

言語$ l $は、$ l = l（t^l）$のようにオラクルチューリングマシンtm $ t $が存在する場合、$ n $ n $、$ t^lの入力$ x $の場合、自己還元可能です。 ）$ $ n-1 $の長さの単語については、$ soracleをクエリします。

グラフの3色性が自己低下できることを非常に厳格で正式な方法で示したいと思います。

SATの自己抑制性の証明は、例として使用できます（SATの自己抑制性).

私の意見では、グラフの3色性の自己抑制性の証明の一般的な考えは、いくつかの側面でSATの自己抑制性の証明とは異なります。

• SATにはすべてのリテラル（真または偽）ごとに2つの選択肢があり、グラフ3色性には3つの選択肢（つまり、赤い青色）があります。
• SATリテラルの選択は互いに独立しており、グラフ3色の色の選択は厳密に依存しています。隣接するノードは異なる色を持つ必要があります。

証拠の一般的な考え方.

$ c_ {v_i} $ bertex $ v_i $の色を示します。これは、次の値のいずれかをとることができます（赤、緑、青）。任意のvertex $ v_0 $を着色して、指定されたグラフからグラフ$ g $を定義し、$ c_ {v_0} $を 'red'に割り当て、Colored Vertex $ v_0 $を入力にグラフ$ g '$を配置しますオラクルの。 Oracleが1回答します。これは、変更されたグラフがまだ3色であることを意味します。現在の割り当てを保存して新しい反復を開始します。異なるVertex $ V_1 $は、並外れた頂点によるColor Vertex $ v_1 $を隣接する頂点の色に応じてvertex $ v_1 $を色付けします。 Oracleが0に答えている場合（以前の割り当てが3つの色が壊れていることを意味する場合、3色のセットとは異なる色を選択しますが、それでも隣接する頂点の色に応じています。

以前の証明は数学的な堅牢性ではありません。問題は、それを改善し、より正式で数学的に厳格にする方法です。新しい頂点に既に色付きの頂点があるエッジがなく、新しい頂点がすでに色の頂点に隣接している場合、より慎重に区別する必要があるようです。

さらに、グラフの3色性が自己緩和可能であることを証明したいと思います。

下向きの自己削減言語の定義。

言語$ a $は、最短クエリの結果を使用して$ x in $で多項式時間で決定できる場合、下方に自己削減可能であると言われています。

アイデアはシンプルで直感的であるように思われます。任意の頂点を着色することから始め、各反復でもう1つの色の頂点を追加し、以前の色を逆にしない場合でもグラフがまだ3色である場合はOracleで確認し、別の色を確認します。

しかし、証明を厳格な方法で書く方法と、より重要なグラフの適切なエンコードを見つける方法。

要するに、グラフ3色性は自己削減可能であり、厳格で正式な方法で自己削減可能であることを示したいと思います。

私たちとあなたの考えを共有してくれて感謝します。

アップデート：

下向きの自己抑制

下向きの自己抑制は決定問題に適用され、Oracleは、より短い入力で同じ決定問題に答えます。下向きの自己減少のプロセスの終わりに、適切な色の割り当てが必要です。

3つ以上の頂点を持つ3つの色グラフ$ g $には、同じ色の2つの頂点$ x、y $があります。どうやら、3色と3つ以上の頂点しかないので、隣接していない頂点は同じ色を持つ可能性があります。 $ x $と$ y $を3つの色と同じ色とマージする場合、グラフが3の場合、$ xに隣接するすべての頂点の正しい割り当てが存在するという理由だけで、3つの色グラフがあります。 $と$ y $は、$ x、y $の同じ色に応じて、$ x、y $をマージすることにより、頂点の色を変更する必要はありません。 （私はそれが最良の説明ではないことを知っています、誰かがそれをよりよく説明できれば感謝します）。すべての反復で、2つの非隣接する頂点$ x、y $ of graph $ g $、マージ$ x $と$ y $をマージし、Graph $ g '$を取得します。これはOracleへのより短い入力です。 Oracleは、3色かどうかにかかわらず、回答します。問題は、Oracleの入力に$ g $を設定する前です。マージされた頂点を色付けし、$ g $の色をテストする必要があります。それのためにエンコード。

自己抑制性

まず、指定されたグラフ$ g $が3色であるかどうかを確認する必要があるため、Oracleの入力に設定すると、Oracleが3つの場合に回答します。 2つの非隣接する頂点は、3色のグラフで同じ色を持つことができます。自己抑制のプロセスは、反復で実行する必要があります。特定のグラフ$ g $の小さなサブグラフ$ g '$から開始できると思います。パラレルでは、すでに色付けされた頂点の割り当てを維持する必要があります。残念ながら、私はまだ完全にアイデアを得ていません。助けとヒントをありがとう。

Answer 1

VORが彼のコメントで言及しているように、3色の部分が色の部分的な割り当てを受け入れないため、あなたの削減は機能しません。単一の頂点の色を設定しないため、問題はさらに深くなります どれか グラフが3色であるかどうかを判断する際の進捗状況：実際、グラフは3色である場合、vertex $ v $に$ c $が割り当てられている3色があり、$ v、c $が選択されます。

エクササイズを解決する方法、2番目の部分についてのヒントを以下に示します。 3つ以上の頂点にグラフ$ g $を3色にするには、2つの頂点$ x、y $が同じ色を取得します（なぜ？）。 $ x $と$ y $をマージすると、結果のグラフはまだ3色です（なぜ？）。このアイデアを使用して、3色性のために下向きの自己還元アルゴリズムを構築してみてください。

編集：そして、ここにエクササイズの解決方法、最初の部分があります。任意の2つの接続されていない頂点$ x、y $を考慮してください。同じ色を取得する着色がある場合、$ g_ {xy} $は3色（なぜ？）であり、$ g $の色は$ g_ {xy} $の色から抽出できます（どのように？）。このプロセスはいつ停止しますか？