グラフ理論と理論計算機科学において、単色三角形問題（たんろいさんさんさん、英: monochromatic triangle problem）はグラフ上のアルゴリズム問題であり、与えられたグラフの辺を三角形を含まない2つの部分グラフに分割することを目的とする。木幅が制限されたグラフでは、 NP完全だが固定パラメータで扱える。
問題の説明
単色三角形問題は、nノードの無向グラフG(V,E)を入力とし、そのノード集合は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 6上の単色三角形問題に対する答えは「いいえ」である。
パラメータ化された複雑さ
グラフのモナディック二階 論理（MSO 2）において、辺を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, languages and programming（タンペレ、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。