単色三角形

グラフ理論と理論計算機科学において、単色三角形問題とはグラフ上のアルゴリズム問題であり、与えられたグラフの辺を三角形のない2 つのサブグラフに分割することが目的である。これはNP 完全であるが、木幅が制限されたグラフ上では固定パラメータで処理可能である。

問題の説明

単色三角形問題は、ノード集合 V とエッジ集合 E を持つ n ノードの無向グラフ G(V,E) を入力として受け取ります。出力はブール値で、G のエッジ集合 E が 2 つの互いに素な集合 E1 と E2 に分割でき、2 つのサブグラフ G1(V,E1) と G2(V,E2) が両方とも三角形のないグラフである場合はtrue、そうでない場合は false になります。この決定問題はNP 完全です。^[1]

複数の色への一般化

この問題は、三角形のない辺彩色に一般化することができ、グラフの辺に色を割り当てて、3 辺すべてに同じ色が割り当てられる三角形がないようにする問題です。単色三角形問題は、使用できる色がちょうど 2 色である場合の三角形のない辺彩色の特殊なケースです。2 色の三角形のない辺彩色が存在する場合、各色の辺は単色三角形問題の 2 つの集合 E1 と E2 を形成します。逆に、単色三角形問題に解がある場合、E1 に 1 色、E2 に 2 色目を使用して、三角形のない辺彩色を得ることができます。

ラムゼーの定理との関連

ラムゼーの定理によれば、色の有限数kに対して、 n個以上の頂点を持つ完全グラフにk色の三角形のない辺彩色が存在しないような数n が存在します。k = 2 の場合、対応するn の値は6 です。つまり、完全グラフK ₆上の単色三角形問題の答えは「いいえ」です。

パラメータ化された複雑さ

単色三角形問題は、グラフのモナド二階論理(MSO ₂ ) で、辺を 2 つの部分集合に分割し、その分割の同じ側に辺がすべて属する 3 つの隣接する頂点が存在しないという論理式で簡単に表現できます。クールセルの定理から、単色三角形問題は、木幅が制限されたグラフ上で固定パラメータで処理可能であることがわかります。より正確には、入力グラフの頂点の数に、急速に増加するが計算可能な木幅の関数を掛け合わせた時間が実行時間となる、問題を解くアルゴリズムがあります。^[2]

参考文献

^ ガリー、マイケル・R. ;ジョンソン、デビッド・S. (1979)、コンピュータとイントラクタビリティ：NP完全性理論ガイド、WHフリーマン、ISBN 978-0-7167-1045-5A1.1: GT6、191ページ。
^ Arnborg, Stefan; Lagergren, Jens; Seese, Detlef (1988)、「木分解可能グラフの簡単な問題 (拡張概要)」、Automata、言語、プログラミング (Tampere、1988)、Lecture Notes in Computer Science、vol. 317、ベルリン: Springer、pp. 38–51、doi :10.1007/3-540-19488-6_105、ISBN 978-3-540-19488-0、MR 1023625。

[1] ガリー、マイケル・R. ;ジョンソン、デビッド・S. (1979)、コンピュータとイントラクタビリティ：NP完全性理論ガイド、WHフリーマン、ISBN 978-0-7167-1045-5A1.1: GT6、191ページ。

[2] Arnborg, Stefan; Lagergren, Jens; Seese, Detlef (1988)、「木分解可能グラフの簡単な問題 (拡張概要)」、Automata、言語、プログラミング (Tampere、1988)、Lecture Notes in Computer Science、vol. 317、ベルリン: Springer、pp. 38–51、doi :10.1007/3-540-19488-6_105、ISBN 978-3-540-19488-0、MR 1023625。