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リスト彩色への反復可能な還元を実現した。
我々は、n頂点グラフのk彩色が、任意の固定kに対して(2−ε_k)^n時間で解けるランダム化アルゴリズムを証明する。
HNでの議論
23- emil-lp
ご存じない方のために説明すると：
K彩色とは、グラフをk色で、隣り合うノードが同じ色にならないように塗り分けられる性質のことです。K彩色問題は決定問題、つまりイエス/ノーで答えられる問いです。
グラフの彩色数とは、k彩色が可能な最小のkのことです。
明らかに、一方のアルゴリズムがあれば、もう一方のアルゴリズムもあります。
問題はこうでした：k彩色を計算する方が、その最小のk（つまり彩色数）を計算するより速いかどうか。
森、木、二部グラフは2彩色可能です。平面グラフは4彩色可能です。平面グラフの彩色数が3かどうかを判定するのはNP完全です。
非常に興味深い未解決問題があります。ハドヴィガー予想は、本質的に彩色数はクリーク（マイナー）数である（それが何を意味するにせよ）と述べています。
- black_knight
この論文の最後に、LLMの使用に関するセクションがあります。
さて、この論文は査読を受けることになります。そして、出版されたとき、私たちはその結果を、数学で出版された他の結果と同様に信頼することになるでしょう。しかし、人間が間違いを犯さないわけではない一方で、LLMは正しく見える自信満々の内容を吐き出す傾向があります。ですから、このように証明を生成するために使われるとき、私は心配になります。査読は完璧ではなく、LLMのタイプの誤りを捕捉するように調整されていないかもしれません。
これに対する解決策があります。それは、結果を形式化して機械検証を受けることです。そしてLLMを使えば、これは今後ベストプラクティスになると私は言いたいです。
- drivebyhooting
それほど速くはありません。
複雑度F(n)の任意のk彩色アルゴリズムは、Nに関して二分探索することで、複雑度lg(N)F(N)の彩色数アルゴリズムを作るために使えます。