k彩色問題は彩色数を計算するより高速に解ける

k-Coloring is Faster than Computing the Chromatic Number

n頂点グラフのk彩色問題に対して、実行時間(2−ε_k)^nのランダム化アルゴリズムを提案した。ここでε_k>0は任意の固定kに対して存在する。これまでk≤6の場合のみ、BjörklundらのO*(2^n)アルゴリズムより高速な解法が知られていた。本研究では、Zamirによる(k+2)彩色からkリスト彩色への還元と、ハイパーグラフコンテナに基づく手法を一般化・統合し、さらに長短の色リストが混在するリスト彩色インスタンス向けの新アルゴリズムを組み合わせることで、固定パレット上で(k+1)リスト彩色からkリスト彩色への反復可能な還元を実現した。