事前着色拡張機能

グラフ理論において、事前着色拡張は、与えられた色のセットでグラフの頂点のサブセットのグラフ着色を、隣接する 2 つの頂点に同じ色を割り当てないグラフ全体の着色に 拡張する問題です。

複雑

事前彩色拡張は、通常のグラフ彩色問題を特殊なケースとして扱い、頂点の初期彩色部分集合が空となるため、NP完全となる。しかし、通常のグラフ彩色問題がより容易な他のグラフクラスについてもNP完全となる。例えば、ルークグラフではNP完全であり、これは部分的に塗りつぶされたラテン方陣を完成させる問題に対応する。^{[ 1 ]}

この問題は木幅が制限されたグラフでは多項式時間で解けるかもしれないが、多項式の指数は木幅に依存する。^{[ 2 ] [ 3 ]} 色数と木幅の両方が制限されている事前色付け拡張インスタンスでは線形時間で解けるかもしれない。^{[ 2 ]}

関連する問題

事前彩色拡張は、リスト彩色の特殊なケースと見なすことができます。リスト彩色とは、頂点がまだ彩色されていないグラフを彩色する問題ですが、各頂点には利用可能な色のリストが割り当てられています。事前彩色拡張問題をリスト彩色問題に変換するには、事前彩色拡張問題において彩色されていない各頂点に、初期彩色された隣接頂点でまだ使用されていない色のリストを割り当て、その後、彩色された頂点をグラフから削除します。

数独パズルは、数独グラフ上の事前着色拡張問題の例として数学的にモデル化することができる。^{[ 4 ] [ 5 ]}

参考文献

1. Colbourn, Charles J. (1984)、「部分ラテン方陣完成の複雑さ」、Discrete Applied Mathematics、8 (1): 25– 30、doi : 10.1016/0166-218X(84)90075-1、MR  0739595。
2. Jansen, Klaus; Scheffler, Petra (1997)、「木状グラフの一般化着色」、離散応用数学、75 (2): 135– 155、doi : 10.1016/S0166-218X(96)00085-6、MR 1451958 
3. Fellows, Michael R. ; Fomin, Fedor V.; Lokshtanov, Daniel; Rosamond, Frances ; Saurabh, Saket; Szeider, Stefan; Thomassen, Carsten (2011) 「木幅でパラメータ化されたいくつかのカラフルな問題の複雑性について」(PDF) , Information and Computation , 209 (2): 143– 153, doi : 10.1016/j.ic.2010.11.026 , MR 2790022 
4. ヘルツバーグ、アグネス・M. ;マーティ、M. ラム(2007)、「数独の正方形と彩色多項式」、アメリカ数学会誌、54 (6): 708– 717、MR 2327972 
5. ローゼンハウス、ジェイソン、タールマン、ローラ（2011年）、Taking Sudoku Seriously: The math behind the world's most popular pencil puzzle、オックスフォード大学出版局、p. 130

外部リンク

• プレカラー拡張機能に関する参考文献、Dániel Marx